编译原理自下而上语法分析.ppt

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

1、自下而上语法分析掌握自底相上分析的基本思想，基本概念掌握算符优先关系的判定，求FIRSTVT集,LASTVT集,构造算符优先关系表，能运用算符优先分析方法进行表达式分析掌握最左素短语、句柄的定义与判定理解规范规约与算符优先归约的区别LR(0)和SLR文法的理解自下而上的语法分析实现思想从输入符号串开始，从左到右进行扫描，将输入符号逐个移入一个栈中，边移入边分析，一旦栈顶符号串形成某个产生式的右部时，就用该产生式的左部非终结符代替，称为归约。重复这一过程，直到归约到栈中只剩下文法的开始符号时，则分

2、析成功，称为“移进-归约”方法。从语法树的角度看：从语法树的树叶开始，逐步向上归约构造分析树，直到形成根结。是推导的逆过程。核心寻找可归约串(这是关键)进行规约。用不同的方法寻找可归约串，就可获得不同的分析方法。最左推导(Left-mostDerive)每次推导都替换当前句型的最左边的非终结符。——与最右归约对应最右推导(Right-mostDerive)每次推导都替换当前句型的最右边的非终结符。——与最左归约(规范归约)对应，得规范句型例：设有文法G[S]：(1)SaAcBe(2)Ab(

3、3)AAb(4)Bd使用最右推导：因为S=>aAcBe=>aAcde=>aAbcde=>abbcde，所以abbcde是文法G的句子。步骤动作(1)SaAcBe(2)Ab(3)AAb(4)Bd最左归约过程是最右推导的逆过程，对输入串abbcde的归约过程如下：该分析过程反复执行“移进”和“归约”两个动作，直到栈中只有开始符号为止。abaAabAaAacAadcAaBcAaeBcAaS1移进a2移进b3归约24移进b5归约36移进c7移进d8归约49移进e10归约1语法分析树的生成演

4、示abbcdeAABSA→bA→AbB→dS→aAcBe(1)SaAcBe(2)Ab(3)AAb(4)Bd这种分析过程具有如下特点：从输入串的开始依次读入单词(移进栈中)。一旦发现可归约串(某个产生式的右端)就立即归约。归约就是将栈顶的一串符号用文法产生式的左部代替，归约可能重复多次，然后继续移进。若最终能归约成文法的开始符号，则分析成功。关键是如何判断可归约串？问题的提出：①在构造语法树的过程中，何时归约？当可归约串出现在栈顶时就进行归约。②如何知道在栈顶符号串中已经形成可归约串？如

5、何进行归约？通过不同的自底向上的分析算法来解释，不同的算法对可归约串的定义是不同的，但分析过程都有一个共同的特点：边移进边归约。规范归约：使用句柄来定义可归约串。算符优先：使用最左素短语来定义可归约串规范归约概念有文法G，开始符号为S,如果有S=>xβy,则xβy是文法G的句型，x,y是任意的符号串如果有S=>xAy,且有A=>β,则β是句型xβy相对于非终结符A的短语如果有S=>xAy,且有A->β,则β是句型xβy相对于A->β的直接短语位于一个句型最左边的直接短语称为句柄。**+*注:每次

6、归约的部分必须是称之为句柄的字符串(最右推导)。关键的问题是如何识别句柄例子下面的例子说明作为短语的两个条件缺一不可。[例]考虑表达式文法：ET

7、E+TTF

8、T*FFi

9、(E)对于句型i*i+i推导EE+TE+FE+iT+iT*F+TT*i+iF*i+ii*i+i尽管有E+i+i但是,i+i并不是该句型的一个短语，因为不存在从E(文法开始符）到i*E的推导。句型的短语和句柄举例文法：S→(T)

10、εT→S

11、T,S

12、a短语：句型((a),S)S=*>(T,S)T=+>(a)句

13、型((T,S),S)S=*>((T),S)T=+>T,S句型(a,(T),(T,S))直接短语以及句柄：S=*>(T,(T),(T,S))T=>aS=*>(a,S,(T,S))S=>(T)S=*>(a,(T),(T))T=>T,S短语与语法树的关系短语：语法树子树的叶子结点组成的符号串。直接短语：语法树简单子树（只有父子两代）的叶子结点组成的符号串。句柄：语法树最左边简单子树的叶子结点组成的符号串。短语与语法树关系的例子句型(a,(T),(T,S))的语法树：S()TTS,T,S(T)a(T)T

14、,S用句柄对句子abbcde进行归约用句柄对句子进行归约的过程与用移进-归约过程是一致的，使用归约的产生式及其顺序是一致的。句型归约规则abbcde(1)SaAcBe(2)Ab(3)AAb(4)Bd(2)Ab(3)AAbaAbcdeaAcde(4)Bd(1)SaAcBeaAcBeS规范归约的定义假定α是文法G的一个句子，如果序列：αn,αn-1,……,α0(=S)满足如下条件，则序列αn,αn-1,……,α0是一个规范归约:(1)αn=α是给定的句子(2)α0=S是文法的开始符