《东北大学秦皇岛分校编译原理课件第二章第七章》由会员分享，可在线阅读，更多相关《东北大学秦皇岛分校编译原理课件第二章第七章（51页珍藏版）》请在金锄头文库上搜索。
1、第7章 LR分析法,7.1 LR类分析法,LR分析法根据当前分析栈和输入串来确定句柄。LR分析过程是一种规范归约过程。LR分析法适用于大多数无二义性的上下文无关文法。常用的LR分析法有：（1）LR（0）分析法（2）SLR（1）分析法（3）LALR（1）分析法（4）LR（1）分析法,LR（K）的含义： L表示由左向右处理输入； R表示生成了最右推导； 数字K表示使用了先行的K个符号。 LR分析法同样要用到先行集合（FIRST集合）和后跟集合（FOLLOE集合）。 SLR（1）是“简单LR（1）”的简写，是对LR（1）分析的改进。 LALR（1）即先行LR（1），是比SLR（1）分析稍微强大但却比
2、一般LR（1）分析简单的方法。,S E E T | E + T T int | (E),Reduce: 如能找到一产生式 A w 且栈中的内容是 qw (q 可能为空), 则可以将其归约为 qA。即倒过来用这个产生式。 如上例, 若栈中内容是 (int ，我们使用产生式 T int并把栈中内容归约为(T Shift: 如不能执行一个归约且在输入串中还有 token ，就把它从输入串移到栈中。 如上例,假定栈中内容是 ( ,输入中还有 int+int)#.不能对( 执行一个归约，因为它不和任何产生式的右端匹配，所以把输入的第一个符号移到栈中,于是栈中内容是 (int ，而余留的输入是 +int)
3、# 。,Reduce的一个特殊情况：栈中的全部内容w归约为开始符号S （即施用 S w） ，且没有余留输入了，意味着已成功分析了整个输入串. 移进归约分析中还会出现一种情况，就是出错，比如当前的token不能构成一个合法句子的一部分，例如上面的文法，试分析 int+)时就会发生错误。,STACK REMAINING INPUT PARSER ACTION1 (int + int)# Shift 2 ( int + int)# Shift 3 (int + int)# Reduce: T int4 (T + int)# Reduce: E T 5 (E + int)# Shift 6 (E +
4、int)# Shift 7 (E + int )# Reduce: T int 8 (E + T )# Reduce: E E + T 9 (E )# Shift 10 (E) # Reduce: T (E) 11 T # Reduce: E T 12 E # Reduce: S E 13 S #,(E + T )# Reduce:E E + Twhy?不用 E T (E ) # 若使用了E T，在栈中形成的(E+E不是规范句型的活前缀（viable prefixes） （E+E不能和任何产生式的右端匹配 （E+E）不是规范句型活前缀：是规范句型（右句型）的前缀，但不超过句柄 移进归约分析的栈
5、中出现的内容加上余留输入构成规范句型,规范推导 规范句型 规范归约,最右推导：在推导的任何一步，其中、是句型，都是对中的最右非终结符进行替换。 最右推导被称为规范推导。 由规范推导所得的句型称为规范句型 GS： SE EE+T|T T(E)|int SE T (E) (E+T) (E+int) (T+int) (int+int) 规范归约 假定是G的一个句子，称序列n ,n-1 ,0是 的一个规范归约 如果该序列满足： （1） n = （2） 0为文法的开始符号 （3）对任何j,0j=n, j-1是从j 经把句柄替换为相应产生式的左部而得到的,LR分析表中动作表的四种动作,（1）移进：把Sj=
6、GOTOSi，a移入到状态栈，把a移入到文法符号栈。（i，j表示状态号） （2）归约：在确定当前句柄时进行的替换操作。 （3）接受acc：当归约到文法符号栈中只剩文法的开始符号时，并且输入符号串已结束即当前输入符号是“#”，则分析成功。 （4）报错：当遇到状态栈顶为某一状态下不该遇到的文法符号时，说明输入串不是该文法的一个句子，则报错。,LR分析器,一个LR分析器由3个部分组成： （1）总控程序：也称驱动程序。对所有的LR分析器总控程序都是相同的。 （2）分析表（或分析函数）：不同的文法其分析表不同，同一文法采用的LR分析器不同时，分析表也将不同。分析表由动作表（ACTION）和状态转换表（G
7、OTO）组成，在计算机里常用二维数组表示。 （3）分析栈：包括文法符号栈和相应的状态栈。都为先进后出栈。分析器的动作由栈顶状态和当前输入符号决定。LR分析器的关键部分是LR分析表的构造。,分析器模型,SP：栈指针 Si：状态栈 Xi：文法符号栈,SP,文法要求,shift-reduce or reduce-reduce 冲突（conflicts） 分析程序不能决定是shift 还是 reduce 或者分析程序归约时有多个产生式可选 例子 （ dangling else） ： S if E then S | if E then S else S 如输入if E then if E then S
8、else S 分析某一时刻，栈的内容:if E then if E then S 而 else 是下一 token 归约还是移进？,LR（0）分析表的结构,LR（0）分析法采用规范归约。LR（0）分析表的构造思想和方法是构造其它LR分析表的基础。LR（0）分析表分为两个部分：（1）ACTION（动作表）部分：列标志为文法的终结符号以及输入结束符#。表中的元素为某个状态或某条规则，或接受标志acc。（2）GOTO（转换表）部分：列标志为非终结符号。表中的元素为要装入的状态。,LR分析算法,置Sp指向输入串w的第一个符号 令S为栈顶状态a是Sp指向的符号 重复 begin if ACTIONS,a
9、=Sjthen begin PUSH j,a(进栈)Sp 前进(指向下一输入符号)end else if ACTIONS,a=rj (第j条产生式为A) then begin pop | 项 令当前栈顶状态为S push GOTOS,A和A(进栈) end else if ACTIONs,a=acc then return (成功） else error end.重复,分析程序,例: GS: S a A c B e 1 A b2 A Ab3 B d4 w=abbcde#,Step states. Syms. The rest of input action goto 1 0 # abbcde#
10、 s2 2 02 #a bbcde# s4 3 024 #ab bcde# r2 goto(2,A) 4 023 #aA s6 5 0236 #aAb cde# r3 6 023 #aA s5 7 0235 #aAc de# s8 8 02358 #aAcd e# r4 9 02357 #aAcB s9 10 023579 #aAcBe # r1 11 01 #S acc,文法GS： (1) S aAcBe (2) A b (3) A Ab (4) B d,a,b,b,c,d,e,步骤,符号栈,输入符号串,动作,1） # abbcde# 移进,2） #a bbcde# 移进,4） #aA bcde# 移进,6） #aA cde# 移进,7） #aAc de# 移进,9） #aAcB e# 移进,11） #S # 接受,符号串abbcde是否是GS的子,对输入串abbcde#的移进-归约分析过程,步骤,符号栈,输入符号串,动作,1） # abbcde# 移进 0 S2,2） #a bbcde# 移进 02 S4,4） #aA bcde# 移进 023 S6,6） #aA cde# 移进 023 S5,7） #aAc de# 移进 0235 S8,
