自下而上语法分析-LR

LR（K）方法概述一种自下而上的语法分析方法。当前最广义的无回溯的“移进-归约”方法。根据栈中的符号串和向前查看的k(k0)个输入符号，就能唯一确定分析器的动作是移进还是归约，以及用哪个产生式进行归约。优点：文法适用范围广；识别效率高；查错能力强；可自动构造。逻辑组成：总控程序＋LR分析表分析表的四种构造方法：LR(0)，SLR(1)，规范LR，LALR

LR分析方法的基本思想是：在规范归约过程中，一方面记住已移进和归约出的整个符号串(历史)，另一方面又根据所用产生式推测未来可能碰到的输入符号(对未来的展望)。当某一符号串类似于句柄出现在栈顶时，需要根据已记载的“历史”、“展望”和“现实”的输入符号三方面的内容来决定栈顶的符号串是否构成了真正的句柄，是否需要归约。一个LR分析器的组成见下图。LR分析方法的基本思想一个LR分析器由3个部分组成：LR分析程序，又称总控程序。所有的LR分析器都是相同的。分析表(分析函数)，不同的文法分析表不同，同一个文法采用的LR分析器不同时，分析表也不同，分析表又可分为动作表(ACTION)和状态转换(GOTO)表两个部分，它们都可用二维数组表示。分析栈，包括文法符号栈和相应的状态栈，它们均是先进后出栈。状态栈：(S0,#)为预先放到栈中的初始状态和符号。文法符号：X1X2…Xm是目前已移进并归约出的句型部分。其实它是多余的，已经概括到状态里。分析器实际上是一个带有先进后出栈的确定的有穷自动机。将“历史”和“展望”综合成“状态”，分析栈用来存放状态，状态概括了从分析开始直到某一归约阶段的全部历史和展望资料，不必象算符优先分析法中要翻阅栈中的内容才能决定是否要进行归约。只需根据栈顶状态和输入符号就可以唯一决定下一个动作。总控程序根据分析表的内容来决定其下一步的处理动作，分析表是根据具体的文法按某种规则构造出来的。LR方法：根据具体文法的分析表对输入串进行分析处理。LR分析过程：在总控程序的控制下，从左到右扫描输入符号串，根据分析栈中的状态和当前输入符号，按分析表中的内容完成相应的分析工作。LR分析表的构成状态动作表ACTION状态转换表GOTOa1a2…#X1X2…XkS1S2...Sn分析表的动作部分：ACTION[Si，aj]表示当分析状态栈的栈顶为Si，输入符号为aj时应执行的动作；表中GOTO[Si,Xj]指出栈顶状态为Si，碰到文法符号为Xj时应转到的下一状态；动作有下列四种：移进(Sn)，归约(R)，接受(A)，报错(E)LR分析器的关键就是构造分析表。文法G：0)S→A，1)A→(A)，2)A→a的分析表：状态ACTIONGOTO()a#A0S2S311ACCEPT2S2S343R2R2R2R24S55R1R1R1R1LR的分析流程开始初始状态0和#入栈读符号根据栈顶状态和输入符号查分析动作表归约?移进?接受?查状态转换表新状态入状态栈

按产生式i归约

根据产生式i的右部符号的个数，符号栈和状态栈相应元素出栈

产生式i的左部符号入栈

输入符号入符号栈

状态i入状态栈读符号分析结束错误YYYNNN步骤状态栈符号栈输入串ACTIONGOTO说明10#(a)#S2开始时，0入状态栈，#入符号栈，输入符号为(，查动作表0行(列为S2，2入状态栈，(入符号栈。202#(a)#S3输入符号为a，查动作表2行a列为S3，3入状态栈，a入符号栈。3023#(a)#R24输入符号为)，查动作表3行)列为R2，用A→a归约，a出符号栈、A入符号栈，3出状态栈、2为栈顶，查GOTO表2行A列得4，4入状态栈。4024#(A)#S5输入符号为)，查动作表4行)列为S5，5入状态栈，)入符号栈。50245#(A)#R11输入符号为#，查动作表5行#列为R1，用A→(A)归约，(A)出符号栈、A入符号栈，245出状态栈、0为栈顶，查GOTO表0行A列得1，1入状态栈。601#A#ACCEPT输入符号为#，查动作表1行#列为ACCEPT，接受。利用分析表分析符号串(a)LR文法：对一个文法，如果能够构造一个分析表，且它的每个入口均是唯一的如何构造LR分析表？活前缀和可归前缀前缀：指从任意符号串x的末尾删除0或多个符号后得到的符号串，如u、uni、university都是university的前缀。活前缀：设λβt是一个规范句型，其中β表示句柄，t∈Vt*，如果λβ=u1u2…ur，那么称符号串u1u2…ui(其中1≤i≤r)是句型λβt的活前缀。可归前缀：含有句柄的活前缀u1u2…ur称为可归前缀。有文法G∶E→T|E+T|E-T，

T→i|(E)，找规范句型E+(i-i)的活前缀和可归前缀。解：首先画出E+(i-i)的语法树可找出第一个i是句柄，那么λβ=E+(i，t=-i)因此活前缀为：E，E+，E+(，E+(i，其中E+(i是可归前缀。ET+E）E（T-ETii活前缀意味着，当前还未形成句柄，或刚刚形成句柄。在活前缀的右边添上一些终结符号后，总可以构成一个规范句型。LR识别过程中，栈里面的符号就是一个活前缀。栈里面的符号添加上适当的终结符号串就可以得到一个句型。在任何时候，只要输入串已扫描过的部分能构成一个活前缀，则意味着所扫描过的这一部分没有错误。活前缀和句柄的关系

1.活前缀不含有句柄的任何符号；

2.活前缀含有句柄的部分符号；

3.活前缀已含有句柄的全部符号。LR(0)项目LR(0)项目的定义：文法的每一个产生式的右部添加一个圆点（.），则构成文法的一个LR(0)项目。直观地，一个项目指明了在分析过程的某一时刻，已经看到的一个产生式的多少。LR(0)项目A→xyz的LR(0)项目：A→.xyzA→x.yzA→xy.zA→xyz.项目集：若干个项目组成的集合称为项目集。例如：对于上述产生式的4个项目即构成一个项目集。后继符号：在项目中紧跟在符号“·”后面的符号称为该项目的后继符号。后继符号表示下一时刻读到的符号。后继符号有多种，据此将项目分为多种：后继符号为终结符：Aα·aβ,称为移进项目；后继符号为非终结符：Aα·Bβ,称为待约项目；后继符号为空：即圆点在最右边Aα·,称为归约项目；归约项目的左边是文法的开始符号Sα·,称为接受项目。后继符号集：项目集中各项目的后继符号所组成的集合称为后继符号集。例如：项目集｛EE·＋T，F·i｝的后继符号集为｛＋，i｝可以由文法的所有LR(0)项目，构造识别文法所有活前缀的FA。在此构造过程中，需要对文法进行拓广，并利用CLOSURE函数和GO函数。LR(0)项目集规范族定义定义：构成识别一个文法活前缀的DFA的项目集（状态）的全体称为这个文法的LR(0)项目集规范族。文法G的拓广文法文法G[S]的拓广文法：G’[S’]=G[S]+{S’→S}拓广的原因：使得语法分析有唯一的“接受”项目：S’→S.项目集I的闭包CLOSURE(I)设I是文法G的任一项目集，则定义和构造CLOSURE(I)的规则如下：①属于I的任何项目也属于CLOSURE(I)；②若A→α.Bβ属于CLOSURE(I)，那么，对于任何关于B的产生式B→γ,项目B→.γ也属于CLOSURE(I)；③重复执行以上两步，直到CLOSURE(I)不再增大为止。项目集闭包的例子文法： 0.E’→E 1.E→E+T 2.E→T 3.T→T*F 4.T→F 5.F→(E) 6.F→iI={[E’→.E]}CLOSURE(I)还包含以下项：[E→.E+T][E→.T][T→.T*F][T→.F][F→.i][F→.(E)]GO(I,X)函数用于定义项目集之间的转换。定义：设I是一个项目集,X是任一文法符，则GO(I,X)定义为：GO(I,X)=CLOSURE(J),其中J={任何具有[A→αX.β]的项目|[A→α.Xβ]∈I}I:A→α·XβJ:A→αX·βXLR(0)项目集规范族构造算法ITEMSETS(G’);{C={CLOSURE({S’→.S})};重复以下操作:对C中每个项目I和I中每个紧接“.”的文法符号xIfGO(I,x)非空且不属于Cthen将GO(I,x)加到C直到C不再增大；}例：拓广文法为：0)S→A，1)A→(A)，2)A→a0:

S→.AA→.(A)A→.a1:

S→A.2:

A→(.A)A→.(A)A→.a

3:

A→a.A(a识别活前缀的有穷自动机

4:

A→(A.)5:

A→(A).A)(aLR(0)项目集规范族的说明如果LR(0)项目集规范族中的每个项目集看做FA一个状态，则项目集规范族的GO函数把这些项目集连接成一个DFA。令I0(CLOSURE({S’→.S}))为DFA的初态，则该DFA就是恰好识别文法所有活前缀的有限自动机。结论：对于任一文法G,关于该文法的LR(0)项目集规范族的GO函数定义了一个识别文法所有活前缀的DFA。有效项目定义：一个项目[A→α1.α2]称为对某个活前缀λα1是有效的，当且仅当存在某个规范推导S=*>λAt=>λα1α2t

其中，α1α2是规范句型λα1α2t的句柄，t是一个终结符号串。有效项目的识别：有效项目的圆点就是活前缀的终止点。引入有效项目的意义：根据栈中活前缀的有效项目确定下一步的动作。具体的，α2=ε,说明栈中已经形成句柄，下一步应该进行归约；α2

≠ε,说明栈中尚未形成句柄，下一步应该进行移进。活前缀与有效项目的关系同一项目可能对多个活前缀是有效的对同一活前缀，可能存在多个有效项目活前缀有效项目的结论一个活前缀w的有效项目集，正是由识别文法所有活前缀的DFA的初态出发，经由标记为w的路径所到达的那个项目集。语法分析过程中，栈中的活前缀的有效项目集就是栈顶的状态所代表的那个项目集。举例构造识别下列文法活前缀的有穷自动机S→A|BA→aAb|cB→aBb|d指出LR（0）项目的分类LR(0)文法如果文法G’的项目集规范族的每个项目集中不存在下述冲突项目：①移进项目和归约项目并存，②多个归约项目并存，则称文法G’为LR(0)文法。只有对于LR(0)文法，才能构造它的LR(0)分析表。LR(0)分析表的构造设文法G’的项目集规范族C={I0,I1,…,In},令其中每个项目集的下标作为分析器的状态，令包含项目[S’→.S]的项目集Ik的下标k为分析器的初态。则构造LR(0)分析表的步骤如下：①若项目A→α.aβ∈Ii且GO(Ii,a)=Ij,其中a为终结符，置ACTION[i,a]=“把状态j和符号a移进栈”，简记为“sj”;②若项目A→α.∈Ii,则对于任何输入符a或结束符#，置ACTION[i,a]=“用产生式A→α进行归约”，简记为“rj”(假定A→α是文法G’的第j条产生式);③若项目S’→S.∈Ii,则置ACTION[i,#]=“接收”，简记为‘accept’；④若GO(Ii,A)=Ij,A为非终结符，则置GOTO(i,A)=j⑤分析表中凡不能用规则①-④添入信息的元素均置上ERROR。状态ACTIONGOTO()a#A0S2S311ACCEPT2S2S343R2R2R2R24S55R1R1R1R1构造LR（0）分析表的步骤小结文法拓广；利用CLOSURE和GO函数，求出C;构造识别活前缀的DFA；由算法构造LR(0)分析表举例构造下列文法的LR（0）分析表S→A|BA→aAb|cB→aBb|dLR(0)分析法面临的问题只有LR(0)文法才能构造LR(0)分析表；LR(0)文法是一种非常简单的文法，这种文法的活前缀识别自动机的每一个状态（项目集）都不含冲突项目。然而，即使是定义简单表达式的文法也不是LR(0)文法。构造文法{E’→EE→E+T|TT→T*F|FF→(E)|i}的项目集规范族，找出其中的冲突项目。移进-归约冲突问题的解决许多冲突可以通过考察有关非终结符的FOLLOW集而得到解决，即通过向前查看一个输入符号来协助解决冲突。考虑如下项目集中的冲突：Ii:{A→α.bβ,B→α.,C→α.}SLR解决方法的基本思想设LR(0)项目集规范族的某个项目集I中含有i个移进项目A1→α.a1β1,A2→α.a2β2,……,Ai→α.aiβi和j个归约项目B1→α.,B2→α.,……,Bj→α.若已知集合{a1,a2,…,ai},FOLLOW(B1),FOLLOW(B2),…,FOLLOW(Bj)两两无交(且没有两个FOLLOW集含有#),则I中的冲突动作可以通过查看当前输入符号a属于上述j+1个集合中的哪一个集合而获得解决，即①若a∈{a1,a2,…,ai},则移进a；②若a∈FOLLOW(Bk),则用产生式Bk→α进行归约；③其它则报错。SLR（1）分析表的构造设文法G’的项目集规范族C={I0,I1,…,In},令其中每个项目集的下标作为分析器的状态，令包含项目[S’→.S]的项目集Ik的下标k为分析器的初态。则构造LR(0)分析表的步骤如下：①若项目A→α.aβ∈Ii且GO(Ii,a)=Ij,其中a为终结符，置ACTION[i,a]=“把状态j和符号a移进栈”，简记为“sj”;②若项目A→α.∈Ii,则对所有a（或#）∈FOLLOW(A)，置ACTION[i,a]=“用产生式A→α进行归约”，简记为“rj”(假定A→α是文法G’的第j条产生式);③若项目S’→S.∈Ii,则置ACTION[i,$]=“接收”，简记为‘acc’；④若GO(Ii,A)=Ij,A为非终结符，则置GOTO(i,A)=j⑤分析表中凡不能用规则①-④添入信息的元素均置上ERROR。构造SLR分析表的步骤小结文法拓广；构造识别活前缀的DFA；求出非终结符的FOLLOW集；由算法构造SLR分析表有关SLR的定义SLR分析表：由SLR方法构造出的分析表，若不含多重定义，则称为文法的SLR分析表SLR分析器：利用SLR分析表的分析器SLR(1)文法：能构造出SLR分析表的文法 构造SLR分析表的例子简单表达式文法：E’→EE