资源描述:
《自下而上语法分析习题》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
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的短语、直接短语和句柄。ET
3、E+TTF
4、T*FFi
5、(E)从语法分析树来识别:一棵子树是由树的某个结点连同它的所有子孙组成的。子树
6、的所有端末结点自左至右排列成一个相对子树根的短语。直接短语:只有父子两代结点形成的短语。句柄:最左子树的直接短语。EE+TTFi3i2i1T*FF从语法树可以看出:i1,i2,i3,i1*i2,i1*i2+i3是句型i1*i2+i3的短语直接短语有:i1,i2,i3句柄是:i1ET
7、E+TTF
8、T*FFi
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的短语、直接短语、句柄ET
14、E+TTF
15、T*FFi
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)AbaAbcde(3)AAbaAcde(4)BdaAcBe(1)SaAcBeS(1)SaAcBe(2)Ab(3)AAb(4)Bd上述例子中句子abbcde的规范归约过程是:abbcde,aAbcde,aAcde,aAcBe,S练习使用下述文法对句型i1*i2+i3进行规范规约:ET
18、E+TTF
19、T*FFi
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))