编译原理课件chap5.ppt

《编译原理课件chap5.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第五章语法分析——自下而上分析所谓自下而上分析法就是从输入串开始，逐步进行“归约”，直至归约到文法的开始符号；或者说从语法树的末端开始，步步向上“归约”，直到根结。5.1自下而上分析基本问题我们先讨论自下而上分析的一些基本思想和基本概念：5.1.1归约自下而上分析的关键问题是寻找可归约串。对“可归约串”概念的不同定义，就形成了不同的自下而上的分析方法。在算符优先分析法中我们用“最左素短语”来刻画“可归约串”，在“规范归约”中，则用“句柄”来刻画“可归约串”5.1.2规范归约简述在这一部分应掌握短语和直接短语和句柄三个重要概念第五章语法分析--自下而上分析令G是一个文法，S是文法的开始符，假定

2、是文法G的一个句型，如果有：S*A且A+则称是句型相对于非终结符A的短语。特别是，如果有A则称是句型相对于规则A的直接短语，一个句型的最左直接短语成为该句型的句柄。注意：短语的两个条件是：S*A且A+[例5.1]考虑文法：ET

3、E+TTF

4、T*FFi

5、(E)（5.2）对于句型i*i+i推导解：E→E+T→T+T→T*F+T→F*F+T→i*F+T→i*i+F→i*i+i第五章语法分析--自下而上分析尽管有E+i+i但是,i+i并不是该句型的一个短语，因为不存在从E(文法开始符）到i*E的推导。但是，i,i*i,和i*i+i自身都是句型i*

6、i+i的短语。而且为为直接短语。[例5。2]上题文法（5。2）的另一个句型E+T*F+i的短语有E+T*F+i,E+T*F,T*F,和i.其中T*F和i为直接短语，T*F为句柄。解：E→E+T→E+T+T→E+T*F+T→E+T*F+F→E+T*F+i第五章语法分析--自下而上分析关于规范归约精确的说，假定是文法G的一个句子，我们称序列nn-1n-2,。。。,0是的一个规范规约，如果此序列满足：（1）n=;(2）0为文法的开始符,即0=S;（3）对于任何的i，0

7、逆过程。因此规范归约也成最左归约。在形式语言中，最右推导常被称为规范推导。由规范推导所得的句型称为规范举行。如果文法G是无二义的，那么规范推导的逆过程必是规范归约。5.1.3符号栈的使用与语法树的表示本节重点掌握符号栈的使用请阅读P87相应段落。现在举个例子以加深对这一节的理解。第五章语法分析--自下而上分析[例5.3]：对于文法（5.2）输入串i1*i2+i3的分析（规范归约）步骤可表示如下：步骤符号栈输入串动作0#i1*i2+i3#预备#i1*i2+i3#读入i1#F*i2+i3#归约，Fi#T*i2+i3#归约，TF#T*i2+i3#读入#T*i2+i3#读入#T*F+i3#归约，F

8、i#T+i3#归约，TT*F#E+i3#归约，ET#E+i3#读入#E+i3#读入#E+F#归约,Fi#E+T#归约,TF#E#归约，EE+T#E#接受第五章语法分析--自下而上分析5.2算符优先分析5.2.1算符优先文法及优先表的构造一个文法，如果它的任何产生式的右部都不含量个相继（并列）的非终结符，即不含如下形式的产生式右部：…QR…则我们称该文法为算符文法。在后面的定义中，a、b代表任意终结符；P、Q、R代表任意非终结符；‘…’代表有终结符和非终结符组成的任意序列，包括空字。假定G是一个不含--产生式的算符文法。对于任何一对终结符a、b，我们说：（1)ab当且仅当文法G

9、中含有形如P…ab…或P…aQb…的产生式;(2)a<b当且仅当G中含有形如P…aR…的产生式，R而R+b…或R+Qb…;(3)a>b当且仅当G中含有形如P…Rb…的产生式，R而R+…a或R+…aQ;第五章语法分析--自下而上分析如果一个文法G中的任何终结符对（a,b）至多只满足下述三关系之一：a=·b,a<·b,a·>b则称G是一个算符优先文法。应掌握算符优先表的构造方法。通过检查G的每个产生式的每个候选式，可以找出满足a=·b的终结符对。为了找出所有满足关系<·和·>的终结符对，我们需要对G的每个非终结符P构造两个集合FIRSTVT(P)和LASTVT(P):FIRST

10、VT(P)={a

11、P+a…或P+Qa…,aVT而QVN}LASTVT(P)={a

12、P+…a或P+…aQ,aVT而QVN}有了这两个集合后，就可以通过检查每个产生式的候选式确定满足关系<·和·>的所有终结符对。例如：假定有个产生式的一个候选式为…aP…那末，对任何bFISTVT(P),我们有a<·b。类似地，假定有产生式的一个候选式为第五章语法分析--自下而上分析…Pb…那末，对任