编译原理讲义第二章文法与语言.ppt

• 注意：在寻找一个句型的短语（或简单 短语）时，必须要求将这个短语规约为 相应的非终结符号后所得到的符号串仍 然是句型。
• 句柄：一个句型的最左简单短语称为该 句型的句柄。
• 定义句柄的原因：在自底向上识别一个 符号串时，总是规约这个句柄。
语言的定义（文法的语言）
• 文法的语言：一个文法G[Z]的语言，用 L(G[Z])表示，定义如下：
文法和语言的定义（推导）
• 直接推导：，，并且是文法中的一个重 写规则，那么我们说v可以直接推导到w， 或者w可以直接规约到v。记作 v => w。
• 例如： • 〈主语〉〈谓语〉〈状语〉 • =>〈名词〉〈谓语〉〈状语〉
文法和语言的定义（推导）
• 推导：对于符号串v和w，如果存在一个 直接推导序列u0=>u1=>…=>，并且u0，， 那么我们说v可以推导到w，或者w规约 到v。记作v =>+ w。
编译原理讲义 (章:文法与语言)
文法与语言
• 文法被用来精确而无歧义地描述语言的 句子的构成方式.
• 文法描述语言的时候不考虑语言的含义。
字母表
定义：字母表是有穷非空集合。
字母表包含了语言中所允许出现的一切符 号。
符号串
• 定义：符号串是由字母表中的符号所组 成的有穷序列。
• 一个语言的句子总是它的字母表的符号 串。这个符号串的组成必须是按照文法 规则组合而成的。
符号串集合
• 定义：若集合A中的一切元素都是同一个 字母表上的集合，那么A被称为该字母表 上的符号串集合。
• 在本课程中，语言被认为是句子的集合。 （外延定义？）所以，一个语言就是对 应于它的字母表上的一个符号串集合。
符号串集合的运算
• 乘积： = { | x A且y B} • 方幂：A的n次方幂就是将n个A相乘。 • 字母表的闭包与正闭包： • 字母表A的闭包是A上的所有符号串（包
括空字符串）的集合。 • 字母表A的正闭包是A上的所有的非空符
号串的集合。
文法和语言的定义（重写规则）
• 重写规则：一个重写规则是一个有序对()， 通常写作 U u。其中U是一个符号， 称为左部；u是一个符号串称为右部。有 时也说这个规则是U的一个规则。
• 重写规则总是基于某个字汇表的。U和u 中的符号必须都在这个字汇表内。这个 字汇表中有些符号不能作为左部。
文法和语言的定义（推导）
• 文法的作用是描述某种语言的句子的构 成方式。使用文法我们可以产生对应语 言的句子。
• 从识别符号开始，不断将当前符号串中 的非终结符号替换为该符号的某个规则 的右部。直到当前的符号串中所有的符 号都是终结符号为止。
文法和语言的定义（推导）
• 例子： • 〈句子〉=>〈主语〉〈谓语〉〈状语〉 • =>〈名词〉〈谓语〉〈状语〉 • => …… • =>
• 这个推导长度为n，且称w为对应于v的一 个字。
• >* w 表示或者v =>+ w。
文法和语言的定义（推导）
• 推导的例子：P25页例2.12。 • 文法： • <标号><数字序列> • <数字序列><数字序列><数字> | <数字> • <数字> 0 | 1 | 2 | 3 | … | 9 • {0,1,2,3,4,5,6,7,8,9}, = {}
• L(G[Z]) = {x | >* x 并且 x } • 一个文法的语言就是该文法的所有的句子的
集合。 • 文法的语言是所有终结符号串所组成的集合
的子集，一般是真子集。
语言的定义（递归与语言）
• 递归的规则：U …U… • 左右递归规则：U U…；U …U • 文法的递归：U =>+ …U…，称文法递归
的句型。
语言的定义（短语，简单短语）
• 短语：对于文法G[Z]，如果Z =>* ，>+ u。 显然，是一个句型。我们称u是句型w中 相对于U的短语。
• 简单短语：在上面的定义中，如果U u是 G的一个规则，那么，u是句型w中相对 于U的简单短语。
• 例子：P22页例2.13。
语言的定义（短语，句柄）
于U。 • 文法的左右递归： • 如果文法是非递归的，那么其语言是有
穷的。
文法与语言（例子）
• G[A]：； • L(G[A])={>=0} • G[Z]：； • L(G[Z]) = {a2>=1}
语言的分类
• 文法的定义：
• () • 该定义是我们前面讲的定义的一个更加
形式化的表达。
• 在这个定义中，文法规则的左部可以是 一个非空符号串。
推导的例子
<标号>
=> <数字序列> => <数字序列><数字> =><数字序列><数字><数字> => <数字><数字><数字> => <数字>23
=> 123语言的Fra bibliotek义（句型,句子）
• 对于文法G[Z]，x称为G的一个句型如果： • Z =>* x • 识别符号是最简单的句型。 • G[Z]的一个句型x被称为句子，如果： •x * • 也就是说句子是全部由终结符号组成
• 存在更加复杂的规则，但是这样的规则 足够描述程序设计语言的文法。
文法和语言的定义（重写规则）
• 例如: • 〈标识符〉 〈字母〉 • 〈标识符〉 〈字母〉|〈标识符〉〈字母〉 • 第二个规则实际使用了的表示方法。表
示方法的还包括: • 花括号表示重复: {〈字母〉} • 方括号表示可选: [〈参数〉]
• 语法分析的一个重要任务就是：判断一 个符号串的组成是否满足某个文法的规 定，并且分析出是如何按照规则组成的。
关于符号串的概念和操作
• 运算： • 联结(并置)：123, 45那么12345 • 方幂：x的n次方幂即将n个x联结。 • 子符号串：v是的子符号串。v非空 • 头，尾：x是的头，y是的尾。
• 文法被分为四类，我们主要用2型和3型 文法。
文法和语言的定义（文法）
• 文法：文法G[Z]是一组有穷非空的重写 规则的集合。其中Z称为识别符号。G为 文法名字
• 文法例子：P22, 例子2.10。 • 所有的规则都是基于同一个符号表V。符
号表又可分划非终结符号集合和终结符 号结合。
• 〈句子〉 <主语><谓语><状语> • <主语><名词> • <名词> | | • <谓语><动词> • <动词> • <介词> • <状语> <介词> <名词>