资源描述：
《编译原理第七章.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第8章LR(k)分析方法8.1分析方法的逻辑结构及分析过程8.2LR(0)分析表的构造8.3SLR(1)分析表的构造8.4LR(1)分析表的构造8.5LALR(1)分析表的构造LR(k)分析方法是指从左向右扫描和自底向上的语法分析。每次根据当前符号或最多向前看k个符号唯一地确定是归约还是继续读。一般来说，凡是上下文无关文法描述的程序设计语言都可以用LR方法进行有效的分析，而且还能在分析过程中及时准确地发现输入符号串的语法错误。通常的程序设计语言一般均能由LR(1)文法产生,而且能由LR(k)产生的语言也可以由LR(1)文法来产生。因此，我们通常只考虑LR(0
2、)和LR(1)两种情况。在本章中我们先后介绍LR(0),SLR(1),LR(1)和LALR(1)分析方法。8.1LR分析方法的逻辑结构及分析过程LR方法也是通过求句柄逐步归约进行语法分析。句柄在运算符优先数法中是通过运算符的优先关系而求得的；在LR方法中，则是通过求可归前缀而求得的。1.活前缀与可归前缀活前缀与可归前缀符号串的前缀是指符号串的任意首部，包括空串ε。定义：对于文法G[S]，若有Sαβ，β∈Vt*则称α为规范前缀，也称为活前缀。r*若α是含句柄的活前缀，并且每个句柄是α的后缀或本身，则称α是可归规范前缀或可归前缀(含有句柄的活前缀)。活前缀不含
3、句柄之右的任何符号。是规范句型的左起部分，到当前句柄为止。如果在其右边加上终结符号串β后就可以成为一个规范句型。S’::=SS::=CbBAA::=AabA::=abB::=CB::=Db C::=aD::=a对于句子ababab有规范推导，见下面的语法树：SaS’CbABDbaba例如，设有文法G[S’]:①规范句型ababab的活前缀为a，可归前缀为此a，时句柄也是a；②规范句型Cbabab的活前缀为C、Cb、Cba，可归前缀为Cba，此时句柄为a；③规范句型CbDbab的活前缀为CbD、CbDb,可归前缀为CbDb，此时句柄为Db；④规范句型CbBab
4、活前缀为CbB、CbBa、CbBab，可归前缀为CbBab，此时的句柄为ab;⑤规范句型CbBA的活前缀为CbBA，可归前缀为CbBA，此时亦为CbBA;⑥规范句型S的活前缀为S，可归前缀为S，此时句柄亦为S。又例如，设有文法G[A]： A::=aBCbB::=BaCB::=bC::=c对于句子abaccb。可归前缀的求法：设某文法有可归前缀αAβ，A∈Vn若有规则A::=uu∈V*则αu也是文法的可归前缀。例如，设有文法G[S]:S::=aAcA::=AbbA::=b文法的所有可归前缀构成的集合称为文法的可归前缀集根据上例文法对句子abbbbbc的归约过程
5、如下：abbbbbcaAbbbbcaAbbcaAcS△△△△其可归前缀集可用自动机来表示，称之为可归前缀图。S4S0S1S2S5S3S6baAcbc从初始状态S0到任一状态形成的符号串构成了某规范句型的活前缀；从初始状态S0到任一终止状态形成的符号串构成了某规范句型的可归前缀。2.LR分析方法的逻辑结构LR分析方法的逻辑结构：设有输入串a1a2a3…an，LR分析方法的逻辑结构图如下：栈顶#an…ai…a2a1#总控制器输入串S0#S1x1….…Smxm分析表输出分析栈中每项都包括状态栈Si和文法符号栈xi两部分。LR分析器包括两个部分，一个总控程
6、序和一张分析表。不同文法的LR分析器的总控程序都是一样的，只是分析表不同，因此LR分析表是LR分析方法的核心。总控程序根据具体的分析表来决定起下一步的处理动作。LR分析的基本原理：把每个句柄(某个产生式的右部)的识别过程划分为若干状态。每个状态下，从左向右地识别句柄中的一个符号，每个状态识别句柄的一部分符号。也就是，在总控程序的控制下，从左到右扫描输入符号串，根据分析栈中的状态和文法符号及当前输入符号，按分析表完成相应的分析工作。由此可见，构造LR分析器的主要工作是构造分析表LR分析表的组成：LR分析表由分析动作(ACTION)表和状态转换(GOTO)表组成
7、。1).分析动作表在分析动作表中，其元素由action(si,aj)来表示。action(si,aj)表示当前分析栈的状态栈栈顶元素为si，文法符号栈栈顶元素为aj(当前输入符号)时，所执行的动作。这个动作可分为四种:移进(S)、归约(r)、接受(acc)和出错(error)。action(Sn,at)…action(Sn,a2)action(Sn,a1)Sn………action(S1,at)…action(S1,a2)action(S1,a1)S1action(S0,at)…action(S0,a2)action(S0,a1)S0at…a2a1状态输入符号2
8、).状态转换表goto[Sn,xe]…goto[Sn
