【编译原理系列】文法的定义

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

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

下面是文法的定义：

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

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

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

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

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

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

产生式的形式是α → β，α称为产生式左部，β称为产生式右部，α属于V_N，β∈(V_N∪V_T)*，α∉ε

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

a → b
b → c|d
c → e

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

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