《编译原理 第6章自底向上语法分析、lr分析程序及其自动构造 1》由会员分享，可在线阅读，更多相关《编译原理 第6章自底向上语法分析、lr分析程序及其自动构造 1（86页珍藏版）》请在金锄头文库上搜索。
1、第6章 分析程序及其自动构造,6.1 自下而上分析及其LR分析概述 6.2 LR (0) 分析 6.3 SLR(1) 分析 6.4 LR（1）分析 6.5 LALR分析 6.6 使用二义文法,自下而上分析算法 能力强 构造复杂 最常用和最有效的模型-移进归约(动作）,将输入分成两部分：未消化和半消化的,总控程序,output,Input#未消化,半消化的,分析表,产生式表,S E E T | E + T T int | (E),Reduce: 如能找到一产生式 A w 且栈中的内容是 qw (q 可能为空), 则可以将其归约为 qA.即倒过来用这个产生式. 如上例, 若栈中内容是 (int ，
2、我们使用产生式 T int并把栈中内容归约为(T Shift: 如不能执行一个归约且在未消化的输入中还有 token ，就把它从输入移到栈中. 如上例,假定栈中内容是 ( ,输入中还有 int+int)#.不能对( 执行一个归约，因为它不和任何产生式的右端匹配.所以把输入的第一个符号移到栈中,于是栈中内容是 (int ，而余留的输入是 +int)# .,Reduce的一个特殊情况：栈中的全部内容w归约为开始符号S （即施用 S w） ，且没有余留输入了，意味着已成功分析了整个输入串. 移进归约分析中还会出现一种情况，就是出错，比如当前的token不能构成一个合法句子的一部分，例如上面的文法，试
3、分析 int+)时就会发生错误.,移进-归约模型分析(int + 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 + int)# Shift 7 (E + int )# Reduce: T int 8 (E + T )# Reduce: E E + T 9 (E )# Shift 10 (E) # Reduce: T (
4、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）不是规范句型活前缀 是规范句型（右句型）的前缀，但不超过句柄 移进归约分析的栈中出现的内容加上余留输入构成规范句型,规范推导 规范句型 规范归约,最右推导：在推导的任何一步，其中、是句型，都是对中的最右非终结符进行替换 最右推导被称为规范推导。 由规范推导所得的句型称为规范句型 G
5、S： 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 if E then S | if E then S else S 如输入if E then if E then S else S 分析某一时刻，栈的内容:if E then if E then S 而 else 是下一 token 归约还是移进？,特定的一种shift-reduce实现技术 分析,L R 最右推导分
6、析器模型和分析算法 分析特征讨论,分析器模型,LR分析算法,置ip指向输入串w的第一个符号 令S为栈顶状态a是ip指向的符号 重复 begin if ACTIONS,a=Sjthen begin PUSH j,a(进栈)ip 前进(指向下一输入符号)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.重复,例6.1: GS: S a A c B e 1 A
7、 b2 A Ab3 B d4 w=abbcde#,Step states. Syms. The rest of input action goto 1 0 # abbcde# 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
8、 (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,9） #aAcB e# 移进 02357 S9,11） #S # 接受 01 acc,对输入串abbcde#的LR分析过程,3） #ab bcde# 归约(Ab) 024 r2 3,5） #aAb cde# 归约(AAb) 0236 r3 3,8） # aAcd e# 归约(Bd) 02358 r4 7,10） #aAcBe # 归约(SaAcBe) 023579 r1 1,状态栈,ACTION,GOTO,文法GS： (1) S aAcBe (2) A b (3) A Ab (4) B d,
