第六章自底向上优先分析法

《第六章自底向上优先分析法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第6章自底向上优先分析法移进-归约分析自底向上语法分析也称为移进-归约分析Shift—ReduceParsing自下而上语法分析的策略：移进与归约；将一个字符串反向归约至开始符号移进-归约过程是自顶向下最右推导的逆过程。仅适用于表达式的语法分析输入符号入栈，同时进行分析。移进就是将一个终结符推进栈归约就是将0个或多个符号从栈中弹出，根据产生式将一个非终结符压入栈。一步归约—当栈顶符号成为句型的句柄，用产生式左部非终结符代替右部的字符串。规范推导—最右推导规范归约—自左向右的规约过程自底向上优先分析法—移进-归约

2、分析分析符号串abbcde是否为G[S]的句子的最右推导：SaAcBeaAcdeaAbcdeabbcdeabbcdeAABS对输入串的移进-归约分析过程例6.1文法G[S]：(1)SaAcBe(2)Ab(3)AAb(4)Bd对输入串的移进-归约分析过程步骤符号栈输入符号串动作#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]：ET+E

8、TTint*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归约Tintint*T

16、+int归约Tint*TT

17、+int移进T+

18、int移进T+int

19、归约TintT+T

20、归约ETT+E

21、归约ET+EE

22、文法G[S]SαAδ且Ab则称b是句型αbδ相对于非终结符A的短语。若有Ab则称b是句型αbδ相对于该规则Ab的直接短语。句柄(Handles)：句型的最左直接短语短语、直接短语、句柄的定义如何决定什么时候移进，什么时候归约？考虑int

23、*int+int可以用Tint进行归约，而得到T

24、*int+int致命错误：无法归约到开始符号E

25、直觉：仅当能被归约到开始符号才进行归约一般的移进-归约策略：若句柄在栈顶出现，则归约；否则移进移进-规约分析策略实际应用中可能出现的“冲突”移进与归约都合法，产生移进-归约冲突归约时可以适用两个不同的产生式，产生归约-归约冲突避免冲突：改写文法根据产生式出现的顺序来选择根据算符的优先级矛盾—冲突Conflicts冲突的例ConflictExample例子：SifEthenS

26、ifEthenSelseS如输入：ifEthenifEthenSelseS分析某一时刻，栈的内容：ifEthenifEthenS而els

27、e是下一token归约还是移进？冲突的例ConflictExample二义文法会导致冲突但应注意，许多非二义文法同样会导致冲突考虑下面的二义文法：EE+E

28、E*E

29、(E)

30、int一个移进-归约分析OneShift-ReduceParse

31、int*int+intshift…………E*E

32、+intreduceEE*EE

33、+intshiftE+

34、intshiftE+int

35、reduceE