编译原理2.3.2语法树及二义性

n n m m n m m n
为一先天二义性语言。 为一先天二义性语言。 • CFL的先天二义性也是不可判定的。 的先天二义性也是不可判定的。 的先天二义性也是不可判定的
2.3.3 短语和句柄
• 问题：在自底向上 问题： 的语法分析中， 的语法分析中，对 于每一步直接归约， 于每一步直接归约， 应如何正确地确定 当前句型中应被归 约的最左子串 约的最左子串? 最左子串 F i E T + T F i T * F i E
E(2) + T(2)
• 但是 对一句型而言，其直接短语可能不唯一。 但是,对一句型而言，其直接短语可能不唯一。 对一句型而言 为了让分析能够机械地进行，我们只考虑最左 为了让分析能够机械地进行，我们只考虑最左 归约。 归约。 E E T F i + T F i T * F i E + T F i
* +
归约时被替换子串的选择
• 从句型 η=E+T*F+i 的语法树可知 E+T 绝不是 的语法树可知, 它的一个直接短语 因为虽然 它的一个直接短语,因为虽然 E→E+T 是 G2[E] 直接短语 的一个产生式,但不存在从 的推导。 的一个产生式 但不存在从 E 到 E*F+i 的推导。 E E(1) E(2) + T(3) T(2) * F(3) + T(1) F(1) i
E + T F T * F i
i • 对一语法树而言，其构造过程不同对应了不 对一语法树而言， 同的推导（归约）过程。 同的推导（归约）过程。 推导
文法的二义性
• 存在这样的文法 ，其某个句子 w ∈ L(G) ， 存在这样的文法G， 可对应结构不同的语法树， 可对应结构不同的语法树，即 w 对应了多个 不同的最左（右）推导，这类文法称为二义 不同的最左* +

产生式 <名词 >∷= wolf | goat | rabbit | tiger
终结符
文法G : 一组非终结符 , 一组终结符 , 一个开始符号, 一组产生式
终结符
? 终结符是组成语言的基本符号 , 不可再分
割，不能由其它文法符号定义
? 词法规则 终结符是字母 , 数字, 其他合法符号
? 语法规则
<主语 >∷= <冠词 > [<形容词〉 ] < 名词>
<谓语 >∷= [<助动词 >] < 动词 > <冠词 > <名词 >
<名词 >∷= wolf | goat | rabbit | tiger
<冠词 >∷ = the |a |an <形容词 >∷= gray | red <助动词 >∷= will <动词> ∷= eat | like
文法和语言 2
(6) bE→be (7) eE→ee
L(G)=
｛anbnen|n≥1 ｝
例2.1
文法和语言 举例 p30
G1: S→bA, A→aA | a
L(G1)={ ba n | n≥1 }
例2.2 G2: S→AB,
A→aA | a,
B→bB | b
L(G2)={ a m b n | m, n≥1}
〈数字〉 →0
〈数字〉 →1
…
〈数字〉 →9}
S =〈标识符〉
补充例 文法 2
(c) 文法的写法
? VN – A, B, C… ,
<表达式 > ,<程序>
? VT – a, b, c,… ,

（3）若E为表达式，是一元运算符，则 E (或E )
也 是表达式；
(4) 若E为表达式,则 ( E )也是表达式。
二、语句
1、赋值句 2、控制语句
无条件转移语句 条件语句 循环语句 过程（或函数）调用语句 返回语句
3、说明句 4、简单句和复合句
§2.3 程序语言的语法描述
本节介绍高级语言语法结构的形式化描述问题
例题2.5
构造一个文法G4，使得
L(G4)={ ambn | m>n≧0 } 正解：文法G4: SAB Aa|aA BaBb|ε
上下文无关文法定义 归纳起来，一个上下文无关文法包括四个组成 部分： 一组终结符号 如：me ,book,gave 等 一组非终结符号 如：<主语>，<谓语> 等 一个开始符号 如: <句子> 一组产生式 如： <间接宾语> → <代词> <直接宾语> → <冠词> <名词>
上下文无关文法定义
形式上说，一个上下文无关文法G是一个四元式： G=（VT，VN，S，），其中： VT是一个非空有限集，它的每个元素为终结符号； VN是一个非空有限集，它的每个元素为非终结符号 且VT∩VN= Φ S 是一个非终结符号，称为开始符号； 是产生式有限集合，形如 A→α * 其中：A∈ VN， α∈(VT U VN) 。 注： 开始符号S是一个特殊的非终结符号，它至少 必须在某个产生式的左部出现一次。
语义规则 是指这样的一组规则，使用它可以定义一
个程序的意义。

描述语义规则的工具：
基于属性文法的语法制导下的翻译方法
2.1.3 程序
所谓程序，是描述一定数据的处理过程，即包括描述 数据和对数据的运算两个功能。

2.二义性文法：如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义性文法。

5.最左推导：任何一步α=>β都是对α中的最右非终结符替换。

6.语法：一组规则，用它可形成和产生一组合式的程序。

7.文法：描述语言的语法结构的形式规则。

8.基本块：指程序中一顺序执行的语句序列，其中只有一个入口和一个出口，入口就是其中的第一个语句，出口就是其中的最后一个语句。

10.短语：令G 是一个文法，S 划文法的开始符号，假定αβδ是文法G 的一个句型，如果有S αAδ且A β，则称β是句型αβδ相对非终结符A 的短语。

12.规范句型：由规范推导所得到的句型。

13.扫描器：执行词法分析的程序。

15.句柄：一个句型的最左直接短语。

16.语法制导翻译：在语法分析过程中，根据每个产生式所对应的语义程序进行翻译的方法 叫做语法制导翻译。

18.素短语：素短语是指这样一个短语，至少含有一个终结符，并且，除它自身外不再含任何更小的素短语。

20.语义：定义程序的意义的一组规则。

三种级别：局部优化、循环优化、全局优化21．词法分析词法分析的主要任务是从左向右扫描每行源程序的符号，按照词法规则从构成源程序的字符串中识别出一个个具有独立意义的最小语法单位，并转换成统一的内部表示(token)，送给语法分析程序。

23．语法树句子的树结构表示法称为语法树(语法分析树或语法推导树)。

给定文法G=(V N ，V T ，P ，S)，对于G 的任何句型都能构造与之关联的语法树。

这棵树具有下列特征：(1)根节点的标记是开始符号S 。

(2)每个节点的标记都是V 中的一个符号。

(3)若一棵子树的根节点为A ，且其所有直接子孙的标记从左向右的排列次序为A 1A 2…A R ，那么A →A 1A 2…A R 一定是P 中的一条产生式。

(4)若一标记为A 的节点至少有一个除它以外的子孙，则A ∈V N 。

(5)若树的所有叶节点上的标记从左到右排列为字符串w ，则w 是文法G 的句型；若w 中仅含终结符号，则w 为文法G 所产生的句子。