1、编译原理讲义(第二章 :文法与语言 )南京大学计算机系赵建华文法与语言 文法被用来精确而无歧义地描述语言的句子的构成方式 . 文法描述语言的时候不考虑语言的含义。字母表定义：字母表是有穷非空集合。 字母表包含了语言中所允许出现的一切符号。符号串 定义：符号串是由字母表中的符号所组成的有穷序列。 一个语言的句子总是它的字母表的符号串。这个符号串的组成必须是按照文法规则组合而成的。 语法分析的一个重要任务就是：判断一个符号串的组成是否满足某个文法的规定，并且分析出是如何按照规则组成的。关于符号串的概念和操作 运算： 联结 (并置 )： x=123, y=45那么 xy=12345 方幂： x的 n
2、次方幂即将 n个 x联结 。 子符号串： v是 xvy的子符号串。 v非空 头，尾： x是 xy的头， y是 xy的尾。符号串集合 定义：若集合 A中的一切元素都是 同一个字母表上 的集合，那么 A被称为 该字母表上的 符号串集合。 在本课程中，语言被认为是句子的集合。（外延定义？）所以，一个语言就是对应于它的字母表上的一个符号串集合。符号串集合的运算 乘积： AB = xy | xA且 y B 方幂： A的 n次方幂就是将 n个 A相乘。 字母表的闭包与正闭包： 字母表 A的闭包是 A上的所有符号串（包括空字符串）的集合。 字母表 A的正闭包是 A上的所有的非空符号串的集合。文法和语言的定义
3、（重写规则） 重写规则：一个重写规则是一个有序对(U,u)， 通常写作 U := u。 其中 U是一个符号，称为左部； u是一个符号串称为右部。有时也说这个规则是 U的一个规则。 重写规则总是基于某个字汇表的。 U和 u中的符号必须都在这个字汇表内。这个字汇表中有些符号不能作为左部。 存在更加复杂的规则，但是这样的规则足够描述程序设计语言的文法。文法和语言的定义（重写规则） 例如 : 标识符 := 字母 标识符 := 字母 |标识符字母 第二个规则实际使用了 BNF的表示方法。 BNF表示方法的还包括 : 花括号表示重复 : 字母 方括号表示可选 : 参数 文法和语言的定义（文法） 文法：文法 GZ是一组有穷非空的重写规则的集合。其中 Z称为识别符号。 G为文法名字 文法例子： P22, 例子 2.10。 所有的规则都是基于同一个符号表 V。 符号表又可分划非终结符号集合 VN和终结符号结合 VT。
