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

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

ID:46571034

大小:298.00 KB

页数:72页

时间:2019-11-25

第六章自底向上优先分析法_第1页
第六章自底向上优先分析法_第2页
第六章自底向上优先分析法_第3页
第六章自底向上优先分析法_第4页
第六章自底向上优先分析法_第5页
资源描述:

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

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

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。