大三下课程编译原理

Ch5Ch55.1“移近—LR0)SLR(1)LR1)LALR1)语法分析器的自动生成与第1Ch5Ch5语法分 5.3LR第2Ch5Ch5语法分 G第3Ch5语法分 LR在R分析的每一步，仅据分析栈当前已经移进和归约的全部语法符号并最多再向前看k个输入字符，就能确定适合于文 则的句柄是否已在栈顶形成，从而第4Ch5Ch5语法分 第5CCh5语法分 (LR分析表(LR分析表#

┆┆#

第6Ch5语法分 LR分析器结构与工作原

状态

的“历史”和“展望”信息； # 和归约(VN#

P第7Ch5语法分 Ch5语法分 ①L→E,②L→③E→

#0E2,5E2④E→ #0E2,5E2输入字符串ababE(归约 ，(移进栈aE(归约第8Ch5Ch5语法分 ab,#EL02112345266第9Ch5语法分 Ch5语法分 G(L)的LR①L→E,②L→③E→#0E2,5E2④#0E2,5E2输入字符串ababE(归约 ，(移进栈aE(归约第10Ch5语法分 LR分析器结构与工作原

Q×(VT¨{#})Q×VN第11Ch5Ch5语法分 LRstateActionGoto …………第12Ch5Ch5语法分 state…goto(Q0,…goto(Q0,goto(Q1,…goto(Q1,……………goto(Qm,…goto(Qm,Qi˛Xi˛第13CCh5语法分 goto(Qi,Xi)

goto(Qi,Xi)的Qi、Xi意指当前栈顶的第14Ch5Ch5语法分 分析动作 state………Qi˛ai˛第15Ch5Ch5语法分 SQ(移进：将ai和Qj状态压入栈jaction(Qi,ai)第16Ch5Ch5语法分 …#…$:a1a2……#…FPaction(Qm,ai)= …#…$:a1a2……#…FP第17CCh5语法分 action(Qi,ai)

SQj(移进：将ai和Qj状态压入栈rj(归约：用第j个产生式归约第18CCh5语法分 $:a1a2…aiai+1…an……#……PP

,

)=归约。设G第j个产生式为：AXm-r+1Xm-r+2…#…AP第19CCh5语法分 Pgotogoto(Qm-r,A)=P…#…A$:a1a2…aiai+1…anF

第20CCh5语法分 action(Qi,ai)

SQj(移进：将ai和第jrj(归约：用第j个产生式归约)acc(接受：分析成功)error(出错：语法错，调出错处理程序)第21Ch5Ch5语法分 ab,#EL02112345266第22Ch5Ch5语法分 LR分析器结构与工作原①分析开始，将初始状态Q0及输入字符串左界符 //初始化②据当前分析栈栈顶Qm，当前输入符号ai查action若action(若action(Qm,ai)＝SQj若action(Qmai)＝rj，若action(Qm,ai)＝acc若action(Qmai)＝error第23Ch5Ch5语法分 第24Ch5Ch5语法分 例 G(L)的LR①②③④输入字符串aba第25Ch5语法分 栈中状态输入符号 a,b,a ,b,a # ,b,a #

44b,a#5,a#6,a# 7a#8##9########第26Ch5Ch5语法分 L⑥⑤①④②③第27Ch5Ch5语法分 LR分析的关键—LR分析表：集成了全第28Ch5Ch5语法分 LR0)SLR1)LR1)LALR1)语法分析器的自动生成与第29Ch5Ch5语法分 LR0LR(0)第30Ch5Ch5语法分 5.4.1 定义5.6（活前缀R$SaAwaw若串是ab的前缀R则是活前缀；当=a，则活前缀特点:第31Ch5语法分 栈中状态输入符号 10a,b,a#10a,b,a#2,b,a#3,b,a#4b,a#5,a#r4(6,a#7a#8##9######r1用规则①归约##第32Ch5Ch5语法分 L⑥⑤①④②③第33Ch5Ch5语法分 5.4.1 定义 （LR(0)项目约定：若产生式形式为Aε则其LR(0)项第34CCh5语法分 5.4.1 例

设文法S→A| A→aA|b|eS→·S→·A→·A→·b

S→AS→BA→a·AA→b·

B→· B→c第35Ch5Ch5 LR(0)句柄a恰好包含在栈中，即当前栈中的内容构成了所期望的刚好含句柄的活前缀，应按A→a进行归约。S’a·（S’是开始符号用S’a第36Ch5Ch5语法分 5.4.1 需将a移进分析栈。 第37例

设文法Ch5语法分 5.4.1 B→· SCh5语法分 5.4.1 B→·A→a·A→a·S→AS→BS'→SA→·aAA→·bS'→·SS→·AS→·BA→A→A→bB→cA→aA第38Ch5Ch5语法分 5.4.1 自动机：①规定文法开始符号在左侧的产生式(设S'→A)的第一个LR(0)项目(即S'·A为NFA的唯一初态；②令所有LR(0)项目分别对应NFA第39③若状态i和状态j出自同一文法G的产生式且两个状态LR(0)i为 iji引一条标记为Ｘiiji为待约项目(设为Ｘ→a·Aβ)，则从状态i引ε弧到所有A·g的状态。Ch5语法分 Ch5语法分 5.4.1

第40Ch5语法分Ch5语法分 5.4.1 NFAM=(Q，Σ，f，q0，Z

G的

i为则j˛f(i，Ｘi若状态i为待约项目(设Ｘ→a·Aβ)A→·gf（i，）第41CCh5语法分 5.4.1 例

设文法G(S )6 61A→·aA e

5S¢→A3e0S¢→ 3eb

e A→ A→be

第42CCh5语法分 5.4.1 e01AAe01AA6e53eb4I

第43Ch5语法分Ch5语法分 5.4.1 b32A→b.bA4aAA→a.AA→.A→.ba01S＇→A.S＇→.AA→.aAA→.bAaAbaA0aA143b201 ab(b归约到01 aA(aA归约到 CC第44Ch5Ch5语法分 LR0LR(0)第45Ch5Ch5语法分 5.4.1 定义例5.12文法G(S的LR(0)项目集规范族CC=（｛S→｛A→b·｝｛S→A·｝｛A→aA·｝）第46Ch5Ch5语法分 5.4.2 构造LR(0)项目集规范族的方法(之一第一步 第二步 G所有活前缀的 第47CCh5语法分 5.4.2 构造LR(0)项目集规范族的方法

第48Ch5Ch5语法分 5.4.2 假定I是文法G的任一项目集，则构造I①I中的每一个项目皆属于②若形如Aa·Bβ(B∈VN的项目属于则对G中的任何产生式B第49Ch5Ch5语法分 求项目集转换函数GOI,X)定义I是文法G的一个项目集，X为G的符号，则GO(I,X)＝closure(J)。J={形如AαX·β的项目|$A→a·Xβ∈I}第50CCh5语法分 5.4.2 构造LR(0)项目集规范族的方法第一步

号，则将产生式S¢→S加入到G中构成新的文法G，S为G的开始符号，G称为G的 法。（使文法开始符号的 第51Ch5语法分 S→A| A→aA|b| B→S→A|BA→aA|b|εB→c第52Ch5语法分 5.4.2 itemsets(GSS

if对CI和每个文法符号X,若GO(I,X)非空且不在C中)GO(I,X)加入C中}while(没 的项目可以加入}第53Ch5语法分 5.4.2 利用构造LR(0)项目集规范族的方法(之二)求 closure(S¢→.A)={S¢→.A，A→.aA|.b}＝I0GO(I0,a)=closure(A→a.A)={A→a.A，A→.aA|.b}＝I2GO(I0,b)=closure(A→b.)={A→b.}＝I3GO(I2,A)=closure(A→aA.)={A→aA.}＝I4第54Ch5Ch5语法分 5.4.2 {A→a.A，A→.aA|.b}，{A→b.}，{A→abA0abA02311223434第55Ch5语法分 5.4.2 Ch5语法分 5.4.2 包含归约项目的项目集构成终态集Z第56Ch5语法分 5.4.2 Ch5语法分 5.4.2 初始状态0＝{closure(S¢→·S)}if对每个状态i和每个文法符号X若GO(i,X)=j非空且不在Q中)while(没有的状态可以加入Q);}第57Ch5语法分 A→a.AA→A→a.AA→.aAA→.b4A→A→aA S¢→.AA→.S¢→.AA→.aAA→.b3A1

A A0b →A1第58Ch5Ch5语法分 LR0LR(0)第59Ch5Ch5语法分 5.4.3 LR(0)分析表的构定义①即含移进项目又含归约项目； ②含有多个归约项目；第60Ch5语法分

0202

ab(b归约到aA(aA归约到AaAbAaAb

A→aAA→a.A→aAA→.aAA→.bbS¢→.AA→.aAS¢→.AA→.aAA→.b3A1→A→ACh5Ch5语法分 5.4.3 LR(0)分析表的构 对应分析表中action(M,a)＝SN(a∈VT)，在DFA中为从状态Ｍ出发，经过一条aN； 对应分析表中action(Ｍ,a)＝rn(a∈VT)，在式编号为n；③对分析表中GOTO(M，B)＝N(BVN)action(Sk＝acc”,其中k是第62Ch5Ch5语法分 5.4.3 LR(0)分析表的构算法 若f(K，a)＝j(a∈ＶT)，则置action(K,a)＝Sj；第63Ch5Ch5语法分 5.4.3 LR(0)分析表的构算法 构造LR(0)分析表（续②若f(k，A)＝j(A∈ＶN)GOTO(K，A)＝j③若A→a·k，则对所有终结符a和结束符“＃”，置action(K,a)＝rj和action(K,＃)＝rj。(其中假设产生式Aa·j个产生式S→S·∈k，则置action(K,第64CCh5语法分 5.4.3 LR(0)分析表的构4:A→aA4:A→aA2:A→a.A A→. 0:S→.AA0:S→.AA→.aAA→.bbb3:A→bA

ab#A01124341:1:S→A→AA→aA②｜b第65Ch5Ch5语法分 5.4.3 LR(0)分析表的构算法 C＝｛I0I1，…，In｝，K 若GOIka)＝Ij(a∈ＶT)action(K,a)＝Sj第66Ch5Ch5 LR(0)算法 构造LR(0)分析表（续 若GOIk,A)＝Ij(A∈ＶN)GOTO(K，A)＝j③若A→a·∈Ik，则对所有终结符a＃”，置action(K,a)＝rjaction(K,＃)＝rj(其中假设产生式Aa·j个产生式 若S→S·∈Ik，则置action(K,⑤第67CCh5语法分 5.4.3 LR(0)分析表的构对例5.12的文法G(S有LR(0)项目集规范族及GO→AA→aA②｜bI0：｛S¢→·A，A→AA→aA②｜bI2：｛A→a·A，A→·aA，A→·bI3：｛A→b·｝I4：｛A→aA·｝ab#A0ab#A0112434

abA02abA02311223434Ch5Ch5语法分 LR0)SLR1)LR1)LALR1)语法分析器的自动生成与第69Ch5语法分 SLR(1)分析与SLR(1)分析表的构例 G A→aA|首先文法 G S 第70G①②S①②SCh5 SLR(1)分析与SLR(1)ASAS→Aa#A011233A 3a\文法G是非LR(0)第71Ch5语法分 SLR(1)分析与SLR(1)分析表的构 第72Ch5Ch5语法分 SLR(1)分析与SLR(1)分析表的构A→b·的项目集（状态）Ii，不管当前输i的那一行的诸元素都指定为rj(其中j为产生式A→b·的编号)。………i… Ch5Ch5语法分 5.6LR(1)分 action(i,a)={A→ ("a∈VT¨ \用A定义4.5（回顾FOLLOW(A)＝｛a|S=>…Aa…，a∈VT｝若S=>…A，则令＃∈FOLLOW(A)。第74Ch5语法分 SLR(1)分析与SLR(1)分析表的构Ii=｛A→b·B→d·，｝FOLLOW(B)，再对任何输入符号a：当a∈FOLLOW(A)时，置actioni＝{A→b归约当a∈FOLLOW(B)时，置actioni＝{Bd归约 SLR(1)第75Ch5Ch5语法分 SLR(1)分析与SLR(1)分析表的构算法 C＝｛I0I1，…，In｝，K 若GOIka)＝Ij(a∈ＶT)action(K,a)＝Sj第76Ch5Ch5语法分 SLR(1)分析与SLR(1)分析表的构算法 构造SLR(1)分析表（续 若GOIk,A)＝Ij(A∈ＶN)GOTO(K，A)＝j③若A→a·∈Ik，则对所有a˛FOLLOW(A)，置action(K,a)＝rj。(其中假设产生式Aa·j个产生式 若S→S·∈Ik，则置action(K,⑤第77Ch5Ch5语法分 5.4.3 LR(0)分析表的构算法5.7’构造SLR(1) 若f(K，a)＝j(a∈ＶT)，则置action(K,a)＝Sj；第78Ch5Ch5语法分 5.4.3 LR(0)分析表的构算法 构造SLR(1)分析表（续 若f(k，A)＝j(AＶN)GOTO(K，A)＝j③若A→a·k，则对所有a˛置action(K,a)＝rj(其中假设产生式Aa·j个产生式 若S→S·∈k，则置action(K,⑤第79Ch5语法分 SLR(1)分析与SLR(1)分析表的构定义表，如果每个不含多重定义，则称它为GSLR(1)SLR(1)分析表构造=SLR(1)方法+LR(0)SLR(1)=第80Ch5语法分 SLR(1Ch5语法分 SLR(1)分析与SLR(1)分析表的构

FOLLOW(A)a#A0a#A0112330

AAA→aS’→A 3a

第81Ch5Ch5语法分 LR0)SLR1)LR1)LALR1)语法分析器的自动生成与第82Ch5Ch5语法分 5.6LR(1)分SLR(1第83Ch5语法分 5.6LR(1)分例 S→S→LL→R→

为为第第84Ch5Ch5语法分 5.6LR(1)分 0：S’→·SS→·ＲＬ→·*L→R→LRi=2：R→3：S→3：S→i6：S→L=·RL→·*LRiR5：Ｌ→L*L8：R→7：L4:LR→·LL→·*L→*第第85 S→ R→ S→ L→ L L S→ L→ S→ R→Ch5语法分 5.6LR(1)分 状态2＝｛S存在移进－归 FOLLOW( FOLLOW(R)∩｛=｝≠\文法G是非SLR(1) Ik：A→b若a∈FOLLOW(A)actionk,a)={A→第86CCh5语法分 5.6LR(1)分 action(k,a)={A→ \用AAb0#…dk=>…Aa…，a∈VAb0#…dk$:…a

第87Ch5Ch5语法分 5.6LR(1)分SLR(1第88Ch5Ch5语法分 5.6LR(1)分 定义 （LR(k)项目［A→a·β，a1a2…akAa·β是一个LR(0ai˛VT¨{#}a1a2…ak：第89Ch5Ch5语法分 5.6LR(1)分 定义 （LR(1)有效项目>dAω=>aω 其中：ω∈VT*，=a，a˛FIRST(w)a为’#’(当w=)，称a第90例5.16 设有文法S→ B→aB|LR(1)项目Ba.B,a]对活前缀aaa$S=>BB=>BaB=>Bab=>

=>a=>aaa

当w=eCh5Ch5语法分 5.6LR(1)分 LR(1)项目B→a.B,#]对活前缀Baa $SBB=>BaB=>第91CCh5语法分 5.6LR(1)分 例如，对例5.15I2＝｛S→L·=FOLLOW(从[R→L·,#]项目 而[R→L·,=]项目

$S‘SR

L S→ L→ S→ R→第92Ch5Ch5语法分 5.6LR(1)分 若文法G的一个LR(0)项目［Aβ1·R*>RR第93Ch5Ch5语法分 5.4.3 LR(0)分析表的构3aAabb4A→b3aAabb4A→bA2S¢→.AA→.aAA→.bA→.aAA→.b→AA→aAA→aA51第94Ch5Ch5语法分 5.6LR(1)分SLR(1第95Ch5Ch5语法分 5.6LR(1)分 1：函数closure(I2：GO函数；第96Ch5算法closure(I{

5.6LR(1)分 *注意：待约项目扩展的项目doifI[A→a·Bβa及G′中的每个产生式B→γFIRST(ba)b,如果[B→•γ，b]不在I中B→•γ,b]加到I}while(没 的项目可以加入I)returnI}第97Ch5Ch5语法分 5.6LR(1)分 GOIX){令J＝{[A→aX•β,a]|[A→a•Xβ,a]˛I}; }LR(1)LR(1)项目集I的GO函数：GO(IX)是I中第98Ch5)

5.6LR(1)分 {C=closure({S¢→•S,#});do{

if对C的每个项目IX,若GO(I,X)非空且不在C中)把GO(I,X)加入C中;}while(没 }

第99Ch5语法分 5.6LR(1)分 算法{初态0=closureS¢→•Sdo

if对每个状态iX若GO(iX)＝j非空且不在DFA中}while(没 }

第100Ch5Ch5语法分 5.6LR(1)分 例 S→S→LL→R→第1016Lfi 6Lfi0S’fiS，#

S’fiS，# SfiL＝R，#SfiR，#

LSfiL•＝R，# L，#

RLfi*R，＝/#

SfiR，#

SfiL＝R•，#Lfii，＝/#RfiL，#

12Lfi

10 13Lfi*R•，# Lfi

RLfi

Lfi*R•，＝/#

Rfi

4Lfi8Rfi

LfiLfi

第102Ch5Ch5语法分 5.6LR(1)分SLR(1第103CCh5语法分 5.6LR(1)分 算法

(LR(1)分析表构造 的文法G和文法G的LR(1)项目集规范族C和GO函数输出：文法G的LR(1)方法：设G的LR(1)C＝｛I0,I1,…,［S¢→·S，＃］的项目集为分析表的初态。第104Ch5Ch5语法分 5.6LR(1)分 算法5.10（续①对于每个项目集Ii中形如［A→a·Xb，b］的项目，若GO(Ii,X)＝Ij，且X∈VT，置action［i,X］＝SjX∈VN时，则置:GOTO［i,X］＝j②若归约项目［A→a·a］∈Ii，Aa为文法的第j个产生式，则置action［i,a］=rj。③若接受项目［S'→S·，#］∈Ii，则置action［i，#］=“acc”④对分析表中不能按上述规则填入信息的元素，第105CCh5语法分 5.6LR(1)分 算法

(LR(1)分析表构造 的文法G和文法G的识别LR(1)输出：文法G的LR(1)方法：设G的识别LR(1)Q＝｛0,1,…,令Q的每个状态Ｋ第106Ch5Ch5语法分 5.6LR(1)分