离散数学是计算机科学的基础理论，离散结构的基础知识和逻辑思维的形式化是信息技术类学生的基本功，离散数学的基本概念是理科专业学生进行信息类课程学习的重要基础。 本课程介绍计算机科学和信息技术理论基础的概念和思想方法，介绍数理逻辑、集合论、图论、抽象代数和形式语言与自动机等各部分的基本概念，介绍离散数学基本概念和空间信息技术之间的联系与结合，培养学生理解和掌握离散数学基本概念，采用形式化方法分析问题，并能自觉运用逻辑分析、结构层次分析和同构类比等思想方法解决问题的能力。
86-BNF范式
Loading...
En provenance du cours de Peking University
离散数学概论 Discrete Mathematics Generality
150 notes
À partir de la leçon
形式语言与自动机：基本概念
Rencontrer les enseignants
陈斌副教授
北京大学
【音乐】 嗨，欢迎回来。
接下来呢我们再来介绍一种，另外一种对于语言的
语法的一种表示的方式，称作为BNF范式， 或者叫做Backus-Naur范式。
那么这个范式呢是由两位这个计算机专家的名字联合命名的， 它是在1960年提出来用来
描述这个ALGOL60这个高级算法语言的这么一个语法的。
那么BNF范式的这个形式非常地简单，它只包含着三个符号。
第一个符号呢是一个，两个冒号加一个等号，那么这就叫做定义为。
然后第二个符号呢是一个竖杠，是叫做或。
第三个符号呢是一对尖括号，那么尖括号呢是用来区分这个非终结符的。
那么这样呢，我们就可以写出这个BNF里头的 一个产生式，比如说像这个A是一个非终结符，那么它用尖括号括起来，
然后定义为，然后有一个a，然后有一个竖杠，然后有一个 bc，然后竖杠，有个c，然后后面接着一个非终结符。
那么这个的意思呢就是说可以把A替换成a，也可以替换成bc，
也可以替换成c和这个B非终结符这三种途径，它竖杠是表示或的意思嘛。
那么这样呢， 这个BNF呢可以用来表示这个2、
3型语法，也就是上下文无关语法和正则语法。
那么可见呢，它的这个表示的方法跟 我们的这个程序设计语言是非常地相关的。
所以呢在BNF里边， 它BNF一般的用途就是用来表示我们程序设计语言的语法。
包括我们的C语言，你在每一本C语言的教材的最后，它都会有一个附录。
附录呢就是C语言的语法的描述，那么它肯定是用BNF来 书写的。
每一个BNF的产生式呢左部呢仅有一个 非终结符，它只有一个非终结符，那么这个呢符合这个上下文无关的语法和
正则语法它的这个，对产生式的规定。
那么而且呢它可以用，如果产生式， 这个左部都相同的话，那么可以把这些产生式合并在一起。
然后用这个竖杠，然后用这个或来进行隔开。
那么非终结符呢用这个 一对尖括号来进行标记，就是BNF范式的 这个定义。
那么我们来看看几个例子。
我们比如说中文句子这么一个例子，那么我们前面的已经用了 短语结构语法来进行描述了。
我们看看BNF它是一个什么样的形式。
它就是句子，然后定义为，然后主语、 谓语，这都是非 终结符。
然后呢主语定义为张三、 李四，然后
加一个竖杠，而这个竖杠，这个或呢，在产生式关系里头， 在产生式里是没有的。
然后谓语呢变成副词、 动词这样的非终结符。
然后副词变成深情地和狂野地，中间加一个竖杠。
然后动词呢变成歌唱、 奔跑，然后加一个竖杠。
那么这个呢就是完整的中文句子，从短语结构语法 翻译成BNF它所变成的这个样子。
我们还可以再看一个例子。
就是像这个正则表达式，a(bb)*c，这是一个正则表达式，它所对应的
这个BNF的规定是一个什么样的BNF的语法。
我们前面呢也接触过这样的a(bb)*c它所用到的这个短语结构语法，对吧？
那么我们把每个短语结构语法当中的每一个产生式， 然后把它翻译成这个BNF，那么就是v0，它是一个非终结符，
定义为a<w>，w是一个非终结符，那么这个看得很明显。
然后w呢变成了bb<w>，也是一个非终结，然后|c， 就这这两，两个这个
BNF范式里边的规则，就可以用来描述这么一个例子了。
那么这里头我们很明显地看到，这个递归呢出现了
一次，也就是w变成了bbw，它出现一次，而且呢这个w呢， 它这个递归呢是出现了非终结符，出现在最右边。
所以呢，我们把这样的一个 语法呢就称作为正规的语法，也就是，实际上它是一个正则文法，对吧？
那么在3型文法当中，这个递归产生式都必须是 正规的。
我们再来看第三个例子，就是十进制数。
十进制数这样的例子呢，我们可以，我们说十进制数呢它都是这个
有左边，然后有小数点，然后有右边这样。
所以十进制数呢它会被定义成无符号的整数， 或者是一个小数，或者呢是无符号整数加一个小数。
我们知道小数呢都是以点开始的，就是一个点，然后后边1,2,3。
那么这是一个小数，如果没有点，那么它就是一个无符号的一个整数。
那么把无符号整数呢就变成，要么它是单个的数字， 要么呢就是数字，再跟上一个无符号整数。
那么这里呢就涉及到一个 在最右边的这么一个递归，它只出现了一次的递归。
那么小数就定义为一个点，然后后边跟着
无符号整数，那么这个点呢因为它没有加尖括号，所以呢它是一个终结符，而不是一个非- 终结符。
所以呢这个点是一个特殊符号。
那么把数字呢就定义成0|1|2|3|4|5|6|7|8|9。
然后再用竖杠隔开，那这样呢，十进制数我们就可以知道了。
例如像1.23这是一个十进制数，像12这是一个十进制数。
或者说 .34，这也是一个十进制数，那么这个呢就通过BNF范式的形式
定义了这个十进制数的这个产生的规则。
那么还可以在 C++程序设计语言里头有定义这个标识符。
那么标识符呢我们知道在C语言当中，它通常用来做这个 变量的名称，或者函数的名称。
那么所以呢它是一个以字母开头的字母数字串，那么它主要用于在变量、 函数等命名的。
那所以呢，用BNF来来进行表达呢，也是很方便的。
第二个字标识符就定义为字母，或者字母加上一个后部。
那么后部呢就定义为字母，或者 数字，或者字母加后部，或者呢数字加后部。
那么这里头，这个后边两个这个规则就涉及到 一个递归，那么这个递归呢就使得后部呢是一个
字母和数字混合起来的一个串，那么它的长度并没有什么限制。
而我们把标识符呢变成字母加后部呢，那就说明了它是一个以字母开头的，对吧？
那么字母呢就定义为a,b,c,d,e,一直到z，26个字母，然后中间呢用竖杠隔开。
同样地，数字呢也跟前面一样，从0到9也用竖杠隔开，那这样呢就整个的是标识符的这么一- 个定义。
大家如果去翻那个C语言的教科书的最后的这个附录里边， 对于C语言的这个标识符，它的这个BNF
的描述应该也大致是这个样子的，它并没有什么太大的不一样。
那么BNF呢它如果只用这个
最核心的这三个符号，有的时候呢显得会特别地繁琐。
尤其是在程序设计语言里头，有一些可选的结构，比如说条件语句，
有if，then，然后也可以是if，then，else这样的形式呢，那么else呢- 它是一个可选的。
那如果用标准的BNF，那么你要为这个if语句呢，
定义两个不同的这个规则，而这个规则呢区别在于一个有else，一个没有else。
那么其他大部分的东西都是一样的，那就显得很繁琐。
所以到后来呢，人们对BNF进行了一个扩展。
那么扩展呢主要包括了这几个方面。
第一个呢是所谓的可选项，它用的一个方括号括起来，这个可选项，就是说可以有，也可- 以没有。
那比如说这个if语句它就可以定义成这样了， if语句就定义为if这个关键字，加一个逻辑表达式，
再加一个then，再then这个关键字，再加上一个语句。
那么到这儿呢为止，就可以了，它是一个完整的if语句。
当然也可以是这个中间有个else， 它else是可选的，else后边跟一个语句，然后呢再加上end if。
这么一个，所以呢从这当中呢，用方括符括起来的，这是一个可选结构。
还有一些呢，比如说是可以重复多次的。
那么重复多次，那么在BNF里头，那么一般地都会用递归来进行表达。
但是呢递归呢有的时候呢会，因为太过于 简洁，而表达呢也会非常地繁琐，用来表达一些重复项。
那么在扩展的当中，这个重复项呢就用 方括号这个括起来，就表示0次或者说多次地重复。
比如说这个标识符，刚才我们用了一大段的
这个不同的这个，这个BNF的这个规则，描述了这个标识符。
那么其中呢，实际上主要是希望说这个字母后边引一个字母、 数字的混合串，
而且呢它的长度不限，那么我们就引入了什么
后部啊这些新的一些终结符，那么也显得特别地繁琐。
那么引入了这个扩展，重复项这么一个扩展的话，那么这个标识符呢就
非常地简单，它的定义，就是字母开头，然后后面字母或者数字 加个方括号，它可以重复0次到多次。
那么在每重复一次，就可以从字母和数字当中选一个， 那么这个呢就是一个重复项的这么一个扩展。
然后最后呢就是说为了便于区分这个单个符号的 终结符，有一些终结符它只有单个符号，那么这样呢它
再加上这个尖括号的话就也显得非常地长，那么它会
跟这个非终结符引起混淆的话，我们
会把这个终结符加上引号，比如说我们前面所定义的这个
十进制数，在定义小数的时候，它前面有一个点，
那这个点看着非常地不起眼，那我们为了强调，就给它加上引号。
比如说语句的序列 当中这个语句，分号，语句，分号，语句，这个分号 它是一个这个终结符。
那么我们会把它加上引号，以示强调它就是一个终结符。
那么但是有时候呢，如果印刷允许的话，我们也可以
用这个粗体字来表示这个终结符，那这样呢这个终结符呢就更加地明显。
而这样非终结符呢就可以不加尖括号了，那这样看起来呢整个的
这个BNF表达式看起来就会干净得多，可读性就会更好一些。
最后呢我们来看看，甚至呢可以用BNF来定义这个BNF。
我们说BNF呢它是一系列的规则，是吧？BNF
定义为规则，然后呢规则BNF，那么这是一个右递归，这是一个递归。
那么规则是什么呢？规则就是一系列的，一系列的这个规则就是左边是
非终结符，右边是一个表达式，中间呢用两个冒号加等号给它区分开。
然后非终结符呢，是什么呢？是单词加上一个一对尖括号，这就是非终结符。
那么单词是什么呢？就是一系列的这个字母。
或者说字母常，在后面再跟着一些字母。
这里引用了一个递归。
那么右边的 表达式是什么呢？表达式呢我们就是说它会根据一些项，
加竖杠，加上竖杠来变成了一个可选，就是或的这么一个 一个整个的表达式。
那项呢是若干个这个因子的 这个重复，所以呢我们也引用了一次这个递归
那么因子是什么？它就是一系列的这个单词， 是，它是一个单词，或者呢，因子也是一个 非终结符。
所以呢整个的项，就是一系列的单词，终结符， 非终结符混合在一起，这么一个 一个称之为因子的一个东西。
那这样呢，通过我们 这几个这个规则，我们就得到了用
实际上用BNF的手段定义了BMF自身。
Explorer notre catalogue
Rejoignez-nous gratuitement et obtenez des recommendations, des mises à jour et des offres personnalisées.
Coursera propose un accès universel à la meilleure formation au monde,
en partenariat avec des universités et des organisations du plus haut niveau, pour proposer des cours en ligne.
© 2018 Coursera Inc. Tous droits réservés.
