自下而上语法分析习题

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

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))