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