欢迎来到天天文库
浏览记录
ID:46571034
大小:298.00 KB
页数:72页
时间:2019-11-25
《第六章自底向上优先分析法》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、第6章自底向上优先分析法移进-归约分析自底向上语法分析也称为移进-归约分析Shift—ReduceParsing自下而上语法分析的策略:移进与归约;将一个字符串反向归约至开始符号移进-归约过程是自顶向下最右推导的逆过程。仅适用于表达式的语法分析输入符号入栈,同时进行分析。移进就是将一个终结符推进栈归约就是将0个或多个符号从栈中弹出,根据产生式将一个非终结符压入栈。一步归约—当栈顶符号成为句型的句柄,用产生式左部非终结符代替右部的字符串。规范推导—最右推导规范归约—自左向右的规约过程自底向上优先分析法—移进-归约
2、分析分析符号串abbcde是否为G[S]的句子的最右推导:SaAcBeaAcdeaAbcdeabbcdeabbcdeAABS对输入串的移进-归约分析过程例6.1文法G[S]:(1)SaAcBe(2)Ab(3)AAb(4)Bd对输入串的移进-归约分析过程步骤符号栈输入符号串动作#abbcde#移进#abbcde#移进#abbcde#归约(A→b)#aAbcde#移进#aAbcde#归约(A→Ab)#aAcde#移进#aAcde#移进#aAcde#归约(B→d)#aAcBe#移进#aAcBe#归约
3、(S→aAcBe)#S#接受移进-归约分析S→EE→T
4、E+TT→int
5、(E)Reduce如能找到一产生式A→w且栈中的内容是qw(q可能为空),则可以将其归约为qA。即倒过来用这个产生式。如上例,若栈中内容是(int,我们使用产生式T→int作为句柄把栈中内容归约为(T移进-归约分析Shift如不能执行一个归约且余留的输入中还有token就把它从输入移到栈中。如上例,假定栈中内容是(输入中还有int+int)#不能对(执行一个归约,因为它不和任何产生式的右端匹配。所以把输入的第一个符号移到栈中,于是栈中内容
6、是(int而余留的输入是+int)#移进-归约分析Reduce的一个特殊情况:栈中的全部内容w归约为开始符号S(即施用S→w),且没有余留输入了,意味着已成功分析了整个输入串。移进归约分析中还会出现一种情况,就是出错,比如当前的token不能构成一个合法句子的一部分,例如上面的文法,试分析int+)时就会发生错误.STACKREMAININGINPUTPARSERACTION1(int+int)#Shift2(int+int)#Shift3(int+int)#Reduce:T–>int4(T+int)#Redu
7、ce:E–>T5(E+int)#Shift6(E+int)#Shift7(E+int)#Reduce:T–>int8(E+T)#Reduce:E–>E+T9(E)#Shift10(E)#Reduce:T–>(E)11T#Reduce:E–>T12E#Reduce:S–>E13S#文法G[E]:ET+E
8、TTint*T
9、int
10、(E)ETE+int*intTintT对输入串的移进-归约分析过程对输入串的移进-归约分析过程
11、int*int+int移进int
12、*int+int移进int*
13、int+int移进int
14、*int
15、+int归约Tintint*T
16、+int归约Tint*TT
17、+int移进T+
18、int移进T+int
19、归约TintT+T
20、归约ETT+E
21、归约ET+EE
22、文法G[S]SαAδ且Ab则称b是句型αbδ相对于非终结符A的短语。若有Ab则称b是句型αbδ相对于该规则Ab的直接短语。句柄(Handles):句型的最左直接短语短语、直接短语、句柄的定义如何决定什么时候移进,什么时候归约?考虑int
23、*int+int可以用Tint进行归约,而得到T
24、*int+int致命错误:无法归约到开始符号E
25、直觉:仅当能被归约到开始符号才进行归约一般的移进-归约策略:若句柄在栈顶出现,则归约;否则移进移进-规约分析策略实际应用中可能出现的“冲突”移进与归约都合法,产生移进-归约冲突归约时可以适用两个不同的产生式,产生归约-归约冲突避免冲突:改写文法根据产生式出现的顺序来选择根据算符的优先级矛盾—冲突Conflicts冲突的例ConflictExample例子:SifEthenS
26、ifEthenSelseS如输入:ifEthenifEthenSelseS分析某一时刻,栈的内容:ifEthenifEthenS而els
27、e是下一token归约还是移进?冲突的例ConflictExample二义文法会导致冲突但应注意,许多非二义文法同样会导致冲突考虑下面的二义文法:EE+E
28、E*E
29、(E)
30、int一个移进-归约分析OneShift-ReduceParse
31、int*int+intshift…………E*E
32、+intreduceEE*EE
33、+intshiftE+
34、intshiftE+int
35、reduceE
此文档下载收益归作者所有