语法分析-自下而上分析.ppt

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

1、第五章语法分析-自下而上分析5.1自下而上分析的基本问题Figure5.5LR演示自下而上分析i+(i+i)*i原理:自左向右扫描，自下而上分析从输入符号串入手，通过反复查找当前句型的可归约串，并使用文法的产生式把它归约成相应的非终结符来一步步地进行分析的。最终把输入串归约成文法的开始符号，表明分析成功。任何自下而上分析方法的关键就是要找出当前句型的可归约串，然后根据产生式判别将它归约成什么样的非终结符。规范归约基本概念如果A=>β，则称β是句型αβδ相对于非终结符A的直接短语。G为文法，S为开始符号，假

2、定αβδ是G的一个句型，如果则称β是句型αβδ相对于非终结符A的短语。表达式文法的例子i+i*i,找出所有短语，直接短语和句柄最左直接短语称为句柄。从句子到开始符号的归约序列，如果每一步都是把句柄替换为相应产生式的左部符号而得到的，则称为规范归约。规范归约是最右推导（规范推导）的逆过程。例：考虑文法G(E)：E→E+T

3、TT→T*F

4、FF→i

5、(E)并假定输入串为（i+i)*i，考察自下而上的分析过程。分析过程图表：步骤分析栈输入串动作#(i+i)*i#移进#(i+i)*i#移进#(i+i)*i#归约

6、#(F+i)*i#归约#(T+i)*i#归约#(E+i)*i#移进#(E+i)*i#移进#(E+i)*i#归约#(E+F)*i#归约步骤分析栈输入串动作10#(E+T)*i#归约11#(E)*i#移进12#(E)*i#归约13#F*i#归约14#T*i#移进15#T*i#移进16#T*i#归约17#T*F#归约18#T#归约19#E#接受栈上的候选式不一定是句柄。例如，在第14步对栈顶为T，它是E的一候选式，但它不是句柄，不能归约成E。判定候选式是极为简单的事情，但判定句柄就不那么容易。而不同的自底向上方

7、法给出不同的判定方法。自下而上方法包括四个动作：移进：把输入流的头符读到分析栈中。归约：把分析栈顶的句柄归约为一非终极符。接受：分析成功。报错：处理错误。首先规定文法符号之间的优先关系和结合性质，然后再利用这种关系，通过比较两个相邻的符号之间的优先顺序来确定可归约串。算符文法：任何产生式的右部都不含两个相继的非终结符5.2算符优先分析例：考虑文法G(E)：E→E+T

8、TT→T*F

9、FF→i

10、(E)是否是算符文法？优先关系：终结符ab的三种优先关系：当且仅当存在形如下面的产生式U→…ab…或U→…aQb

11、…当且仅当存在形如下面的产生式U→…aW…的生产式，且有Wb…当且仅当存在形如U→…Vb…的产生式且有V…a或V…aQababab如果一个算符文法的任何终结符对至多只满足三种关系之一，称为算符优先文法。验证终结符对之间的优先关系(p90优先表)例：考虑文法G(E)：E→E+T

12、TT→T*F

13、FF→i

14、(E)是否是算符优先文法？如何从文法构造优先关系表？检查文法产生式的每个候选，可找出所有满足的终结符对。如何找出满足和终结符对？对每个非终结符P构造两个集合FIRSTVT(P)和LASTVT(P)FIRS

15、TVT(P)=LASTVT(P)=检查每个产生式候选，若形为...aP...,则对任何b∈FIRSTVT(P)，我们有ab。若形为...Pb...,则对任何a∈LASTVT(P)，我们有ab。对表达式文法的非终结符构造FIRSTVT和LASTVT并建立优先关系表算符优先分析算法素短语：这样的一个短语，它至少含一个终结符，不含比自身更小的素短语。最左素短语：句型最左边的素短语。定理：算符优先文法的句型#N1a1N2a2...NnanNn+1#的最左素短语是满足如下条件的最左子串Njaj...NiaiNi+1

16、aj-1ajajaj+1...aiaiai+1演示SuanFuYouXian优先函数利用两个函数f和g，对每个终结符θ，映射为两个数f(θ)和g(θ)，使得：若θ1θ2则f(θ1)g(θ2)有的关系表不存在优先函数！对于存在优先函数的关系表，如何构造优先函数？请自学p94~95优先函数的构造方法。5.3LR分析法1965年，D.knuth首先提出了LR(K)文法及LR(K)分析技术。LR(K)分析是指自左向右扫描和自下而上的语法分析，且

17、在分析的每一步，只须根据分析栈中当前已移进和归约出的全部文法符号，并至多再向前查看K个输入符号，就能确定相当于某一产生式右部符号的句柄是否已在分析栈的顶部形成。从而也就可以确定所应采取的分析动作（是移进输入符号还是按某产生式进行归约）。当前扫描到Xn+1,向前查看k个符号，来确定是把Xn+1移进栈，还是把Xi…Xn作为句柄进行归约。1）要归约时，则根据某产生式U→XiXi+1…Xn进行归约：#X1X2…Xi-1UXn+1Xn+