第11讲语法分析VII

上下文无关文法自上而下自下而上LL(1)文法2个函数递归下降预测分析非递归的预测分析最左推导最右推导！LR文法输入LR分析程序输出栈LR分析器的模型actiongotosmXmsm-1Xm-1…s0…a1ai…an$移进-规约分析归约移进-归约冲突规约-归约冲突句柄1。句柄与某个产生式的右部符号串相同2。句柄是句型的一个子串3。把句柄归约成非终结符代表了最右推导逆过程的一步简单的LR方法（SLR）规范的LR方法向前看的LR方法(LALR）温故知新温故而知新自下而上分析概述自下而上分析方法LR分析器2归约归约，是自下而上分析中的重要动作归约，对应着最右推导的逆过程3abbcdeAABSSaABeAAbc|bBd文法：abbcdeaAbcdeaAdeaABeSrmrmrmrm句柄句柄的非形式定义句型的句柄，是该句型中与一个产生式右部匹配的字符串句柄的精确定义右句型的句柄是一个产生式的右部

，并且该句柄

在用A替换中的句柄之后，得到的是最右推导中的前一个句型令=

ω，则可以通过产生式A->归约为句型Aω4句柄S*X为X的句柄在移进-归约分析中，句柄总是出现在栈顶自下而上分析基于识别句柄5自下而上分析方法使用两种方法：移进shiftABC|xyzABCx|yz归约reduceCbxy|ijkCbA|ijk6温故而知新自下而上分析概述自下而上分析方法LR分析器73.5

LR分析器3.5.1

LR分析算法8输入LR分析程序输出栈LR分析器的模型actiongotosmXmsm-1Xm-1…s0…a1ai…an$LR语法分析器的行为为描述LR语法分析的行为，引入概念格局(Configuration)用二元组表示

(s0X1s1X2s2…Xmsm,aiai+1…an$)

栈的内容尚未处理的输入Xi代表文法符号，si表示状态代表右句型X1X2…Xmaiai+1…an在分析栈中增加了状态9初始格局10LR分析程序输出Action[s,a]Gotos0…a1ai…an$输入栈移进之前(s0X1s1X2s2…Xmsm,aiai+1…an$)11输入LR分析程序输出Action[sm,ai]=“shift

s”GotosmXmsm-1Xm-1…s0…a1ai…an$栈移进之后(s0X1s1X2s2…Xmsmais

,

ai+1…an$)

12LR分析程序输出Action[sm,ai]=“shift

s”GotosmXmsm-1Xm-1…s0…a1ai…an$ais输入栈归约之前13LR分析程序输出栈Action[sm,ai]=“rA”smXmsm-rXm-r…s0…a1ai…an$Goto[sm-r,A]=s

…输入归约从栈中弹出2*||个符号14LR分析程序输出Action[sm,ai]=“rA”sm-rXm-r…s0…a1ai…an$Goto[sm-r,A]=s

2*||输入栈归约从栈中弹出2*||个符号，再进栈15LR分析程序输出Action[sm,ai]=“rA”ssm-rXm-r…s0…a1ai…an$Goto[sm-r,A]=s

A2*||输入栈接受16LR分析程序输出Action[s,$]=“accept”sX1s0…a1ai…an$Goto输入栈报错17LR分析程序输出Action[s,a]未定义…a1ai…an$GotosmXmsm-rXm-r…s0…输入栈本讲纲要活前缀活前缀的DFALR(0)项目集构建识别活前缀的DFA构造SLR分析表18活前缀活前缀：右句型的前缀，该前缀不超过最右句柄的右端

S

*rm

Aw

rm

w

的任何前缀（包括和

本身）都是一个活前缀。19一个符号串的前缀是指从第一个符号开始的连续的若干个符号构成的子串。活前缀文法例子20SaABeAAbc|bBd自下而上分析时，栈中可能出现的串：aabaAaAbaAbcaAdaABaABeS活前缀：右句型的前缀，该前缀不超过最右句柄的右端

S

*rm

Aw

rm

w

的任何前缀（包括和

本身）都是一个活前缀。活前缀与句柄的关系文法例子21栈中可能出现的串：aabaAaAbaAbcaAdaABaABeS①活前缀已含有句柄的全部符号，表明产生式A→β的右部β已出现在栈顶。出现句柄（对应A->b）出现句柄（对应A->Abc）出现句柄（对应B->d）出现句柄（对应S->aABe）SaABeAAbc|bBd活前缀与句柄的关系文法例子22栈中可能出现的串：aabaAaAbaAbcaAdaABaABeS①活前缀已含有句柄的全部符号，表明产生式A→β的右部β已出现在栈顶。出现产生式A->Abc右端的一部分，期望从输入串中看到bc出现产生式S->aABe的右端一部分，期望从输入串中看到e②活前缀只含句柄的一部分符号如β1表明A→β1β2的右部子串β1已出现在栈顶，当前期待从输入串中看到β2推出的符号。出现产生式A->Abc右端的一部分，期望从输入串中看到cSaABeAAbc|bBd活前缀与句柄的关系文法例子23栈中可能出现的串：aabaAaAbaAbcaAdaABaABeS①活前缀已含有句柄的全部符号，表明产生式A→β的右部β已出现在栈顶。期望出现符号A推出的符号串②活前缀只含句柄的一部分符号如β1表明A→β1β2的右部子串β1已出现在栈顶，当前期待从输入串中看到β2推出的符号。③活前缀不含有句柄的任何符号，此时期望产生式A→β的右部所推出的符号串。SaABeAAbc|bBdLR分析的核心工作构建识别活前缀的DFA基于DFA构建分析表24本讲纲要活前缀活前缀的DFALR(0)项目集构建识别活前缀的DFA构造SLR分析表25活前缀分析过程中在分析栈里出现的串，被称为活前缀活前缀可以用一个DFA来识别例如，下面的产生式文法 SV=E SE V*E Vid EV26请画出识别上述活前缀的DFA!本讲纲要活前缀活前缀的识别LR(0)项目集构建识别活前缀的DFA构造SLR分析表27LR(0)项目集由一些LR(0)项目组成的集合LR(0)项目在右部的某个地方加点的产生式例如，对于产生式AXYZ对应的加点项有A·XYZAX·YZAXY·ZAXYZ·又例如，对于A，其加点项有A·28点的左边代表历史信息，右边代表展望信息。直观地讲，项目表示在分析过程的某一阶段，已经看到了产生式的多大部分，以及希望看到的部分。分析过程实例通过实例来说明加点项含义29$SaABeAAbc|bBdabbcde$对应的加点项是S

·aABe表示什么意思呢？分析刚开始，栈内还没有任何字符，加点项中的·

后面是期望看到的文法符号aS0action(0,a)=s1,表示从状态0移进a之后，状态迁移到S1S代表移进动作分析过程实例通过实例来说明加点项含义30$SaABeAAbc|bBdbbcde$对应的加点项是aSa·

ABeA

·

AbcA

·

bA的来源有两种可能S0S1状态S1对应的项目可能有Sa·

ABeA

·

AbcA

·

b下一步动作：action(1,b)=S231$SaABeAAbc|bBdbcde$状态S2是从状态S1移入b后得到的新状态移进符号b后，加点项A

·

b

中的点可以向后移一格，变成Ab

·abS0S1S2状态S1Sa·

ABeA

·

AbcA

·

b状态S2Ab·下一步动作要对b进行归约32$SaABeAAbc|bBdbcde$需要看一下在状态1，如果后面看到一个符号A后可以将点移动到哪里有两种可能结果：aASaA·

BeAA

·bcS0S1状态S1Sa·

ABeA

·

AbcA

·

bS2状态S2SaA·

BeAA

·bcB

·d33$SaABeAAbc|bBdcde$移进b之后aAbS0S1S2状态S2SaA·

BeAA

·bcB

·d新状态为：状态S3AA

b·

cS334$SaABeAAbc|bBdde$进入新状态aAbcS0S1S2S3状态S3AA

b·

c状态S4AA

bc·S4这是一个归约状态，下一步动作是归约35$SaABeAAbc|bBdde$到达状态aAS0S1S2状态S2SaA·

BeAA

·bcB

·d下一步做什么呢？36$SaABeAAbc|bBde$到达状态aAS0S1S2状态S2SaA·

BeAA

·

bcB

·dd状态S5Bd·S5又到了一个归约状态37$SaABeAAbc|bBde$到达状态aAS0S1S2状态S2SaA·

BeAA

·

bcB

·dB状态S6SaAB·

eS638$SaABeAAbc|bBd$到达状态aAS0S1S2B状态S7SaABe·

S6e状态S6SaAB·

e归约态！39$SaABeAAbc|bBd$SS0OK大功告成！本讲纲要活前缀活前缀的识别LR(0)项目集构建识别活前缀的DFA构造SLR分析表403.5

LR分析器从文法构造识别活前缀的DFA

1.拓广文法

EE

EE+T|T TT*F|F F(E)|id

41当且仅当分析器使用EE

规约时，宣告分析成功ErmE+Trm

E+FrmE+idrmT+idrmF+idrmid+id

id+id

F+idT+idE+idE+FE+TE3.5

LR分析器从文法构造识别活前缀的DFA 2.构造LR(0)项目集规范族I0:

E·E E·E+T

E·T T

·T*F T

·F F

·(E) F

·id42闭包函数closure(I)1、I的每个项目均加入closure(I)2、如果Aα·Bβ在closure(I)中，且Bγ是产生式，那么如果项目B·γ还不在closure(I)中的话，那么把它加入。EE

EE+T|TTT*F|FF(E)|id3.5

LR分析器从文法构造识别活前缀的DFA 2.构造LR(0)项目集规范族I0:

E·E (核心项目) E·E+T E·T T·T*

F (非核心项目，

T·F 通过对核心项目求闭包 F·(E)而获得） F·id43E’·E及所有的点不在产生式右部的左端的项目EE

EE+T|TTT*F|FF(E)|id3.5

LR分析器从文法构造识别活前缀的DFA 2.构造LR(0)项目集规范族I0: I1:

E·E EE· E·E+T EE·+T E·T T·T*

F T·F F·(E) F·id

44EE

EE+T|TTT*F|FF(E)|idI1:=goto(I0,E)I1:=goto(I0,X)定义：满足[A·X]属于I0

的所有项目[AX·]的集合的闭包3.5

LR分析器从文法构造识别活前缀的DFA 2.构造LR(0)项目集规范族I0: I1:=goto(I0,E)

E·E EE· E·E+T EE·+T E·T T·T*

F I2:=goto(I0,T) T·F E

T·

F·(E) TT·*

F

F·id

45EE

EE+T|TTT*F|FF(E)|id3.5

LR分析器从文法构造识别活前缀的DFA

2.构造LR(0)项目集规范族I0: I1:

E·E EE· E·E+T EE·+T E·T T·T*

F I2: T·F E

T·

F·(E) TT·*

F

F·id

I3:=goto(I0,F)

TF·46EE

EE+T|TTT*F|FF(E)|id3.5

LR分析器I0: I4:=goto(I0,(

)

E·E F(·E) E·E+T E·E+T E·T E·T T·T*

F T·T*

F T·F T·F F·(E) F·(E) F·id F·id

I5:=goto(I0,id

)

F

id·473.5

LR分析器48

I1:

EE· EE·+TI6

:

EE+·T T·T*F

T·F

F·(E)

F·id

EE

EE+T|TTT*F|FF(E)|idI1I0EI3I2I4I5TF(id3.5

LR分析器49

I1I0EI3I2I4I5TF(idI2:ET·TT·*F

I7:TT

*·FF·(E)

F·id

EE

EE+T|TTT*F|FF(E)|id3.5

LR分析器50

I1I0EI3I2I4I5TF(idEE

EE+T|TTT*F|FF(E)|idI3:

T

F·

3.5

LR分析器51

I1I0EI3I2I4I5TF(idEE

EE+T|TTT*F|FF(E)|idI3:

T

F·

52

I1I0EI3I2I4I5TF(idEE

EE+T|TTT*F|FF(E)|idI4:

F

(·E) E·E+T E·TT·T*F T

·F F·(E) F·id

I2: ET·

TT·*F

I8:

F(E·) EE·+TI3:

TF·

I4:

F(·E)

...

I5:

F

id·

3.5LR分析器53I5:F

id·

EE

EE+T|TTT*F|FF(E)|idI1I0EI3I2I4I5TF(id3.5LR分析器54I1I0+EI6I3I2I4I8I7I5指向I2指向I3T*F(Eidid(FTEE

EE+T|TTT*F|FF(E)|id

55

I1I0+指向I7EI6I9I3I2I4I11I8I7I10*TI5指向I4指向I3指向I5指向I4指向I5指向I6指向I2指向I3F(FTid*id(F(Eid+)id(FT本讲纲要活前缀活前缀的识