文法的定义讲解整理一、文法引入自然语言下面我们来学习文法的定义。什么是文法我们先从一个自然语言的例子讲起。这是一个简化版本的用来描述英语句子构成规则的文法。从这个文法中我们可以看出一个句子是由一个名词短语加上一个动词短语构成的。那么一个名词短语可以是由一个形容词加一个名词短语构成。还可以由一个名词构成。一个动词短语是由一个动词加上一个名词短语构成。形容词可以是 little名词可以是 boy 或者 apple动词可以是 eat。二、文法核心组成要素的提取从这个例子中我们可以提取出一些文法的组成要素。在这个文法中出现的符号可以分为两类这些用尖括号括起来的部分称为是语法成分而未用尖括号括起来的部分表示语言的基本符号。因为这个文法是用来描述句子的构成规则的那么句子的基本符号就是单词。如果一个文法是用来描述单词的构成规则的话那么这个文法的基本符号就是字母。三、文法的形式化定义四元组那么根据这个例子我们可以给出文法的形式化定义。文法我们用大写字母 G 来表示。我们把一个文法 G 定义成一个四元组。这里的这个 VT。VT 是终结符集合V 表示向量 vectorT 表示终结符 terminal symbol。那么什么是终结符呢终结符就是文法所定义的语言的基本符号。例如在刚才的这个例子中这个文法是用来描述句子的组成规则的。那么句子的基本符号是单词因此这些单词构成了这个文法的终结符集。终结符有时候也称为 token。这里的 VN 是非终结符集合非终结符是用来表示语法成分的符号。例如刚才这个文法中用尖括号括起来的这些符号。由于可以从它们进一步推导出其他的语法成分因此它们称为是非终结符。非终结符有时也称为是语法变量。这里我们需要注意一下终结符集合和非终结符集合它们是不相交的。终结符和非终结符统称为文法符号。因此VT 并上 VN 表示的是文法符号集。文法中的这个 P表示的是产生式的集合。产生式描述了将终结符和非终结符组合成串的方法。简而言之。产生式就是用来产生串的式子。产生式的一般形式是阿尔法α加一个箭头→加上一个贝塔β读作阿尔法α定义为贝塔β。从这两个式子我们可以看出阿尔法α和贝塔β表示的是文法符号串。因为这个 VT 是终结符集合它是一个字母表VN 是非终结符集合它也是一个字母表。那么这两个字母表的并集还是一个字母表。我们前面讲过。字母表的闭包表示的是这个字母表上的符号串构成的集合。因此阿尔法α和贝塔β都是文法符号串。这里我们要求阿尔法α中至少要包含一个非终结符。阿尔法α也称为产生式的头或者左部贝塔β称为产生式的体或者右部。例如在刚才的这个文法中的每一条规则都是一个产生式。文法中的 S 表示的是文法的开始符号。S 是一个特殊的非终结符它表示的是该文法中最大的语法成分。例如在刚才的这个例子中这个文法是用来描述句子的构成规则那么句子就是这个文法中最大的语法成分。因此这个就是这个文法的开始符号。四、文法实例算术表达式文法下面我们来看一个文法的例子。这是一个简化版本的用来表示算术表达式的文法。在这个文法中终结符集合中包括了以下几个终结符分别是 ID也就是标识符加号。乘号、左括号和右括号这些都是最终出现在句子中的单词。因此它们构成了这个文法的终结符集合。这个文法的非终结符集合中只有一个非终结符。是 EE 表示的是表达式Expression。那么我们来看一下这个文法它的产生式集合有 4 个产生式分别是E 定义为 EE。E 定义为 E 乘 EE 定义为括号 EE 定义为 ID。由于这是一个用来描述表达式的文法因此表达式是这个文法最大的语法成分那么E 就是这个文法的开始符号。而且这个文法中也没有其他的非终结符。我们这里约定在不引起歧义的前提下可以只写文法的产生式。例如这个文法我们可以简写为这种形式就是只把它的产生式列出来就可以表示这个文法。五、产生式的简写规则下面我们来看一下产生式的简写。对一组有相同左部的阿尔法产生式阿尔法α定义为贝塔一阿尔法α定义为贝塔二一直到阿尔法α定义为贝塔 N。可以简记为阿尔法α定义为贝塔一竖线、贝塔二竖线一直到竖线贝塔 N。读作阿尔法定义为贝塔一或者贝塔二。或者一直到贝塔 N。那么贝塔 1 到贝塔 N称为是阿尔法的候选式。例如对于这些 E 产生式我们就可以把它简写成E 定义为 EE 或 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 它们表示的是终结符号串。既然是串就有可能是空串因此这里包括空串。小写的希腊字母比如说阿尔法、贝塔、伽马等等它们表示的是文法符号串。既然是文法符号串那么也包括空串。除非特别说明第一个产生式的左部就是文法的开始符号。我们来总结一下字母表中排在前面的小写字母用来表示终结符字母表中排在前面的大写字母用来表示非终结符。字母表中排在后面的大写字母用来表示文法符号文法符号既可以是终结符也可以是非终结符。而字母表中排在后面的小写字母用来表示终结符号串。而小写的希腊字母用来表示文法符号串。