编译原理 4 语法分析学习课件

第四章语法分析

哈尔滨工业大学陈鄞4.1自顶向下的分析4.2预测分析法4.3自底向上的分析4.4LR分析法4.5语法分析器自动生成工具提纲从分析树的顶部（根节点）向底部（叶节点）方向构造分析树可以看成是从文法开始符号S推导出词串w的过程例每一步推导中，都需要做两个选择替换当前句型中的哪个非终结符用该非终结符的哪个候选式进行替换输入id

+(id+id)

E+E

E+(E)

E+(E+E)

E+(id+E)

id+(id+E)

id+(id+id)文法①E→E+E②

E→E*E③E→(E)④E→id

(E)E+EididE+E推导过程：EidE分析树：自顶向下的分析(Top-DownParsing)在最左推导中，总是选择每个句型的最左非终结符进行替换例如果S

*lm

α，则称α是当前文法的最左句型(left-sententialform)推导过程E

lm

E+E

lmid+E

lmid+(

E)

lmid+(

E+E)

lmid+(id+E)

lmid+(id+id)输入id

+(id+id)文法①E→E+E②

E→E*E③E→(E)④E→id最右归约最左推导最左推导(Left-mostDerivation)在最右推导中，总是选择每个句型的最右非终结符进行替换例在自底向上的分析中，总是采用最左归约的方式，因此把最左归约称为规范规约，而最右推导相应地称为规范推导输入id+(id+id)文法①E→E+E②

E→E*E③E→(E)④E→id推导过程E

lm

E+E

lm

E+(

E)

lm

E+(

E+E)

lm

E+(

E+id

)

lm

E+(id+id

)

lmid+(id+id)最左归约最右推导最右推导(Right-mostDerivation)E

lm

E

+E

lmid+E

lmid+(E

)

lmid+(E

+E)

lmid+(id+E

)

lmid+(id+id)EE+Eid(E)E+EididE

rm

E+E

rm

E+(E

)

rm

E+(E+E

)

rm

E+(E

+id)

rm

E

+(id+id)

rmid+(id+id)E

E+

E

E+(E)

E+(E+E)

E+(id+E)

id+(id+E)

id+(id+id)E

E

+

E

id+E

id+(E)

id+(E

+E

)

id

+(E

+id

)

id+(id+id

)最左推导和最右推导的唯一性总是选择每个句型的最左非终结符进行替换根据输入流中的下一个终结符，选择最左非终结符的一个候选式自顶向下的语法分析采用最左推导方式文法①E→TE’

②E’→+TE’｜ε

③T→FT’

④T’→*

FT’｜ε

⑤F→(

E

)｜id输入id+id*id

ETE’FT’T＋E’idεFT’idεF＊T’idε例递归下降分析

(Recursive-DescentParsing)由一组过程组成，每个过程对应一个非终结符从文法开始符号S对应的过程开始，其中递归调用文法中其它非终结符对应的过程。如果S对应的过程体恰好扫描了整个输入串，则成功完成语法分析voidA(){选择一个A产生式，A→X1X2…Xk

；for

(i=1tok){if

(Xi是一个非终结符号)

调用过程Xi();elseif(Xi

等于当前的输入符号a)

读入下一个输入符号;else/*发生了一个错误*/;}}可能需要回溯(backtracking)，导致效率较低自顶向下语法分析的通用形式

预测分析是递归下降分析技术的一种，它不需要回溯，因此，是一种确定的自顶向下分析方法通过在输入中向前看固定个数符号来选择正确的A-产生式。通常情况下只需向前看一个符号（即下一个输入符号）可以对某些文法构造出向前看k个输入符号的预测分析器，该类文法有时也称为LL(k)文法类预测分析(PredictiveParsing)例文法G

S→aAd|aBe

A→c

B→b输入

abc同一非终结符的多个候选式存在共同前缀，将导致回溯现象自顶向下分析中遇到的问题问题1例文法GE→E+T|E–T|TT→T*F|T/F|FF→(E)|id输入

id+id*id左递归文法会使递归下降分析器陷入无限循环E

E+T

E+T+T+T

E+T+T

…如果一个文法中有一个非终结符A使得对某个串α存在一个推导A

+Aα，那么这个文法就是左递归的含有A→Aα形式产生式的文法称为是直接左递归的(immediateleftrecursive)经过两步或两步以上推导产生的左递归称为是间接左递归的问题2

A→Aα|β (α≠ε,

β不以A开头)

A→βA′

A′→αA′｜ε例

事实上，这种消除过程就是把左递归转换成了右递归E→E+T｜TT→T*F｜FF→(E)｜idE→TE′E′→+TE′|εT→FT′T′→*FT′｜εF→(E)｜idαβαβA

Aα

Aαα

Aααα…

Aα…α

βα

…αA′

αA′

ααA′

αααA′…

α…αA′

α…αr=βα*消除直接左递归A→Aα1|Aα2|…|Aαn

|β1|β2|…|βm(αi

≠ε,

βj不以A开头)A

β1A′|β2A′|…|βm

A′A′

α1A′|α2A′|…|αn

A′|ε

消除左递归是要付出代价的——引进了一些非终结符和ε_产生式消除直接左递归的一般形式例

S→Aa|bA→Ac|Sd|ε将S的定义代入A-产生式，得：A→Ac|Aad|bd|ε消除A-产生式的直接左递归，得：A→bd

A’|A’A’→cA’|ad

A’|εS

Aa

Sda消除间接左递归输入：不含循环推导（即形如A

+A的推导）和ε-产生式的文法G输出：等价的无左递归文法方法：按照某个顺序将非终结符号排序为A1，A2，…，An

.

for

(从1到n的每个i){for

(从1到i-1的每个i){

将每个形如Ai→Aj

γ的产生式替换为产生式组Ai→δ1

γ∣δ2

γ∣…∣δk

γ，

其中Aj→δ1∣δ2∣…∣δk

，是所有的Aj

产生式

}

消除Ai

产生式之间的立即左递归}

消除左递归算法例文法GS

→aAd|aBeA→cB→b文法G'S→aS'S'→Ad|BeA→cB→b

通过改写产生式来推迟决定，等读入了足够多的输入，获得足够信息后再做出正确的选择提取左公因子(LeftFactoring)输入：文法G输出：等价的提取了左公因子的文法方法：

提取左公因子算法对于每个非终结符A，找出它的两个或多个选项之间的最长公共前缀α。如果α≠ε，即存在一个非平凡的(nontrivial)公共前缀，那么将所有A-产生式A→

α

β1|α

β2|…|α

βn|γ1

|γ2

|…|γm替换为A→α

A'|γ1

|γ2

|…|γmA'→β1

|β2

|…|βn其中，

γi

表示所有不以α开头的产生式体；

A'是一个新的非终结符。不断应用这个转换，直到每个非终结符的任意两个产生式体都没有公共前缀为止4.1自顶向下的分析4.2预测分析法4.3自底向上的分析4.4LR分析法4.5语法分析器自动生成工具提纲S_文法不含ε产生式预测分析法的工作过程从文法开始符号出发，在每一步推导过程中根据当前句型的最左非终结符A和当前输入符号a，选择正确的A-产生式。为保证分析的确定性，选出的候选式必须是唯一的。S_文法（简单的确定性文法，Korenjak&Hopcroft，1966）假如允许S_文法包含ε产生式，将会产生什么问题？每个产生式都以终结符开始同一非终结符的各个候选式的首终结符都不同4.2.1LL(1)文法什么时候使用ε产生式？如果当前某非终结符A与当前输入符a不匹配时，若存在A→ε，可以通过检查a是否可以出现在A的后面，来决定是否使用产生式A→ε（若文法中无A→ε

，则应报错）输入

ada推导

S→aBC

B→bC

B→dB

B→ε

C→c

C→a

D→e

S

aBC

adBC

adC

adaade

S

aBC

adBC

adC可以紧跟B后面出现的终结符：c、a例文法非终结符A的后继符号集可能在某个句型中紧跟在A后边的终结符a的集合，记为

FOLLOW(A)={a|S

*

αAaβ,a∈VT，α,β∈(VT∪VN)*}例(1)S→aBC(2)B→bC(3)B→dB(4)B→ε(5)C→c(6)C→a

FOLLOW(B)={a,c}输入bd{a,c}如果A是某个句型的的最右符号，则将结束符“$”添加到FOLLOW(A)中非终结符的后继符号集产生式A→β的可选集是指可以选用该产生式进行推导时对应的输入符号的集合，记为SELECT(A→β)SELECT(A→aβ)={a

}SELECT(A→ε)=FOLLOW(A)q_文法每个产生式的右部或为ε

，或以终结符开始具有相同左部的产生式有不相交的可选集q_文法不含右部以非终结符打头的产生式产生式的可选集

串首终结符串首第一个符号，并且是终结符。简称首终结符给定一个文法符号串α，α的串首终结符集FIRST(α)被定义为可以从α推导出的所有串首终结符构成的集合。如果α

*ε，那么ε也在FIRST(α)中对于

α∈(VT∪VN)+,FIRST(α)={a|α

*

aβ，a∈VT，β∈(VT∪VN)*}；如果

α

*ε，那么

ε∈FIRST(α)产生式A→α的可选集SELECT如果

ε

FIRST(α),那么SELECT(A→α)=FIRST(α)如果

ε∈FIRST(α),那么SELECT(A→α)=(FIRST(α)-{ε})∪FOLLOW(A)串首终结符集文法G是LL(1)的，当且仅当G的任意两个具有相同左部的产生式A→α|β满足下面的条件：如果α和β均不能推导出ε，则FIRST(α)∩FIRST(β)=Φα

和β至多有一个能推导出ε如果β

*ε，则FIRST(α)∩FOLLOW(A)=Φ；

如果α

*ε，则FIRST(β)∩FOLLOW(A)=Φ；同一非终结符的各个产生式的可选集互不相交可以为LL(1)文法构造预测分析器LL(1)文法第一个“L”表示从左向右扫描输入第二个“L”表示产生最左推导“1”表示在每一步中只需要向前看一个输入符号来决定语法分析动作文法G是LL(1)的，当且仅当G的任意两个具有相同左部的产生式A→α|β满足下面的条件：如果α和β均不能推导出ε，则FIRST(α)∩FIRST(β)=Φα

和β至多有一个能推导出ε如果β

*ε，则FIRST(α)∩FOLLOW(A)=Φ；

如果α

*ε，则FIRST(β)∩FOLLOW(A)=Φ；LL(1)文法例①E→TE'

②E'→+TE'|ε

③T→FT'

④T'→*FT'|ε

⑤F→(E)|id +

ε*

ε

(id(

id

(id

FIRST(E)={ }FIRST(E')={ }FIRST(T)={ }FIRST(T')={ }FIRST(F)={ }FIRST(X)：可以从X推导出的所有串首终结符构成的集合如果

X

*ε，那么

ε∈FIRST(X)计算文法符号X的FIRST(X)不断应用下列规则，直到没有新的终结符或ε可以被加入到任何FIRST集合中为止如果X是一个终结符，那么FIRST(X)={X}如果X是一个非终结符，且X→Y1…Yk∈P(k≥1)，那么如果对于某个i，a在FIRST(Yi)中且ε在所有的FIRST(Y1),…,FIRST(Yi-1)中(即Y1...Yi-1

*ε)，就把a加入到FIRST(X)中。如果对于所有的j=1,2,...,k，ε在FIRST(Yj)中，那么将ε加入到FIRST(X)如果

X→ε∈P，那么将ε加入到FIRST(X)中算法向FIRST(X1X2

…Xn)加入FIRST(X1)中所有的非ε符号如果ε在FIRST(X1)中，再加入FIRST(X2)中的所有非ε符号；如果ε在FIRST(X1)和FIRST(X2)中，再加入FIRST(X3)中的所有非ε符号，以此类推最后，如果对所有的i，ε都在FIRST(Xi)中，那么将ε加入到FIRST(X1X2

…Xn)中计算串X1X2…Xn的FIRST集合计算非终结符A的FOLLOW(A)FOLLOW(A)：可能在某个句型中紧跟在A后边的终结符a的集合FOLLOW(A)={a|S

*

αAaβ,a∈VT，α,β∈(VT∪VN)*}如果A是某个句型的的最右符号，则将结束符“$”添加到FOLLOW(A)中例①E→TE'

②E'→+TE'|ε

③T→FT'

④T'→*FT'|ε

⑤F→(E)|id FOLLOW(E)={ }FOLLOW(E')={ }FOLLOW(T)={

}FOLLOW(T')={

}FOLLOW(F)={

}$)

+)$

)$

+$

*)+$

)FIRST(E)={(id}FIRST(E')={+ε}FIRST(T)={(id}FIRST(T')={*ε}FIRST(F)={(id}不断应用下列规则，直到没有新的终结符可以被加入到任何FOLLOW集合中为止将$放入FOLLOW(S)中，其中S是开始符号，$是输入右端的结束标记如果存在一个产生式A→αBβ，那么FIRST(β)中除ε

之外的所有符号都在FOLLOW(B)中如果存在一个产生式A→αB，或存在产生式A→αBβ且FIRST(β)包含ε，那么

FOLLOW(A)中的所有符号都在FOLLOW(B)中算法例：表达式文法各产生式的SELECT集(1)E→TE'(2)E'→+TE'(3)E'→ε

(4)T→FT'(5)T'→*FT'(6)T'→ε(7)F→(E)(8)F→idSELECT(1)={(id}SELECT(2)={+}SELECT(3)={$

)}SELECT(4)={(id}SELECT(5)={*}SELECT(6)={+)$

}SELECT(7)={(}SELECT(8)={id}表达式文法是LL(1)文法XFIRST(X)FOLLOW(X)E(id$)E'+ε$)T(id+)$T'*ε

+)$F(id*+)$产生式SELECTEE→TE'(idE'E'→+TE’+E'→ε$)TT→FT'(idT'T'→*FT’*FF→(E)(F→idid非终结符输入符号id+*()$

EE→TE'E→TE'E'E'→+TE’E'→εE'→εTT→FT'T→FT'T'T'→εT'→*FT’T'→εT'→εFF→idF→(E)预测分析表递归的预测分析法非递归的预测分析法LL(1)文法的分析方法voidA(){选择一个A产生式，A→X1X2…Xk

；for

(i=1tok){if

(Xi是一个非终结符号)

调用过程Xi();elseif(Xi

等于当前的输入符号a)

读入下一个输入符号;else/*发生了一个错误*/;}}4.2.2递归的预测分析法

递归的预测分析法是指：在递归下降分析中，根据预测分析表进行产生式的选择根据每个非终结符的产生式和LL(1)文法的预测分析表，为每个非终结符编写对应的过程例SELECT(4)={:}SELECT(7)={end}(1)<PROGRAM>→program<DECLIST>:<TYPE>;<STLIST>end(2)<DECLIST>→id<DECLISTN>(3)<DECLISTN>→,id<DECLISTN>(4)<DECLISTN>→ε(5)<STLIST>→s<STLISTN>(6)<STLISTN>→;s<STLISTN>(7)<STLISTN>→ε(8)<TYPE>→real(9)<TYPE>→intprogramDESCENT; begin GETNEXT(TOKEN);

PROGRAM(TOKEN); GETNEXT(TOKEN);

if

TOKEN≠’$’thenERROR; end例SELECT(4)={:}SELECT(7)={end}(1)<PROGRAM>→program<DECLIST>:<TYPE>;<STLIST>end(2)<DECLIST>→id<DECLISTN>(3)<DECLISTN>→,id<DECLISTN>(4)<DECLISTN>→ε(5)<STLIST>→s<STLISTN>(6)<STLISTN>→;s<STLISTN>(7)<STLISTN>→ε(8)<TYPE>→real(9)<TYPE>→int

procedurePROGRAM(TOKEN); begin

ifTOKEN≠’program’thenERROR;

GETNEXT(TOKEN); DECLIST(TOKEN);

GETNEXT(TOKEN);

ifTOKEN≠’:’thenERROR;

GETNEXT(TOKEN); TYPE(TOKEN);

GETNEXT(TOKEN);

ifTOKEN≠’;’thenERROR;

GETNEXT(TOKEN); STLIST(TOKEN);

GETNEXT(TOKEN);

ifTOKEN≠’end’thenERROR; end

例SELECT(4)={:}SELECT(7)={end}(1)<PROGRAM>→program<DECLIST>:<TYPE>;<STLIST>end(2)<DECLIST>→id<DECLISTN>(3)<DECLISTN>→,id<DECLISTN>(4)<DECLISTN>→ε(5)<STLIST>→s<STLISTN>(6)<STLISTN>→;s<STLISTN>(7)<STLISTN>→ε(8)<TYPE>→real(9)<TYPE>→intprocedureDECLIST(TOKEN); begin

ifTOKEN≠’id’thenERROR;

GETNEXT(TOKEN); DECLISTN(TOKEN); end例SELECT(4)={:}SELECT(7)={end}(1)<PROGRAM>→program<DECLIST>:<TYPE>;<STLIST>end(2)<DECLIST>→id<DECLISTN>(3)<DECLISTN>→,id<DECLISTN>(4)<DECLISTN>→ε(5)<STLIST>→s<STLISTN>(6)<STLISTN>→;s<STLISTN>(7)<STLISTN>→ε(8)<TYPE>→real(9)<TYPE>→intprocedureDECLISTN(TOKEN); begin

ifTOKEN=‘,’then begin GETNEXT(TOKEN);

ifTOKEN≠’id’thenERROR;

GETNEXT(TOKEN);

DECLISTN(TOKEN); end

elseifTOKEN≠’:’thenERROR; end 例SELECT(4)={:}SELECT(7)={end}(1)<PROGRAM>→program<DECLIST>:<TYPE>;<STLIST>end(2)<DECLIST>→id<DECLISTN>(3)<DECLISTN>→,id<DECLISTN>(4)<DECLISTN>→ε(5)<STLIST>→s<STLISTN>(6)<STLISTN>→;s<STLISTN>(7)<STLISTN>→ε(8)<TYPE>→real(9)<TYPE>→intprocedureSTLIST(TOKEN); begin

ifTOKEN≠’s’thenERROR; GETNEXT(TOKEN);

STLISTN(TOKEN); end例SELECT(4)={:}SELECT(7)={end}(1)<PROGRAM>→program<DECLIST>:<TYPE>;<STLIST>end(2)<DECLIST>→id<DECLISTN>(3)<DECLISTN>→,id<DECLISTN>(4)<DECLISTN>→ε(5)<STLIST>→s<STLISTN>(6)<STLISTN>→;s<STLISTN>(7)<STLISTN>→ε(8)<TYPE>→real(9)<TYPE>→intprocedureSTLISTN(TOKEN); begin

ifTOKEN=‘;’then begin GETNEXT(TOKEN);

ifTOKEN≠’s’thenERROR;

GETNEXT(TOKEN);

STLISTN(TOKEN); end

elseifTOKEN≠’end’thenERROR; end

例SELECT(4)={:}SELECT(7)={end}(1)<PROGRAM>→program<DECLIST>:<TYPE>;<STLIST>end(2)<DECLIST>→id<DECLISTN>(3)<DECLISTN>→,id<DECLISTN>(4)<DECLISTN>→ε(5)<STLIST>→s<STLISTN>(6)<STLISTN>→;s<STLISTN>(7)<STLISTN>→ε(8)<TYPE>→real(9)<TYPE>→intprocedureTYPE(TOKEN); begin

ifTOKEN≠’real’orTOKEN≠’int’ thenERROR; end4.2.3非递归的预测分析法非递归的预测分析不需要为每个非终结符编写递归下降过程，而是根据预测分析表构造一个自动机，也叫表驱动的预测分析a+b$预测分析程序输入预测分析表M栈输出XYZ$下推自动机

(PushDownAutomata,PDA)例：L={anbn|n≥1}

栈

剩余输入

输出

E$ id+id*id$

TE'$id+id*id

$ E→TE'

FT'E'$id+id*id

$ T→FT'idT'E'$id+id*id

$ F→id

T'E'$

+id*id

$

E'$+id*id

$ T'→ε+TE'$ +id*id

$ E'→+TE'

TE'$ id*id

$

FT'E'$id*id

$ T→FT'idT'E'$ id*id

$ F→id

T'E'$*id

$ *FT'E'$

*id

$ T'→*FT'

FT'E'$

id

$ idT'E'$

id

$ F→id

T'E'$

$

E'$

$ T'→ε

$$ E'→ε如果w是至今为止已经匹配完成的输入部分，那么栈中保存的文法符号序列α满足S*lm

wα例输入符号id+*()$

EE→TE'

E→TE'E'E'→+TE'E'→ε

E'→εTT→FT'T→FT'T'T'→εT'→*FT'T'→εT'→εFF→idF→(E)非终结符输入：一个串w和文法G的分析表

M输出：如果w在L(G)中，输出w的最左推导；否则给出错误指示方法：最初，语法分析器的格局如下：输入缓冲区中是w$，G的开始符号位于栈顶，其下面是$。下面的程序使用预测分析表M生成了处理这个输入的预测分析过程设置ip使它指向w的第一个符号，其中ip是输入指针；令X=栈顶符号；while

(X≠＄

)｛

/*栈非空*/

if

(X等于ip所指向的符号a)执行栈的弹出操作，将ip向前移动一个位置；elseif(X是一个终结符号)error();elseif(M[X，a]是一个报错条目)error();elseif(M[X，a]=X→Y1Y2…Yk

)｛

输出产生式X→Y1Y2…Yk

；

弹出栈顶符号；

将Yk，Yk-1…，Yi

压入栈中，其中Y1位于栈顶。}

令X=栈顶符号}表驱动的预测分析法递归的预测分析法非递归的预测分析法程序规模程序规模较大，不需载入分析表主控程序规模较小，需载入分析表（表较小）直观性较好较差效率较低分析时间大约正比于待分析程序的长度自动生成较难较易递归的预测分析法vs.非递归的预测分析法1）构造文法2）改造文法：消除二义性、消除左递归、消除回溯3）求每个变量的FIRST集和FOLLOW集，从而求得每个

候选式的SELECT集4）检查是不是LL(1)文法。若是，构造预测分析表5）对于递归的预测分析，根据预测分析表为每一个非终结

符编写一个过程；对于非递归的预测分析，实现表驱动

的预测分析算法预测分析法实现步骤错误检测栈顶的终结符和当前输入符号不匹配栈顶非终结符与当前输入符号在预测分析表对应项中的信息为空4.2.4预测分析中的错误处理预测分析中的错误恢复恐慌模式忽略输入中的一些符号，直到输入中出现由设计者选定的同步词法单元(synchronizingtoken)集合中的某个词法单元其效果依赖于同步集合的选取。集合的选取应该使得语法分析器能从实际遇到的错误中快速恢复例如可以把FOLLOW(A)中的所有终结符放入非终结符A的同步记号集合如果终结符在栈顶而不能匹配，一个简单的办法就是弹出此终结符例分析表的使用方法如果M[A,a]是空，表示检测到错误，根据恐慌模式，忽略输入符号a如果M[A,a]是synch，则弹出栈顶的非终结符A，试图继续分析后面的语法成分如果栈顶的终结符和输入符号不匹配，则弹出栈顶的终结符输入符号id+*()$

EE→TE'

E→TE'E'E'→+TE'E'→ε

E'→εTT→FT'T→FT'T'T'→εT'→*FT'T'→εT'→εFF→idF→(E)synchsynchsynchsynchsynchsynchsynchsynchsynch非终结符Synch表示根据相应非终结符的FOLLOW集得到的同步词法单元X

FOLLOW(X)E

$)E'

$)T

+)$T'

+)$F

*+)$

栈 剩余输入

E$

+id*+id$ignore+

E$id*+id$

TE'$id*+id$

FT'E'$id*+id$ idT'E'$id*+id$ T'E'$*+id$ *FT'E'$*+id$ FT'E'$+id$error

T'E'$ +id$

E'

$ +id$ +TE'$ +id$

TE'$ id$

FT'E'$ id$idT'E'$ id$

T'E'$ $

E'$ $ $ $

输入符号id+*()$

EE→TE'

E→TE'E'E'→+TE'E'→ε

E'→εTT→FT'T→FT'T'T'→εT'→*FT'T'→εT'→εFF→idF→(E)synchsynchsynchsynchsynchsynchsynchsynchsynch非终结符4.1自顶向下的分析4.2预测分析法4.3自底向上的分析4.4LR分析法4.5语法分析器自动生成工具提纲从分析树的底部(叶节点)向顶部(根节点)方向构造分析树可以看成是将输入串w归约为文法开始符号S的过程自顶向下的语法分析采用最左推导方式自底向上的语法分析采用最左归约方式（反向构造最右推导）自底向上语法分析的通用框架移入-归约分析(Shift-ReduceParsing)4.3自底向上的语法分析每次归约的符号串称为“句柄”。它是某个产生式的右部。对它的归约代表了相应的最右推导中的一个反向步骤例：移入-归约分析栈剩余输入

动作$

id+(id+id)$$id +(id+id)$

移入$E+(id+id)$

归约:E→id$E+ (id+id)$

移入$E+( id+id)$

移入$E+(id +id)$

移入$E+(E +id)$

归约:E→id$E+(E+id)$

移入$E+(E+id )$

移入$E+(E+E )$

归约:E→id$E+(E )$

归约:E→E+E$E+(E) $

移入$E+E $

归约:E→(E)$E $

归约:E→E+EEEEEEE文法①E→E+E②E→E*E③E→(E)④E→idid

id

id

++

(

)栈内符号串+剩余输入=“规范句型”栈剩余输入

动作$

id+(id+id)$$id +(id+id)$

移入$E+(id+id)$

归约:E→id$E+ (id+id)$

移入$E+( id+id)$

移入$E+(id +id)$

移入$E+(E +id)$

归约:E→id$E+(E+id)$

移入$E+(E+id )$

移入$E+(E+E )$

归约:E→id$E+(E )$

归约:E→E+E$E+(E) $

移入$E+E $

归约:E→(E)$E $

归约:E→E+E例：id

+(id+id

)EEEEEE文法①E→E+E②E→E*E③E→(E)④E→id在对输入串的一次从左到右扫描过程中，语法分析器将零个或多个输入符号移入到栈的顶端，直到它可以对栈顶的一个文法符号串β进行归约为止然后，它将β归约为某个产生式的左部语法分析器不断地重复这个循环，直到它检测到一个语法错误，或者栈中包含了开始符号且输入缓冲区为空为止。当进入这样的格局时，语法分析器停止运行，并宣称成功完成了语法分析移入-归约分析的工作过程移入：将下一个输入符号移到栈的顶端归约：被归约的符号串的右端必然处于栈顶。语法分析器在栈中确定这个串的左端，并决定用哪个非终结符来替换这个串接收：宣布语法分析过程成功完成报错：发现一个语法错误，并调用错误恢复子例程移入-归约分析器可采取的4种动作文法(1)<S>→var<IDS>:<TYPE>(2)<IDS>→i(3)<IDS>→<IDS>,i(4)<TYPE>→real|int$

var$variA

$var

<IDS>$var<IDS>,$var

<IDS>,

iBvar<IDS>var<IDS>:var<IDS>:

realvar<IDS>:<TYPE><S>输入var

iA

,

iB

:

realvar<IDS>,<IDS>var<IDS>,<IDS>:var<IDS>,<IDS>:

realvar<IDS>,<IDS>:<TYPE>造成错误归约的原因：错误地识别了句柄（产生式的右部不一定都是句柄）栈移入-归约分析中的关键问题<S><TYPE>:<IDS>variB,<IDS>iAreal自底向上分析采用最左归约方式，它是最右推导的逆过程，因此，每一步归约都是最右推导中某一步的反向操作

最右推导每一步得到的符号串都是该文法的一个规范句型，因此，最左归约每一步得到的符号串也是该文法的一个规范句型对于A→β∈P，如果S

*rm

αAw

rm

αβw(即αAw和αβw都是

该文法的规范句型)，则称β是规范句型αβw的句柄(Handle)如何正确地识别句柄？句柄的正式定义4.1自顶向下的分析4.2预测分析法4.3自底向上的分析4.4LR分析法4.5语法分析器自动生成工具提纲4.4LR分析法LR文法(Knuth,1963)是最大的、可以构造出相应移入-归约语法分析器的文法类L:对输入进行从左到右的扫描R:反向构造出一个最右推导序列LR(k)分析需要向前查看k个输入符号的LR分析k=0和

k=1这两种情况具有实践意义当省略(k)时，假设k=1自底向上分析的关键问题是什么？如何正确地识别句柄句柄是逐步形成的，用“状态”表示句柄识别的进展程度例：S→bBB

S→.bBB

S→b.BB

S→bB.B

S→bBB.归约状态移进状态待约状态LR分析器基于这样一些状态来构造自动机进行句柄的识别LR分析法的基本原理a1…ai…an

$LR主控程序动作表ACTION转移表GOTO产生式序列状态/符号栈输入缓冲区分析表SmSm-1………S1S0XmXm-1………X1$LR分析器（自动机）的总体结构例文法①S→BB②B→aB③B→b输入babsn：将符号a、状态n

压入栈rn：用第n个产生式进行归约状态ACTIONGOTOab$SB0s3s4121acc2s3s453s3

s464r3r3r35r1r1r16r2r2r2LR分析表的结构①如果ACTION[sm,ai]=sx，那么格局变为：s0s1…smx

$X1…Xmaiai+1…an$初始化一般情况下s0$

a1a2…an$s0s1…sm$X1…Xmaiai+1…an$LR分析器的工作过程初始化一般情况下s0$

a1a2…an$s0s1…sm$X1…Xmaiai+1…an$LR分析器的工作过程②如果ACTION[sm,ai]=rx表示用第x个产生式A→Xm-(k-1)…Xm

进行归约，那么格局变为：s0

s1…sm-k$X1…Xm-kA

ai

ai+1…an$s0

s1…sm-ky

$X1…Xm-kA

ai

ai+1…an$如果GOTO[sm-k,A]=y，那么格局变为：初始化一般情况下s0$

a1a2…an$s0s1…sm$X1…Xmaiai+1…an$LR分析器的工作过程③如果ACTION[sm,ai]=acc，那么分析成功④如果ACTION[sm,ai]=err，那么出现语法错误输入：串w和LR语法分析表，该表描述了文法G的ACTION函数和

GOTO函数。

输出：如果w在

L(G)中，则输出w的自底向上语法分析过程中的归约

步骤；否则给出一个错误指示。方法：初始时，语法分析器栈中的内容为初始状态s0，输入缓冲区中

的内容为w$。然后，语法分析器执行下面的程序：令a为w$的第一个符号；

while(1){/*永远重复*/令s是栈顶的状态；if(ACTION[s，a]

=st){将t压入栈中；

令a为下一个输入符号；}elseif(ACTION[s，a]

=归约A→β){

从栈中弹出│β│个符号；

将GOTO[t，A]压入栈中；

输出产生式A→β

；}elseif(ACTION[s，a]

=接受)break；/*语法分析完成*/else调用错误恢复例程；

}LR分析算法LR(0)分析SLR分析LR(1)分析LALR分析如何构造给定文法的LR分析表？右部某位置标有圆点的产生式称为相应文法的一个LR(0)项目（简称为项目）

A→α1.α2例：S→bBB

归约项目移进项目待约项目S→.bBB

S→b.BB

S→bB.B

S→bBB.项目描述了句柄识别的状态产生式A→ε

只生成一个项目A→·4.4.1LR(0)分析如果G

是一个以S为开始符号的文法，则G的增广文法

G'

就是在G中加上新开始符号S'

和产生式S'

→

S而得到的文法例1)E→E+T2)E→T3)T→T*F4)T→F5)F→(E)

6)F→id0)E'→E1)E→E+T2)E→T3)T→T*F4)T→F5)F→(E)

6)F→id引入这个新的开始产生式的目的是使得文法开始符号仅出现在一个产生式的左边，从而使得分析器只有一个接受状态增广文法(AugmentedGrammar)①S'→S

②S→vI:T

③I→I,i④I→i⑤T→r(0)S'→.S(1)S'→S

.

(2)S→.vI:T

(3)S→v.I:T(4)S→vI.:T(5)S→vI:.T(6)S→vI:T.

(7)I→.I,i(8)I→I.,i(9)I→I,.i(10)I→I,i.(11)I→.i(12)I→i.(13)T→.r(14)T→r.归约项目接收项目初始项目文法中的项目①S'→S

②S→vI:T

③I→I,i④I→i⑤T→r后继项目（SuccessiveItem）同属于一个产生式的项目，但圆点的位置只相差一个符号，

则称后者是前者的后继项目A→α.Xβ的后继项目是A→αX.β(0)S'→.S(1)S'→S

.

(2)S→.vI:T

(3)S→v.I:T(4)S→vI.:T(5)S→vI:.T(6)S→vI:T.

(7)I→.I,i(8)I→I.,i(9)I→I,.i(10)I→I,i.(11)I→.i(12)I→i.(13)T→.r(14)T→r.文法中的项目①S'→S

②S→vI:T

③I→I,i④I→i⑤T→r这15个项目中是否会有某些项目是等价的？可以把等价的项目组成一个项目集(I)

，称为项目集闭包(ClosureofItemSets)，每个项目集闭包对应着自动机的一个状态(0)S'→.S(1)S'→S

.

(2)S→.vI:T

(3)S→v.I:T(4)S→vI.:T(5)S→vI:.T(6)S→vI:T.

(7)I→.I,i(8)I→I.,i(9)I→I,.i(10)I→I,i.(11)I→.i(12)I→i.(13)T→.r(14)T→r.文法中的项目状态ACTIONGOTOab$SB0s3s4121acc2s3s453s3

s464r3r3r35r1r1r16r2r2r2LR(0)分析表例：LR(0)自动机I0:S'→·SS→·BBB→·aBB→·b

I1:S'→S·SBI2:S→B·BB→·aBB→·b

aI3:B→a·BB→·aBB→·b

bI4:B→b·

BI5:S→BB·abBI6:B→aB·ab文法(0)S'→S

(1)S→BB(2)B→aB(3)B→bCLOSURE()函数76CLOSURE(I)=I∪{B→·

γ|A→α·Bβ∈CLOSURE(I),B→γ∈P}计算给定项目集I的项目集闭包SetOfltems

CLOSURE(I){

J

=

I；repeat

for(J中的每个项A→

α∙Bβ)

for(G的每个产生式B→

γ

)

if(项B→

∙γ不在J中

)将B→

∙γ加入J中；

until在某一轮中没有新的项被加入到J中；

returnJ；}GOTO()函数77SetOfltems

GOTO(I，X){

将J

初始化为空集；

for(I

中的每个项A→

α∙Xβ

)