S S d c b A a d
A→ab|a
?句子cad是该文法定义语言的句子
当需要用A派生 时，无法根据输 入符号a唯一的 确定A的候选式
34
c a
A
2015-3-29
候选式的确定与回溯(Backtracking)

给定文法S→cABd A→ab|ε
S S c A B d ε
B→a
?句子cad是该文法定义语言的句子
C
E If a≠0 then if S
T S(非最长) C
E a>0 then S b=1 S else b=-1
三、重要问题——二义性及其消除
S→TS|CS C→if E then T →CS else
S
S
S T (最长) T (最长) C C S
C
C
if E then if E then S else if E then S else if E then S
发现不匹配,需 要回退(回溯)
S x A y
S xAy
x**y
匹配成功
2015-3-29
S
x A y
7
三、重要问题——回溯
x * * y
xAy x*y
发现不匹配,需要回退
S
S x A y
x * * y
S
xAy x**y
匹配成功
S
x A y
2015-3-29
8
三、重要问题——二义性及其消除
E → E + T｜ T T → T * F｜F F → ( E )｜id E→ T E’
E ’→ + T E ’| ε
T→ F T’ T’→* F T’｜ε F→ ( E )｜id
2015-3-29
21
例： 间接左递归的消除
S→Ac|c
A→Bb|b B→Sa|a 将B的定义代入A产生式得：A→Sab|ab|b 将A的定义代入S产生式得: S→Sabc|abc|bc|c 消除直接左递归： S→abcS’|bcS’|cS’ S’→abcS’|ε 删除“多余的”产生式：A→Sab|ab|b和 B→Sa|a 结果： S→abcS’|bcS’|cS’ 2015-3-29 S’→abcS’|ε

E→E+E|E-E|E*E|E/E|(E)|id 对 同 一 句 子存 在两棵语法分析树，哪个是对的？
E E
E
id
Байду номын сангаас
+ E
id
E
* E id
E E
id + E
*
E
id
2015-3-29
id
9
三、重要问题——二义性及其消除
二义性文法 E→E+E|E-E|E*E|E/E|(E)|id 非二义性文法 E→E+T|E-T|T T→T*F|T/F|F F→(E)|id 改造方法：引入语法变量，使文法含有更多的信息
当需要用A派生 时，因为A→ε 使得无法根据输 入符号a唯一的 确定A的候选式
35
c A B d a
2015-3-29
b
a
E→E+T|E-T|T|-E T→T*F|T/F|F F→F↑P|P P→(E)|id|const|FUN(L) FUN→ abs | sin | cos | ln | log | exp | sqrt L→E|E,L

VN＝{E,T,F,P,FUN,L｝ VT＝{id,const,+,-,*,/,(,), \,, abs,sin,cos,log,ln,exp,sqrt} S＝ E 2015-3-29 19
EE+E a1+E a1+E*E a1+a2*E a1+a2*a3

EE+E E+E*E E+E*a3 二义性(先天二义性语言、二义性文法) E+a2*a3 a1+a2*a3
2015-3-29 6
三、重要问题——虚假匹配
S xAy
输入串x**y
S→xAy A→**|* x*y
E
a>0 then
M
b=1 else
M
b=-1
按照“改造2”构造的语法树
S→TS|CS C→if E then T →CS else
C S
S T(最长)
C
E
If a≠0 then
E
if a>0 then
S
b=1
S
else b=-1
按照“改造2”构造的语法树
S→TS|CS C→if E then T →CS else
22
消除左递归的一般方法

对产生式组

A→Aα1|Aα2|…|Aαn|β1|β2|…|βm

用如下产生式组替换


Aβ1 B|β2 B |…|βm B Bα1 B|α2 B |…|αn B|ε 其中：B为新变量，相当于A’


消除左递归的算法见P70的算法
为非终结符编号，再采用代入法将间接左递归变 为直接左递归，消除直接左递归
11
一个句子有两棵不同的语法树
S S E E S If a≠0 then if a>0 then b=1 else S S E If a≠0 then if E S S a>0 then b=1 else b=-1 S b=-1
三、重要问题——二义性及其消除

1.重写文法
S→U|M U→if E then S U→if E then M else U M→if E then M else M|other S→TS|CS C→if E then T →CS else 2015-3-29
2015-3-29
10
三、重要问题——二义性及其消除
再例：If语句 S→if E then S S→if E then S else S S→other 设执行下列语句前b=0, If a≠0 then if a>0 then b=1 else b=-1 当a=1时,b=1;当a=-1时，执行后b=-1 If a≠0 then if a>0 then b=1 else b=-1 当a=1 时,b=1;当a=-1时，执行后b=0 2015-3-29
自动机识别语言

自顶向下
算符优先分析法
Bottom Up LR(0)、SLR(1)[LR(1)、LALR]
2015-3-29 4
自底向上
4.2 自顶向下分析面临的问题与CFG 的改造


一、自顶向下的分析 从文法的开始符号出发，寻求所给的输入符 号串的最左推导 从树根S开始，构造所给输入符号串的语法树 例：G为：S→xAy A→**|*，输入串：x**y
三、重要问题——左递归及其消除


无法根据左递归文法进行自顶向下的分析 A a1a2……ai……an 直接左递归

A Aα
当前变量
输入指针
(栈顶、最左变量)
间接左递归 A+Aα
左递归的消除方法
将A→Aα
2015-3-29
|β 替换为A→β A′ 和 A′→α A′｜ε
20
例：表达式文法直接左递归的消除
2015-3-29
32
候选式的确定与回溯(Backtracking)

给定文法S→cAd A→ab|e S c A e d 当需要用A派生时， 可以根据输入符号e唯 一的确定A的候选式
33
?句子ced是该文法定义语言的句子
2015-3-29
候选式的确定与回溯(Backtracking)

给定文法S→cAd
第 4章 自顶向下的语法分析 （ 1）
语法分析(Syntax Analysis) 文法的改造问题 自顶向下(Top Down)的分析 推导(Derivation)
2015-3-29 1
4.1 语法分析的任务

语法分析(Syntax Analysis)

检查扫描器输出的单词序列是否符合该语 言的文法(句子)，并分析组成此句子的语法 成分 Parser Syntax Analyzer
2015-3-29 24
三、重要问题——提取左因子
将形如
A→αβ1|αβ2|…|αβm |γ1|γ2|… | γp
的规则改写为
A→αA' |γ1|γ2|… | γp和 A'→β1|β2|…|βm

结果：
S→ if E then SS’|other S'→ε|else S

2015-3-29
S→TS|CS|other C→if E then T →CS else
E → T E’ E ’→ + T E ’｜ ε T → F T’ T’→ * F T’｜ε F → ( E )｜id
候选式的确定与回溯(Backtracking)

给定文法S→cAd A→ab|e S c a A b d 出现一次虚假的匹配， 并且立即发现cad不是 合法句子
?句子cad是该文法定义语言的句子


对于不同的文法，可用不同的分析方法

多用于编译的手工实现 多用于编译的自动生成
27

LR文法 ── LR分析法

2015-3-29
4.3 自顶向下的分析方法

基本思想

寻找输入符号串的最左推导 试图根据当前输入单词确定使用哪个产生式

基本过程

从S出发，构造输入符号串(Token)的最左派生 从根开始，按与最左推导相对应的顺序，构造 输入符号串(Token)的语法分析树