编译原理
19
二义性的影响
不同的分析树对应不同的赋值。 对程序来讲，其含义会产生二义性。
2018/10/6
编译原理
20
消除二义性
通常可以通过增加非终结符，或者只允许左递归/右 递归的方式来消除二义性。
T非终结符强迫了优先级 左递归：左结合
2018/10/6
编译原理
21
2018/10/6
编译原理
22
语法分析——上下文无关文法
授课：胡静
目录
复习内容
上下文无关文法（CFGs） 推导 语法分析树和抽象语法 二义性文法
属性文法 YACC
2018/10/6
编译原理
2
语法分析器所处的位置
2018/10/6
编译原理
3
语法分析的例子
2018/10/6
编译原理
4
语法分析总述
达到的目标：确定输入的token流是否符合程序的语 法，如果符合的话，要识别出其结构。 语法分析需要如下条件：
V是非终结符的有限集合 Σ是终结符的有限集合 S ∈ V 是一个特殊的非终结符，叫做开始符号 →⊆ V × (V ∪ Σ)* 是一个有限关系，叫做产生式。
上下文无关文法简写为 CFG
2018/10/6
编,Σ,S,→>，是一个上下文无关文法，“直接的推 导”关系 (⇒) 定义为 { <αAγ, αβγ> | A→β }. 例如：
T→F F→(E) F→digit
T.val := T1.val * F.val
T.val := F.val F.val := E.val F.val := digit.lexval
2018年10月6日
编译原理
24
翻译模式
翻译模式给出了使用语义规则进行计算的次序，这 样就可以把某些细节表示出来。 在翻译模式中，和文法符号相关的属性和语义规则 （这里也称语义动作），用“{}”括起来，插入到产 生式右部合适的位置上。 翻译模式给出了使用语义规则进行计算的顺序。
2018/10/6 编译原理 9
举例
设有文法G，其产生式是S → aSbS | ε 那么
S ⇒ aSbS ⇒ aaSbSbS ⇒ aabSbS ⇒ aabbS ⇒ aabbaSbS ⇒aabbabS ⇒ aabbab
也就是说，属于L(G)
2018/10/6
编译原理
10
文法和接受器
上下文无关文法的接受器如下：
正则表达式没有足够的描述能力来描述程序语言的语 法。
例如：嵌套的等价结构
比如括号嵌套 { (), ()(), (()), (())(), ()(()), (())(()), ((())(())), etc. }
2018/10/6 编译原理 6
上下文无关文法
上下文无关文法是一个四元组表示形式 <V,Σ,S,→>
对语法进行描述的方法 一个接受器的机制，来确定输入的token流是否符合 语法描述。 能够还原语法结构的方法。
2018/10/6
编译原理
5
为什么不能用正则表达式
正则表达式可以对token进行表示
用正则表达式对token进行描述，而后可以很方便有 效的执行（使用DFA）
不能够使用正则表达式来描述程序语言的语法：
设G的文法的产生式是 S → aSbS | ε 那么
S ⇒ aSbS aSbS ⇒ aaSbSbS aaSbSbS ⇒ aabSbS aabSbS ⇒ aabbS aabbS ⇒ aabbaSbS aabbaSbS ⇒ aabbabS aabbabS ⇒ aabbab
2018/10/6 编译原理 8
目录
复习内容
上下文无关文法（CFGs） 推导 语法分析树和抽象语法 二义性文法
属性文法 YACC
2018/10/6
编译原理
23
属性文法举例
产生式 L→En E→E1 + T E→T
语义规则 print(E.val) E.val := E1.val + T.val E.val := T.val
T→T1 * F
2018/10/6
编译原理
12
求和的文法
文法：
S→E+S|E E → number | ( S )
Expanded:
可接受的输入的例子：
(1+2+(3+4))+5
2018/10/6 编译原理 13
推导的例子
2018/10/6
编译原理
14
推导和分析树
语法树：描述推导过程 的树形结构 树的叶子是终结符 中间结点是非终结符 不能够描述推导步骤的 顺序。
语法分析器 = CFG接受器，当token流被接受时，输 出相应的推导 例子： LL(k), LR(k), SLR, LALR
2018/10/6 编译原理 11
每个正则语言都是CFL
为每个RE归纳的建立一个CFG
ε a R1R2 R1 | R 2 R1 * S→ε S→a S → S1S2 S → S1 | S 2 S → S1 S | ε
二义性文法：不同的推导产生不同的分析树。
考虑表达式1 + 2 * 3 推导1: S ⇒ S + S ⇒1 + S ⇒1 + S * S ⇒1 + 2 * S ⇒ 1 + 2 * 3 推导2: S ⇒S * S ⇒ S * 3 ⇒S + S * 3 ⇒S + 2 * 3 ⇒1 + 2 * 3
2018/10/6
E+S⇒1+S
最右推导：总是替换最右边的非终结符
E+S⇒E+E+S
2018/10/6
编译原理
17
例子
S→E+S|E E → number | ( S ) 最左推导
最右推导
相同的分析树：选择的相同的产生式，只是顺序不同。
2018/10/6 编译原理 18
二义性文法
考虑另一个文法
S → S + S | S * S | number
2018/10/6
编译原理
15
分析树和抽象语法树（AST）
分析树也叫做具体语法树
2018/10/6
编译原理
16
推导顺序
可以选择任意顺序来使用产生式；选择任意一个非 终结符A，比如：αAγ ⇒ αβγ 两个标准的顺序：最左推导和最右推导——使用在 不同类的自动语法分析当中。 最左推导：总是替换最左边的非终结符
上下文无关语言
设G = <V,Σ,S,→>是CFG，由G所产生的语言表示为 L(G)， L(G) = { x | S ⇒* x } L(G) = 从开始符号开始，将产生式作为规则改写的 手段，重复的使用，最后得到的终结符号串的集合， 叫做L(G)。 上下文无关语言(CFLs)是由上下文无关文法产生的语 言。 如果x ∈ L(G)，那么x的推导是一个字符串序列 S=α0 , α1 , ... , αn=x, 其中每一个αi ⇒ αi+1 当0≤i<n。我们写 作α0⇒α1 ... ⇒ αn。