自下而上语法分析习题

自下而上语法分析习题

ID:42356971

大小:1.06 MB

页数:26页

时间:2019-09-13

自下而上语法分析习题_第1页
自下而上语法分析习题_第2页
自下而上语法分析习题_第3页
自下而上语法分析习题_第4页
自下而上语法分析习题_第5页
资源描述:

《自下而上语法分析习题》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、自下而上语法分析方法习题课第五章本章要求1.掌握自下而上分析的基本思想,基本概念2.掌握算符优先文法、算符优先关系的判定3.掌握最左素短语、句柄的定义与判定4.掌握求FirstVT集,LastVT集,学会构造算符优先关系表,能用算符优先分析法进行表达式分析问题的提出:①在构造语法树的过程中,何时归约?当可归约串出现在栈顶时就进行归约。②如何知道在栈顶符号串中已经形成可归约串?如何进行归约?通过不同的自底向上的分析算法来解释,不同的算法对可归约串的定义是不同的,但分析过程都有一个共同的特点:边移进边归约。规范归约:使用句柄来定义可归约串。算符优先:使用最左

2、素短语来定义可归约串规范归约的概念有文法G,开始符号为S,如果有S=>xβy,则xβy是文法G的句型,x,y是任意的符号串如果有S=>xAy,且有A=>β,则β是句型xβy相对于非终结符A的短语如果有S=>xAy,且有A->β,则β是句型xβy相对于A->β的直接短语位于一个句型最左边的直接短语称为句柄.**+*注意:每次归约的部分必须是句柄(最右推导)。关键的问题是如何识别句柄例:考虑如下文法:求句型i1*i2+i3的短语、直接短语和句柄。ET

3、E+TTF

4、T*FFi

5、(E)从语法分析树来识别:一棵子树是由树的某个结点连同它的所有子孙组成的。子树

6、的所有端末结点自左至右排列成一个相对子树根的短语。直接短语:只有父子两代结点形成的短语。句柄:最左子树的直接短语。EE+TTFi3i2i1T*FF从语法树可以看出:i1,i2,i3,i1*i2,i1*i2+i3是句型i1*i2+i3的短语直接短语有:i1,i2,i3句柄是:i1ET

7、E+TTF

8、T*FFi

9、(E)句型i1*i2+i3的语法树如图:练习1、令文法G1为:E→E+T

10、TT→T*F

11、FF→(E)

12、i证明E+T*F是它的一个句型,指出这个句型的所有短语、直接短语和句柄。EE+TT*FT*F是句型E+T*F相对于T的短语E+T*F句型E+T*

13、F相对于E的短语T*F是句型E+T*F相对于T的直接短语T*F是句柄2对下述文法,求句型E+T*F+i的短语、直接短语、句柄ET

14、E+TTF

15、T*FFi

16、(E)EE+TFiE+TT*F短语有:i,T*F,E+T*F,E+T*F+i直接短语有:i,T*F句柄是:T*F练习规范归约的定义:假定α是文法G的一个句子,如果序列:αn,αn-1,……,α0(=S)满足如下条件,则序列αn,αn-1,……,α0是一个规范归约:(1)αn=α是给定的句子(2)α0=S是文法的开始符号(3)对任何i,0

17、号而得到的。规范归约是最右推导的逆过程,规范归约又称为最左归约。最右推导又称规范推导,由规范推导所得到的句型称规范句型,规范推导的逆过程是规范归约。句型归约规则abbcde(2)AbaAbcde(3)AAbaAcde(4)BdaAcBe(1)SaAcBeS(1)SaAcBe (2)Ab (3)AAb (4)Bd上述例子中句子abbcde的规范归约过程是:abbcde,aAbcde,aAcde,aAcBe,S练习使用下述文法对句型i1*i2+i3进行规范规约:ET

18、E+TTF

19、T*FFi

20、(E)i1*i2+i3,F*i2+i3,T*i

21、2+i3,T*F+i3,T+i3,E+i3,E+F,E+T,EEE+TTFi3i2i1T*FF2、考虑下面的表格结构文法G2:S→a

22、^

23、(T) T→T,S

24、S(1)给出(a,(a,a))和(((a,a),^,(a)),a)的最左和最右推导。(a,(a,a))的最左推导:S(T)(T,S)(S,S)(a,S)(a,(T))(a,(T,S))(a,(S,S))(a,(a,S))(a,(a,a))(((a,a),^,(a)),a)的最左推导:S(T)(T,S)(S,S)((T),S)((T,S),S)((T,S,S),S)((

25、S,S,S),S)(((T,S),S,S),S)(((S,S),S,S),S)(((a,S),S,S),S)(((a,a),S,S),S)(((a,a),^,S),S)(((a,a),^,a),S)(((a,a),^,a),a)(((a,a),^,(a)),a)的最右推导:S(T)(T,S)(S,S)(S,a)((T),a)((T,S,S),S)((S,S,S),S)(((T,S),S,S),S)(((S,S),S,S),S)(((a,S),S,S),S)(((a,a),S,S),S)(((a,a),^,S),S)

26、(((a,a),^,a),S)(((a,a),^,a),a)(a,(a,a))

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

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

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