编译原理--文法定义（哈工大）
文法的定义讲解整理
一、文法引入：自然语言
下面我们来学习文法的定义。什么是文法？我们先从一个自然语言的例子讲起。这是一个简化版本的，用来描述英语句子构成规则的文法。从这个文法中我们可以看出，一个句子是由一个名词短语加上一个动词短语构成的。那么一个名词短语可以是由一个形容词加一个名词短语构成。还可以由一个名词构成。一个动词短语是由一个动词加上一个名词短语构成。形容词可以是 little，名词可以是 boy 或者 apple，动词可以是 eat。
二、文法核心组成要素的提取
从这个例子中，我们可以提取出一些文法的组成要素。在这个文法中出现的符号可以分为两类，这些用尖括号括起来的部分称为是语法成分，而未用尖括号括起来的部分表示语言的基本符号。因为这个文法是用来描述句子的构成规则的，那么句子的基本符号就是单词。如果一个文法是用来描述单词的构成规则的话，那么这个文法的基本符号就是字母。
三、文法的形式化定义（四元组）
那么根据这个例子，我们可以给出文法的形式化定义。文法我们用大写字母 G 来表示。我们把一个文法 G 定义成一个四元组。这里的这个 VT。VT 是终结符集合，V 表示向量 vector，T 表示终结符 terminal symbol。那么什么是终结符呢？终结符就是文法所定义的语言的基本符号。例如在刚才的这个例子中，这个文法是用来描述句子的组成规则的。那么句子的基本符号是单词，因此这些单词构成了这个文法的终结符集。终结符有时候也称为 token。这里的 VN 是非终结符集合，非终结符是用来表示语法成分的符号。
例如刚才这个文法中，用尖括号括起来的这些符号。由于可以从它们进一步推导出其他的语法成分，因此它们称为是非终结符。非终结符有时也称为是语法变量。
这里我们需要注意一下终结符集合和非终结符集合，它们是不相交的。终结符和非终结符统称为文法符号。因此，VT 并上 VN 表示的是文法符号集。文法中的这个 P，表示的是产生式的集合。产生式描述了将终结符和非终结符组合成串的方法。简而言之。产生式就是用来产生串的式子。产生式的一般形式是阿尔法α加一个箭头→，加上一个贝塔β，读作阿尔法α定义为贝塔β。从这两个式子我们可以看出，阿尔法α和贝塔β表示的是文法符号串。因为这个 VT 是终结符集合，它是一个字母表，VN 是非终结符集合，它也是一个字母表。那么这两个字母表的并集还是一个字母表。我们前面讲过。字母表的闭包表示的是这个字母表上的符号串构成的集合。因此，阿尔法α和贝塔β都是文法符号串。这里我们要求阿尔法α中至少要包含一个非终结符。阿尔法α也称为产生式的头或者左部，贝塔β称为产生式的体或者右部。
例如在刚才的这个文法中的每一条规则都是一个产生式。文法中的 S 表示的是文法的开始符号。S 是一个特殊的非终结符，它表示的是该文法中最大的语法成分。例如在刚才的这个例子中，这个文法是用来描述句子的构成规则，那么句子就是这个文法中最大的语法成分。因此这个就是这个文法的开始符号。
四、文法实例：算术表达式文法
下面我们来看一个文法的例子。这是一个简化版本的，用来表示算术表达式的文法。在这个文法中，终结符集合中包括了以下几个终结符，分别是 ID，也就是标识符，加号。乘号、左括号和右括号，这些都是最终出现在句子中的单词。因此它们构成了这个文法的终结符集合。这个文法的非终结符集合中只有一个非终结符。是 E，E 表示的是表达式，Expression。那么我们来看一下这个文法，它的产生式集合有 4 个产生式，分别是，E 定义为 E+E。E 定义为 E 乘 E，E 定义为括号 E，E 定义为 ID。由于这是一个用来描述表达式的文法，因此表达式是这个文法最大的语法成分，那么，E 就是这个文法的开始符号。而且这个文法中也没有其他的非终结符。我们这里约定，在不引起歧义的前提下，可以只写文法的产生式。例如这个文法我们可以简写为这种形式，就是只把它的产生式列出来，就可以表示这个文法。
五、产生式的简写规则
下面我们来看一下产生式的简写。对一组有相同左部的阿尔法产生式，阿尔法α定义为贝塔一
，阿尔法α定义为贝塔二，一直到阿尔法α定义为贝塔 N
。可以简记为阿尔法α定义为贝塔一
竖线、贝塔二
竖线，一直到竖线贝塔 N
。读作阿尔法定义为贝塔一
或者贝塔二
。或者一直到贝塔 N。那么贝塔 1 到贝塔 N
称为是阿尔法的候选式。例如，对于这些 E 产生式，我们就可以把它简写成，E 定义为 E+E 或 E×E 或括号 E，或 id。
六、文法符号的使用通用约定
为了避免总是声明哪些符号是终结符，哪些符号是非终结符。这里我们对符号的使用做一些约定。我们约定，下述符号是终结符。字母表中排在前面的小写字母，比如说 a b c 表示的是终结符。另外，运算符、标点符号和数字都是终结符。粗体的字符串，比如说 id if 等等，它们也是终结符。
我们约定，下述符号是非终结符。字母表中排在前面的大写字母，有大写的 A、B、C，它们表示的是非终结符。另外字母 S 通常用来表示文法的开始符号，因此它也是一个非终结符。小写斜体的名字，比如说 E S P R 用来表示表达式 Expression S T M T 用来表示句子 Statement。那么他们这些小写的斜体名字都表示非终结符，除了字母表中排在前面的大写字母以外，用来代表程序构造的一些大写字母。比如说 E、T、F 等等，也是非终结符。这里，E 表示的是表达式，expression。T 表示的是项，term。F 表示的是因子，factor。
我们约定字母表中排在后面的大写字母，比如说大写的 X、Y、Z，它表示的是文法符号。也就是说它既可以表示终结符，也可以表示非终结符。字母表中排在后面的小写字母主要是 u v w x y z 它们表示的是终结符号串。既然是串，就有可能是空串，因此这里包括空串。小写的希腊字母，比如说阿尔法、贝塔、伽马等等，它们表示的是文法符号串。既然是文法符号串，那么也包括空串。除非特别说明，第一个产生式的左部就是文法的开始符号。我们来总结一下，字母表中排在前面的小写字母用来表示终结符，字母表中排在前面的大写字母用来表示非终结符。字母表中排在后面的大写字母用来表示文法符号，文法符号既可以是终结符，也可以是非终结符。而字母表中排在后面的小写字母用来表示终结符号串。而小写的希腊字母用来表示文法符号串。