编译原理课件第8讲

温故知新上下文无关文法自上而下自下而上LL(1)文法2个函数递归下降预测分析非递归的预测分析最左推导最右推导？E

TEE

+TE|T

FTT

*FT

|F

(E)|id输入：id*idETE

id*T

FidFT

Elm

TE’lm

FT’E’lm

idT’E’

lmid*FT’E’

lmid*idT’E’lmid*idE’lmid*id1/75温故知新E

TEE

+TE|T

FTT

*FT

|F

(E)|id输入：id*idETE

id*T

FidFT

Erm

TE’rmTrm

FT’

rmF*FT’

rmF*FrmF*idrmid*id从左至右读取输入字符串，却要进行最右推导。这样利用左边的字符来决定右边的非终结符的展开方式，非常困难。因此，最右推导不适合使用自上而下的方式构造分析树。温故知新上下文无关文法自上而下自下而上LL(1)文法2个函数递归下降预测分析非递归的预测分析最左推导最右推导！3.4

自下而上分析3.4.1

归约：自下而上分析的例子例 S

aABe

A

Abc|b B

dabcdBSeAAbabbcdeaAbcdeaAdeaABeSSrmaABermaAdermaAbcdermabbcde输入：abbcde3.4

自下而上分析3.4.2

句柄 句型的句柄是和某产生式右部匹配的子串，并且，把它归约成该产生式左部的非终结符代表了最右推导过程的逆过程的一步。

S

aABe

A

Abc|b B

dSrmaABe

rmaAdermaAbcdermabbcde句柄与某个产生式的右部符号串相同句柄是句型的一个子串把句柄归约成非终结符代表了最右推导逆过程的一步5/753.4

自下而上分析3.4.2

句柄句柄性质：SrmaABe

rmaAdermaAbcdermabbcde句柄的右边仅含终结符。如果文法二义，那么句柄可能不唯一。例 EE+E|E*E|(E)|idErmE*E E

rmE+ErmE*

E+E rmE+id3rmE*E+id3 rmE*E

+id3rmE*

id2+id3

rmE*

id2+id3

rm

id1

*id2+id3

rm

id1

*id2+id3

在句型E*E+id3中，句柄不唯一。3.4

自下而上分析3.4.3用栈实现移进归约分析分析器的四种动作：移进动作把下一个输入符号压栈。规约动作分析器知道整个句柄已经完全出现在栈顶，它确定句柄的左端在栈中的位置，在决定采用哪个非终结符来代替句柄（即确定使用哪个产生式）。接受动作分析器宣告分析成功。报错动作分析器发现了语法错误，调用错误恢复例程。a+b$输入移进-归约分析程序分析表M输出XYZ$栈3.4

自下而上分析3.4.3用栈实现移进归约分析通过

移进归约分析器在分析输入串id1

*id2+id3时的动作序列来了解移进归约分析的工作方式。3.4

自下而上分析栈

输

入

动

作

$id1

*id2+id3$

3.4

自下而上分析栈

输

入

动

作

$id1

*id2+id3$移进

10/753.4

自下而上分析栈

输

入

动

作

$id1

*id2+id3$移进

$id1

*

id2+id3$

3.4

自下而上分析栈

输

入

动

作

$id1

*id2+id3$移进

$id1

*

id2+id3$按E

id归约

3.4

自下而上分析栈

输

入

动

作

$id1

*id2+id3$移进

$id1

*

id2+id3$按E

id归约

$E

*

id2+id3$

3.4

自下而上分析栈

输

入

动

作

$id1

*id2+id3$移进

$id1

*

id2+id3$按E

id归约

$E

*

id2+id3$移进

3.4

自下而上分析栈

输

入

动

作

$id1

*id2+id3$移进

$id1

*

id2+id3$按E

id归约

$E

*

id2+id3$移进

$E*

id2+id3$

15/753.4

自下而上分析栈

输

入

动

作

$id1

*id2+id3$移进

$id1

*

id2+id3$按E

id归约

$E

*

id2+id3$移进

$E*

id2+id3$移进

3.4

自下而上分析栈

输

入

动

作

$id1

*id2+id3$移进

$id1

*

id2+id3$按E

id归约

$E

*

id2+id3$移进

$E*

id2+id3$移进

$E*id2

+id3$

3.4

自下而上分析栈

输

入

动

作

$id1

*id2+id3$移进

$id1

*

id2+id3$按E

id归约

$E

*

id2+id3$移进

$E*

id2+id3$移进

$E*id2

+id3$按E

id归约

3.4

自下而上分析栈

输

入

动

作

$id1

*id2+id3$移进

$id1

*

id2+id3$按E

id归约

$E

*

id2+id3$移进

$E*

id2+id3$移进

$E*id2

+id3$按E

id归约

$E*E

+id3$

3.4

自下而上分析栈

输

入

动

作

$id1

*id2+id3$移进

$id1

*

id2+id3$按E

id归约

$E

*

id2+id3$移进

$E*

id2+id3$移进

$E*id2

+id3$按E

id归约

$E*E

+id3$移进

20/753.4

自下而上分析栈

输

入

动

作

$id1

*id2+id3$移进

$id1

*

id2+id3$按E

id归约

$E

*

id2+id3$移进

$E*

id2+id3$移进

$E*id2

+id3$按E

id归约

$E*E

+id3$移进

$E*E+id3$

3.4

自下而上分析栈

输

入

动

作

$id1

*id2+id3$移进

$id1

*

id2+id3$按E

id归约

$E

*

id2+id3$移进

$E*

id2+id3$移进

$E*id2

+id3$按E

id归约

$E*E

+id3$移进

$E*E+id3$移进

3.4

自下而上分析栈

输

入

动

作

$id1

*id2+id3$移进

$id1

*

id2+id3$按E

id归约

$E

*

id2+id3$移进

$E*

id2+id3$移进

$E*id2

+id3$按E

id归约

$E*E

+id3$移进

$E*E+id3$移进

$E*E+id3

$

3.4

自下而上分析栈

输

入

动

作

$id1

*id2+id3$移进

$id1

*

id2+id3$按E

id归约

$E

*

id2+id3$移进

$E*

id2+id3$移进

$E*id2

+id3$按E

id归约

$E*E

+id3$移进

$E*E+id3$移进

$E*E+id3

$按E

id归约

3.4

自下而上分析栈

输

入

动

作

$id1

*id2+id3$移进

$id1

*

id2+id3$按E

id归约

$E

*

id2+id3$移进

$E*

id2+id3$移进

$E*id2

+id3$按E

id归约

$E*E

+id3$移进

$E*E+id3$移进

$E*E+id3

$按E

id归约

$E*E+E

$

25/753.4

自下而上分析栈

输

入

动

作

$id1

*id2+id3$移进

$id1

*

id2+id3$按E

id归约

$E

*

id2+id3$移进

$E*

id2+id3$移进

$E*id2

+id3$按E

id归约

$E*E

+id3$移进

$E*E+id3$移进

$E*E+id3

$按E

id归约

$E*E+E

$按E

E+E归约

3.4

自下而上分析栈

输

入

动

作

$id1

*id2+id3$移进

$id1

*

id2+id3$按E

id归约

$E

*

id2+id3$移进

$E*

id2+id3$移进

$E*id2

+id3$按E

id归约

$E*E

+id3$移进

$E*E+id3$移进

$E*E+id3

$按E

id归约

$E*E+E

$按E

E+E归约

$E*E

$

3.4

自下而上分析栈

输

入

动

作

$id1

*id2+id3$移进

$id1

*

id2+id3$按E

id归约

$E

*

id2+id3$移进

$E*

id2+id3$移进

$E*id2

+id3$按E

id归约

$E*E

+id3$移进

$E*E+id3$移进

$E*E+id3

$按E

id归约

$E*E+E

$按E

E+E归约

$E*E

$按E

E*E归约

3.4

自下而上分析栈

输

入

动

作

$id1

*id2+id3$移进

$id1

*

id2+id3$按E

id归约

$E

*

id2+id3$移进

$E*

id2+id3$移进

$E*id2

+id3$按E

id归约

$E*E

+id3$移进

$E*E+id3$移进

$E*E+id3

$按E

id归约

$E*E+E

$按E

E+E归约

$E*E

$按E

E*E归约

$E

$

3.4

自下而上分析栈

输

入

动

作

$id1

*id2+id3$移进

$id1

*

id2+id3$按E

id归约

$E

*

id2+id3$移进

$E*

id2+id3$移进

$E*id2

+id3$按E

id归约

$E*E

+id3$移进

$E*E+id3$移进

$E*E+id3

$按E

id归约

$E*E+E

$按E

E+E归约

$E*E

$按E

E*E归约

$E

$接受

30/753.4

自下而上分析使用移进归约方式，即使知道了应该进行归约，也还有两个问题必须解决确定右句型中将要归约的子串如何确定选择哪一个产生式3.4

自下而上分析3.4.4

移进归约分析的冲突

移进归约冲突例 stmt

ifexprthenstmt |ifexprthenstmtelsestmt|other 如果移进归约分析器处于格局 栈

输入 …ifexprthenstmt else…$

3.4

自下而上分析归约归约冲突stmtid(parameter_list)|expr:=exprparameter_list

parameter_list,parameter|parameterparameter

idexpr

id(expr_list)|idexpr_list

expr_list,expr|expr由A(I,J)开始的语句 栈 输入 …id(id ,id)…3.4

自下而上分析归约归约冲突的解决stmtprocid(parameter_list)|expr:=exprparameter_list

parameter_list,parameter|parameterparameter

idexpr

id(expr_list)|idexpr_list

expr_list,expr|expr由A(I,J)开始的语句 栈 输入 …procid(id ,id)…3.5

LR分析器本节介绍LR(k)分析技术特点适用于一大类上下文无关文法效率高主要介绍构造LR分析表的三种技术简单的LR方法（简称SLR）规范的LR方法向前看的LR方法（简称LALR）

35/753.5

LR分析器3.5.1

LR分析算法输入LR分析程序输出栈LR分析器的模型actiongotosmXmsm-1Xm-1…s0…a1ai…an$3.5

LR分析器例E

E+T|T T

T*F|

F F(E)|id状态动

作

转

移

id

+*()$

E

TF

0s5s41231s6acc

2

r2s7r2r23r4r4r4r44s5s4

8233.5

LR分析器栈

输

入

动

作

0id*id+id

$

3.5

LR分析器栈

输

入

动

作

0id*id+id

$移进

3.5

LR分析器栈

输

入

动

作

0id*id+id

$移进

0id5

*

id+id

$

40/753.5

LR分析器栈

输

入

动

作

0id*id+id

$移进

0id5

*

id+id

$按F

id归约

3.5

LR分析器栈

输

入

动

作

0id*id+id

$移进

0id5

*

id+id

$按F

id归约

0F3*

id+id

$

3.5

LR分析器栈

输

入

动

作

0id*id+id

$移进

0id5

*

id+id

$按F

id归约

0F3*

id+id

$按T

F归约

3.5

LR分析器栈

输

入

动

作

0id*id+id

$移进

0id5

*

id+id

$按F

id归约

0F3*

id+id

$按T

F归约

0T2*

id+id

$

3.5

LR分析器栈

输

入

动

作

0id*id+id

$移进

0id5

*

id+id

$按F

id归约

0F3*

id+id

$按T

F归约

0T2*

id+id

$移进

45/753.5

LR分析器栈

输

入

动

作

0id*id+id

$移进

0id5

*

id+id

$按F

id归约

0F3*

id+id

$按T

F归约

0T2*

id+id

$移进

0T2*7id+id$

3.5

LR分析器栈

输

入

动

作

0id*id+id

$移进

0id5

*

id+id

$按F

id归约

0F3*

id+id

$按T

F归约

0T2*

id+id

$移进

0T2*7id+id$移进

3.5

LR分析器栈

输

入

动

作

0id*id+id

$移进

0id5

*

id+id

$按F

id归约

0F3*

id+id

$按T

F归约

0T2*

id+id

$移进

0T2*7id+id$移进

0T2*7id5+id$

3.5

LR分析器栈

输

入

动

作

0id*id+id

$移进

0id5

*

id+id

$按F

id归约

0F3*

id+id

$按T

F归约

0T2*

id+id

$移进

0T2*7id+id$移进

0T2*7id5+id$按F

id归约

3.5

LR分析器栈

输

入

动

作

0id*id+id

$移进

0id5

*

id+id

$按F

id归约

0F3*

id+id

$按T

F归约

0T2*

id+id

$移进

0T2*7id+id$移进

0T2*7id5+id$按F

id归约

0T2*7F10+id$

50/753.5

LR分析器栈

输

入

动

作

0id*id+id

$移进

0id5

*

id+id

$按F

id归约

0F3*

id+id

$按T

F归约

0T2*

id+id

$移进

0T2*7id+id$移进

0T2*7id5+id$按F

id归约

0T2*7F10+id$按T

T*F归约

3.5

LR分析器栈

输

入

动

作

0id*id+id

$移进

0id5

*

id+id

$按F

id归约

0F3*

id+id

$按T

F归约

0T2*

id+id

$移进

0T2*7id+id$移进

0T2*7id5+id$按F

id归约

0T2*7F10+id$按T

T*F归约

.........

3.5

LR分析器栈

输

入

动

作

0id*id+id

$移进

0id5

*

id+id

$按F

id归约

0F3*

id+id

$按T

F归约

0T2*

id+id

$移进

0T2*7id+id$移进

0T2*7id5+id$按F

id归约

0T2*7F10+id$按T

T*F归约

.........0E1$

3.5

LR分析器栈

输

入

动

作

0id*id+id

$移进

0id5

*

id+id

$按F

id归约

0F3*

id+id

$按T

F归约

0T2*

id+id

$移进

0T2*7id+id$移进

0T2*7id5+id$按F

id归约

0T2*7F10+id$按T

T*F归约

.........0E1$接受

3.5

LR分析器3.5.2LR文法和LR分析方法的特点概念 活前缀：右句型的前缀，该前缀不超过最右句柄的右端

S

*rmAw

rm

w

的任何前缀（包括和

本身）都是一个活前缀。一个符号串的前缀是指从第一个符号开始的连续的若干个符号构成的子串。55/753.5

LR分析器3.5.2LR文法和LR分析方法的特点概念 活前缀：右句型的前缀，该前缀不超过最右句柄的右端定义

LR文法：我们能为之构造出所有条目都唯一的LR分析表3.5

LR分析器LR分析方法的特点栈中的文法符号总是形成一个活前缀。3.5

LR分析器栈

输

入

动

作

0id*id+id

$移进

0id5

*

id+id

$按F

id归约

0F3*

id+id

$按T

F归约

0T2*

id+id

$移进

0T2*7id+id$移进

0T2*7id5+id$按F

id归约

0T2*7F10+id$按T

T*F归约

.........0E1$接受

3.5

LR分析器LR分析方法的特点栈中的文法符号总是形成一个活前缀。分析表的转移函数本质上是识别活前缀的DFA。3.5

LR分析器例E

E+T|E

T T

T*F|

T

E F(E)|Fid状态动

作

转

移

id

+*()$

E

TF

0s5s41231s6acc

2

r2s7