当我们要描述一种语言时,需要给出这种语言的所有句子,当句子的数目是有限可数时,就要都列出来;当句子是一个无穷集,也就是无限不可数时,就要给出可以表示它们的结构的描述方法或者说,句子的组成规则。这种规则就是文法

从形式上用于描述和规定结构的称为文法(或者说语法)

下面是文法的定义:

文法G定义为一个四元组(VN,VT,P,S),其中,VN为非终结符集合,VT终结符集合;P是产生式结合;S称为识别符或开始符号,也是一个非终结符,至少要在一条产生式的左边出现。

出现了几个名词,终结符、非终结符、产生式、识别符/开始符号等。下面具体聊聊这些名词和文法的定义。

VN是非终结符集合,非终结符N指的是可以被拆分的字符或串,它采取递归定义:一个非终结符是由终结符和至少一个非终结符组成的串,相对应的,终结符就是不可拆分的,语言中要用到的字符。所以VN中所存储的是所有的非终结符,VT中存储的是所有的终结符。

简单点讲:终结符就是推导到终结符时,不可再推导下去;而非终结符可以继续推导下去。

集合P存储的是所有的产生式。那什么是产生式呢?产生式就是推导规则。比方说 a→b 就是一条规则,即一条产生式,可以通过 a 推导出 b。

对照前面说的非终结符和终结符,就应该可以理解,在产生式左边的只能是非终结符,因为终结符不能再推导下去。而右边可以有终结符和非终结符。用数学的集合知识表示就是:

产生式的形式是α → β,α称为产生式左部,β称为产生式右部,α属于VN,β∈(VN∪VT)*,α∉ε

最后是S,S是开始符号,也就是最开始的那条产生式左边的非终结符,一切的推导从它开始。比方说

a → b
b → c|d
c → e

其中,a → b就是最开始的产生式,a就是最开始的非终结符,就是S。S是非终结符,所以S∈VN

以上就是编译原理中文法的定义以及相对应的没那么学术化的解释。


我的微信公众号
![](http://upload-images.jianshu.io/upload_images/3093748-7c07998b7495defc.jpg?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)