溫故知新上下文無關(guān)文法自上而下自下而上LL(1)文法2個(gè)函數(shù)遞歸下降預(yù)測分析非遞歸的預(yù)測分析最左推導(dǎo)最右推導(dǎo)？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從左至右讀取輸入字符串，卻要進(jìn)行最右推導(dǎo)。這樣利用左邊的字符來決定右邊的非終結(jié)符的展開方式，非常困難。因此，最右推導(dǎo)不適合使用自上而下的方式構(gòu)造分析樹。溫故知新上下文無關(guān)文法自上而下自下而上LL(1)文法2個(gè)函數(shù)遞歸下降預(yù)測分析非遞歸的預(yù)測分析最左推導(dǎo)最右推導(dǎo)！3.4

自下而上分析3.4.1

歸約：自下而上分析的例子例 S

aABe

A

Abc|b B

dabcdBSeAAbabbcdeaAbcdeaAdeaABeSSrmaABermaAdermaAbcdermabbcde輸入：abbcde3.4

自下而上分析3.4.2

句柄 句型的句柄是和某產(chǎn)生式右部匹配的子串，并且，把它歸約成該產(chǎn)生式左部的非終結(jié)符代表了最右推導(dǎo)過程的逆過程的一步。

S

aABe

A

Abc|b B

dSrmaABe

rmaAdermaAbcdermabbcde句柄與某個(gè)產(chǎn)生式的右部符號(hào)串相同句柄是句型的一個(gè)子串把句柄歸約成非終結(jié)符代表了最右推導(dǎo)逆過程的一步5/753.4

自下而上分析3.4.2

句柄句柄性質(zhì)：SrmaABe

rmaAdermaAbcdermabbcde句柄的右邊僅含終結(jié)符。如果文法二義，那么句柄可能不唯一。例 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用棧實(shí)現(xiàn)移進(jìn)歸約分析分析器的四種動(dòng)作：移進(jìn)動(dòng)作把下一個(gè)輸入符號(hào)壓棧。規(guī)約動(dòng)作分析器知道整個(gè)句柄已經(jīng)完全出現(xiàn)在棧頂，它確定句柄的左端在棧中的位置，在決定采用哪個(gè)非終結(jié)符來代替句柄（即確定使用哪個(gè)產(chǎn)生式）。接受動(dòng)作分析器宣告分析成功。報(bào)錯(cuò)動(dòng)作分析器發(fā)現(xiàn)了語法錯(cuò)誤，調(diào)用錯(cuò)誤恢復(fù)例程。a+b$輸入移進(jìn)-歸約分析程序分析表M輸出XYZ$棧3.4

自下而上分析3.4.3用棧實(shí)現(xiàn)移進(jìn)歸約分析通過

移進(jìn)歸約分析器在分析輸入串id1

*id2+id3時(shí)的動(dòng)作序列來了解移進(jìn)歸約分析的工作方式。3.4

自下而上分析棧

輸

入

動(dòng)

作

$id1

*id2+id3$

3.4

自下而上分析棧

輸

入

動(dòng)

作

$id1

*id2+id3$移進(jìn)

10/753.4

自下而上分析棧

輸

入

動(dòng)

作

$id1

*id2+id3$移進(jìn)

$id1

*

id2+id3$

3.4

自下而上分析棧

輸

入

動(dòng)

作

$id1

*id2+id3$移進(jìn)

$id1

*

id2+id3$按E

id歸約

3.4

自下而上分析棧

輸

入

動(dòng)

作

$id1

*id2+id3$移進(jìn)

$id1

*

id2+id3$按E

id歸約

$E

*

id2+id3$

3.4

自下而上分析棧

輸

入

動(dòng)

作

$id1

*id2+id3$移進(jìn)

$id1

*

id2+id3$按E

id歸約

$E

*

id2+id3$移進(jìn)

3.4

自下而上分析棧

輸

入

動(dòng)

作

$id1

*id2+id3$移進(jìn)

$id1

*

id2+id3$按E

id歸約

$E

*

id2+id3$移進(jìn)

$E*

id2+id3$

15/753.4

自下而上分析棧

輸

入

動(dòng)

作

$id1

*id2+id3$移進(jìn)

$id1

*

id2+id3$按E

id歸約

$E

*

id2+id3$移進(jìn)

$E*

id2+id3$移進(jìn)

3.4

自下而上分析棧

輸

入

動(dòng)

作

$id1

*id2+id3$移進(jìn)

$id1

*

id2+id3$按E

id歸約

$E

*

id2+id3$移進(jìn)

$E*

id2+id3$移進(jìn)

$E*id2

+id3$

3.4

自下而上分析棧

輸

入

動(dòng)

作

$id1

*id2+id3$移進(jìn)

$id1

*

id2+id3$按E

id歸約

$E

*

id2+id3$移進(jìn)

$E*

id2+id3$移進(jìn)

$E*id2

+id3$按E

id歸約

3.4

自下而上分析棧

輸

入

動(dòng)

作

$id1

*id2+id3$移進(jìn)

$id1

*

id2+id3$按E

id歸約

$E

*

id2+id3$移進(jìn)

$E*

id2+id3$移進(jìn)

$E*id2

+id3$按E

id歸約

$E*E

+id3$

3.4

自下而上分析棧

輸

入

動(dòng)

作

$id1

*id2+id3$移進(jìn)

$id1

*

id2+id3$按E

id歸約

$E

*

id2+id3$移進(jìn)

$E*

id2+id3$移進(jìn)

$E*id2

+id3$按E

id歸約

$E*E

+id3$移進(jìn)

20/753.4

自下而上分析棧

輸

入

動(dòng)

作

$id1

*id2+id3$移進(jìn)

$id1

*

id2+id3$按E

id歸約

$E

*

id2+id3$移進(jìn)

$E*

id2+id3$移進(jìn)

$E*id2

+id3$按E

id歸約

$E*E

+id3$移進(jìn)

$E*E+id3$

3.4

自下而上分析棧

輸

入

動(dòng)

作

$id1

*id2+id3$移進(jìn)

$id1

*

id2+id3$按E

id歸約

$E

*

id2+id3$移進(jìn)

$E*

id2+id3$移進(jìn)

$E*id2

+id3$按E

id歸約

$E*E

+id3$移進(jìn)

$E*E+id3$移進(jìn)

3.4

自下而上分析棧

輸

入

動(dòng)

作

$id1

*id2+id3$移進(jìn)

$id1

*

id2+id3$按E

id歸約

$E

*

id2+id3$移進(jìn)

$E*

id2+id3$移進(jìn)

$E*id2

+id3$按E

id歸約

$E*E

+id3$移進(jìn)

$E*E+id3$移進(jìn)

$E*E+id3

$

3.4

自下而上分析棧

輸

入

動(dòng)

作

$id1

*id2+id3$移進(jìn)

$id1

*

id2+id3$按E

id歸約

$E

*

id2+id3$移進(jìn)

$E*

id2+id3$移進(jìn)

$E*id2

+id3$按E

id歸約

$E*E

+id3$移進(jìn)

$E*E+id3$移進(jìn)

$E*E+id3

$按E

id歸約

3.4

自下而上分析棧

輸

入

動(dòng)

作

$id1

*id2+id3$移進(jìn)

$id1

*

id2+id3$按E

id歸約

$E

*

id2+id3$移進(jìn)

$E*

id2+id3$移進(jìn)

$E*id2

+id3$按E

id歸約

$E*E

+id3$移進(jìn)

$E*E+id3$移進(jìn)

$E*E+id3

$按E

id歸約

$E*E+E

$

25/753.4

自下而上分析棧

輸

入

動(dòng)

作

$id1

*id2+id3$移進(jìn)

$id1

*

id2+id3$按E

id歸約

$E

*

id2+id3$移進(jìn)

$E*

id2+id3$移進(jìn)

$E*id2

+id3$按E

id歸約

$E*E

+id3$移進(jìn)

$E*E+id3$移進(jìn)

$E*E+id3

$按E

id歸約

$E*E+E

$按E

E+E歸約

3.4

自下而上分析棧

輸

入

動(dòng)

作

$id1

*id2+id3$移進(jìn)

$id1

*

id2+id3$按E

id歸約

$E

*

id2+id3$移進(jìn)

$E*

id2+id3$移進(jìn)

$E*id2

+id3$按E

id歸約

$E*E

+id3$移進(jìn)

$E*E+id3$移進(jìn)

$E*E+id3

$按E

id歸約

$E*E+E

$按E

E+E歸約

$E*E

$

3.4

自下而上分析棧

輸

入

動(dòng)

作

$id1

*id2+id3$移進(jìn)

$id1

*

id2+id3$按E

id歸約

$E

*

id2+id3$移進(jìn)

$E*

id2+id3$移進(jìn)

$E*id2

+id3$按E

id歸約

$E*E

+id3$移進(jìn)

$E*E+id3$移進(jìn)

$E*E+id3

$按E

id歸約

$E*E+E

$按E

E+E歸約

$E*E

$按E

E*E歸約

3.4

自下而上分析棧

輸

入

動(dòng)

作

$id1

*id2+id3$移進(jìn)

$id1

*

id2+id3$按E

id歸約

$E

*

id2+id3$移進(jìn)

$E*

id2+id3$移進(jìn)

$E*id2

+id3$按E

id歸約

$E*E

+id3$移進(jìn)

$E*E+id3$移進(jìn)

$E*E+id3

$按E

id歸約

$E*E+E

$按E

E+E歸約

$E*E

$按E

E*E歸約

$E

$

3.4

自下而上分析棧

輸

入

動(dòng)

作

$id1

*id2+id3$移進(jìn)

$id1

*

id2+id3$按E

id歸約

$E

*

id2+id3$移進(jìn)

$E*

id2+id3$移進(jìn)

$E*id2

+id3$按E

id歸約

$E*E

+id3$移進(jìn)

$E*E+id3$移進(jìn)

$E*E+id3

$按E

id歸約

$E*E+E

$按E

E+E歸約

$E*E

$按E

E*E歸約

$E

$接受

30/753.4

自下而上分析使用移進(jìn)歸約方式，即使知道了應(yīng)該進(jìn)行歸約，也還有兩個(gè)問題必須解決確定右句型中將要?dú)w約的子串如何確定選擇哪一個(gè)產(chǎn)生式3.4

自下而上分析3.4.4

移進(jìn)歸約分析的沖突

移進(jìn)歸約沖突例 stmt

ifexprthenstmt |ifexprthenstmtelsestmt|other 如果移進(jìn)歸約分析器處于格局 棧

輸入 …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分析器本節(jié)介紹LR(k)分析技術(shù)特點(diǎn)適用于一大類上下文無關(guān)文法效率高主要介紹構(gòu)造LR分析表的三種技術(shù)簡單的LR方法（簡稱SLR）規(guī)范的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狀態(tài)動(dòng)

作

轉(zhuǎn)

移

id

+*()$

E

TF

0s5s41231s6acc

2

r2s7r2r23r4r4r4r44s5s4

8233.5

LR分析器棧

輸

入

動(dòng)

作

0id*id+id

$

3.5

LR分析器棧

輸

入

動(dòng)

作

0id*id+id

$移進(jìn)

3.5

LR分析器棧

輸

入

動(dòng)

作

0id*id+id

$移進(jìn)

0id5

*

id+id

$

40/753.5

LR分析器棧

輸

入

動(dòng)

作

0id*id+id

$移進(jìn)

0id5

*

id+id

$按F

id歸約

3.5

LR分析器棧

輸

入

動(dòng)

作

0id*id+id

$移進(jìn)

0id5

*

id+id

$按F

id歸約

0F3*

id+id

$

3.5

LR分析器棧

輸

入

動(dòng)

作

0id*id+id

$移進(jìn)

0id5

*

id+id

$按F

id歸約

0F3*

id+id

$按T

F歸約

3.5

LR分析器棧

輸

入

動(dòng)

作

0id*id+id

$移進(jìn)

0id5

*

id+id

$按F

id歸約

0F3*

id+id

$按T

F歸約

0T2*

id+id

$

3.5

LR分析器棧

輸

入

動(dòng)

作

0id*id+id

$移進(jìn)

0id5

*

id+id

$按F

id歸約

0F3*

id+id

$按T

F歸約

0T2*

id+id

$移進(jìn)

45/753.5

LR分析器棧

輸

入

動(dòng)

作

0id*id+id

$移進(jìn)

0id5

*

id+id

$按F

id歸約

0F3*

id+id

$按T

F歸約

0T2*

id+id

$移進(jìn)

0T2*7id+id$

3.5

LR分析器棧

輸

入

動(dòng)

作

0id*id+id

$移進(jìn)

0id5

*

id+id

$按F

id歸約

0F3*

id+id

$按T

F歸約

0T2*

id+id

$移進(jìn)

0T2*7id+id$移進(jìn)

3.5

LR分析器棧

輸

入

動(dòng)

作

0id*id+id

$移進(jìn)

0id5

*

id+id

$按F

id歸約

0F3*

id+id

$按T

F歸約

0T2*

id+id

$移進(jìn)

0T2*7id+id$移進(jìn)

0T2*7id5+id$

3.5

LR分析器棧

輸

入

動(dòng)

作

0id*id+id

$移進(jìn)

0id5

*

id+id

$按F

id歸約

0F3*

id+id

$按T

F歸約

0T2*

id+id

$移進(jìn)

0T2*7id+id$移進(jìn)

0T2*7id5+id$按F

id歸約

3.5

LR分析器棧

輸

入

動(dòng)

作

0id*id+id

$移進(jìn)

0id5

*

id+id

$按F

id歸約

0F3*

id+id

$按T

F歸約

0T2*

id+id

$移進(jìn)

0T2*7id+id$移進(jìn)

0T2*7id5+id$按F

id歸約

0T2*7F10+id$

50/753.5

LR分析器棧

輸

入

動(dòng)

作

0id*id+id

$移進(jìn)

0id5

*

id+id

$按F

id歸約

0F3*

id+id

$按T

F歸約

0T2*

id+id

$移進(jìn)

0T2*7id+id$移進(jìn)

0T2*7id5+id$按F

id歸約

0T2*7F10+id$按T

T*F歸約

3.5

LR分析器棧

輸

入

動(dòng)

作

0id*id+id

$移進(jìn)

0id5

*

id+id

$按F

id歸約

0F3*

id+id

$按T

F歸約

0T2*

id+id

$移進(jìn)

0T2*7id+id$移進(jìn)

0T2*7id5+id$按F

id歸約

0T2*7F10+id$按T

T*F歸約

.........

3.5

LR分析器棧

輸

入

動(dòng)

作

0id*id+id

$移進(jìn)

0id5

*

id+id

$按F

id歸約

0F3*

id+id

$按T

F歸約

0T2*

id+id

$移進(jìn)

0T2*7id+id$移進(jìn)

0T2*7id5+id$按F

id歸約

0T2*7F10+id$按T

T*F歸約

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

3.5

LR分析器棧

輸

入

動(dòng)

作

0id*id+id

$移進(jìn)

0id5

*

id+id

$按F

id歸約

0F3*

id+id

$按T

F歸約

0T2*

id+id

$移進(jìn)

0T2*7id+id$移進(jìn)

0T2*7id5+id$按F

id歸約

0T2*7F10+id$按T

T*F歸約

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

3.5

LR分析器3.5.2LR文法和LR分析方法的特點(diǎn)概念 活前綴：右句型的前綴，該前綴不超過最右句柄的右端

S

*rmAw

rm

w

的任何前綴（包括和

本身）都是一個(gè)活前綴。一個(gè)符號(hào)串的前綴是指從第一個(gè)符號(hào)開始的連續(xù)的若干個(gè)符號(hào)構(gòu)成的子串。55/753.5

LR分析器3.5.2LR文法和LR分析方法的特點(diǎn)概念 活前綴：右句型的前綴，該前綴不超過最右句柄的右端定義

LR文法：我們能為之構(gòu)造出所有條目都唯一的LR分析表3.5

LR分析器LR分析方法的特點(diǎn)棧中的文法符號(hào)總是形成一個(gè)活前綴。3.5

LR分析器棧

輸

入

動(dòng)

作

0id*id+id

$移進(jìn)

0id5

*

id+id

$按F

id歸約

0F3*

id+id

$按T

F歸約

0T2*

id+id

$移進(jìn)

0T2*7id+id$移進(jìn)

0T2*7id5+id$按F

id歸約

0T2*7F10+id$按T

T*F歸約

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

3.5

LR分析器LR分析方法的特點(diǎn)棧中的文法符號(hào)總是形成一個(gè)活前綴。分析表的轉(zhuǎn)移函數(shù)本質(zhì)上是識(shí)別活前綴的DFA。3.5

LR分析器例E

E+T|E

T T

T*F|

T

E F(E)|Fid狀態(tài)動(dòng)

作

轉(zhuǎn)

移

id

+*()$

E

TF

0s5s41231s6acc

2

r2s7