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

编译原理长春工业大学计算机科学与工程学院自下而上语法分析掌握自底相上分析的基本思想，基本概念掌握算符优先关系的判定，求FIRSTVT集,LASTVT集,构造算符优先关系表，能运用算符优先分析方法进行表达式分析掌握最左素短语、句柄的定义与判定理解规范规约与算符优先归约的区别LR(0)和SLR文法的理解编译原理长春工业大学计算机科学与工程学院自下而上的语法分析实现思想从输入符号串开始，从左到右进行扫描，将输入符号逐个移入一个栈中，边移入边分析，一旦栈顶符号串形成某个产生式的右部时，就用该产生式的左部非终结符代替，称为归约。重复这一过程，直到归约到栈中只剩下文法的开始符号时，则分析成功，称为“移进-归约”方法。从语法树的角度看：从语法树的树叶开始，逐步向上归约构造分析树，直到形成根结。是推导的逆过程。核心寻找可归约串(这是关键)进行规约。用不同的方法寻找可归约串，就可获得不同的分析方法。编译原理长春工业大学计算机科学与工程学院最左推导(Left-mostDerive)每次推导都替换当前句型的最左边的非终结符。——与最右归约对应最右推导(Right-mostDerive)每次推导都替换当前句型的最右边的非终结符。——与最左归约(规范归约)对应，得规范句型例：设有文法G[S]：(1)SaAcBe(2)Ab(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编译原理长春工业大学计算机科学与工程学院语法分析树的生成演示abbcdeAABSA→bA→AbB→dS→aAcBe(1)SaAcBe(2)Ab(3)AAb(4)Bd编译原理长春工业大学计算机科学与工程学院这种分析过程具有如下特点：从输入串的开始依次读入单词(移进栈中)。一旦发现可归约串(某个产生式的右端)就立即归约。归约就是将栈顶的一串符号用文法产生式的左部代替，归约可能重复多次，然后继续移进。若最终能归约成文法的开始符号，则分析成功。关键是如何判断可归约串？编译原理长春工业大学计算机科学与工程学院问题的提出：①在构造语法树的过程中，何时归约？当可归约串出现在栈顶时就进行归约。②如何知道在栈顶符号串中已经形成可归约串？如何进行归约？通过不同的自底向上的分析算法来解释，不同的算法对可归约串的定义是不同的，但分析过程都有一个共同的特点：边移进边归约。规范归约：使用句柄来定义可归约串。算符优先：使用最左素短语来定义可归约串编译原理长春工业大学计算机科学与工程学院规范归约概念有文法G，开始符号为S,如果有S=xβy,则xβy是文法G的句型，x,y是任意的符号串如果有S=xAy,且有A=β,则β是句型xβy相对于非终结符A的短语如果有S=xAy,且有A-β,则β是句型xβy相对于A-β的直接短语位于一个句型最左边的直接短语称为句柄。**+*注:每次归约的部分必须是称之为句柄的字符串(最右推导)。关键的问题是如何识别句柄编译原理长春工业大学计算机科学与工程学院例子下面的例子说明作为短语的两个条件缺一不可。[例]考虑表达式文法：ET|E+TTF|T*FFi|(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)|εT→S|T,S|a短语：句型((a),S)S=*(T,S)T=+(a)句型((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,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是文法的开始符号(3)对任何i,0in，αi-1是从αi经把句柄替换为相应文法产生式的左部符号而得到的。规范归约是最右推导的逆过程，规范归约又称为最左归约。最右推导又称规范推导，由规范推导所得到的句型称规范句型，规范推导的逆过程是规范归约。编译原理长春工业大学计算机科学与工程学院使用修剪语法树的方法来进行归约：SaAcBeAbdSaAcBeAbbdSaAcBe编译原理长春工业大学计算机科学与工程学院分析器的四种动作移进：将下一输入符号移入栈归约：当栈顶出现句柄，用产生式左侧的非终结符替换栈顶的句柄接受：分析成功，是归约的一种特殊情况出错：栈顶的内容与输入符号相悖，进行出错处理编译原理长春工业大学计算机科学与工程学院分析成功的条件：栈顶为文法符号，输入串为空。注意，该过程并未涉及如何在栈里找可归约串。实际上，不同的找可归约串的方法，构成了不同的分析算法。“移进-归约”分析法用栈实现的特点：可归约串必定位于栈顶，即可归约串之后就是剩余的输入串。栈内符号串与剩余输入串正好构成一个句型。编译原理长春工业大学计算机科学与工程学院例：有文法：(1)E-E+T|T(2)T-T*F|F(3)F-(E)|i对输入串i1+i2*i3的规范归约过程：编译原理长春工业大学计算机科学与工程学院动作栈输入缓冲区1)准备#i1+i2*i3#2)移进#i1+i2*i3#3)归约F→i#F+i2*i3#4)归约T→F#T+i2*i3#5)归约E→T#E+i2*i3#6)移进#E+i2*i3#7)移进#E+i2*i3#8)归约F→i#E+F*i3#9)归约T→F#E+T*i3#10)移进#E+T*i3#11)移进#E+T*i3#12)归约F→i#E+T*F#13)归约T→T*F#E+T#14)归约E→E+T#E#15)接受所得的结果是：用产生式序列表示语法分析树(1)E-E+T|T(2)T-T*F|F(3)F-(E)|ii1+i2*i3FTEFTFTE编译原理长春工业大学计算机科学与工程学院算符优先分析算符优先分析法的思想源于表达式的分析，即利用相邻终结符号之间的关系来寻找可归约串。将句型中的终结符号当作“算符”，借助于算符之间的优先关系确定可归约串。显然，在一个符号串中，任意两个相邻终结符号a和b之间，只可能存在以下四种优先关系：(1)a,b优先性相同，记作ab。(2)a优先性高于b，记作ab。(3)a优先性低于b，记作ab。(4)a与b不可能相邻，即此符号串不是句型(出错)。如果以上四种关系中的任意两种都不会同时成立，则可以根据终结符号之间的归约关系进行语法分析。编译原理长春工业大学计算机科学与工程学院算符文法:一个上下无关文法G,如果没有P-,且没有P-...QR...(P,Q,R属于非终结符),则G是一个算符文法。算符优先关系的定义：ab,G中有P-...ab...或P-...aQb...(在同一产生式中)ab,G中有P-...aR...的产生式,且R=b...或R=Qb...ab,G中有P-...Rb...的产生式,且R=...a或R=...aQ算符优先文法（OPG）的定义++++编译原理长春工业大学计算机科学与工程学院例：E→E+E|E*E|(E)|i证明不是OPG文法。因为：E→E+E，EE*E则有+*又因为：E→E*E,EE+E则有+*所以不是算符优先文法。算符优先文法算符文法G的任何终结符a,b之间要么没有优先关系，若有优先关系,至多有,,中的一种成立,则G为一算符优先文法。编译原理长春工业大学计算机科学与工程学院算符优先关系表的构造FIRSTVT集定义：对每个非终结符P,FIRSTVT(P)={a|P=a...或P=Qa...,a为终结符,P，Q为非终结符}++由优先性低于的定义和FIRSTVT集合的定义可以得出：若存在某个产生式：…aP…，对所有：b∈FIRSTVT(P)，都有：ab。按照下面两条规则来构造FIRSTVT集：①若有产生式P-a...或P-Qa...,则a∈FIRSTVT(P)②若有产生式P-R...,则FIRSTVT(R)包含在FIRSTVT(P)中编译原理长春工业大学计算机科学与工程学院LASTVT集定义：对每个非终结符P,LASTVT(P)={a|P=...a或P=...aQ,a为终结符,P，Q为非终结符}++由优先性高于的定义和LASTVT集合的定义可以得出：若存在某个产生式：…Pb…，对所有：a∈LASTVT(P)，都有：ab。按照下面两条规则来构造LASTVT集：①若有产生式P-...a或P-...aQ,则a∈LASTVT(P)②若有产生式P-...R,则LASTVT(R)包含在LASTVT(P)中编译原理长春工业大学计算机科学与工程学院构造优先关系表如果每个非终结符的FIRSTVT和LASTVT集均已知,则可构造优先关系表。若产生式右部有...aP...的形式,则对于每个b∈FIRSTVT(P)都有ab若产生式右部有...Pb的形式,则对于每个a∈LASTVT(P)集,都有ab若产生是形如：A→…ab…或A→…aBb…形式，则有ab构造优先关系表的算法如下：编译原理长春工业大学计算机科学与工程学院For每条形如PX1X2…Xn的产生式dofori=1ton-1do{ifXi和Xi+1都是终结符thenXi=Xi+1ifi=n-2且xi和Xi+2都是终结符,Xi+1为非终结符thenXi=Xi+2ifXi为终结符,Xi+1为非终结符thenforfirstVT中的每个元素adoXiaifXi为非终结符,Xi+1为终结符thenforlastVT中的每个元素adoaXi+1}编译原理长春工业大学计算机科学与工程学院算符优先分析算法通过比较终结符间的优先关系来实现根据优先分析的原理，语法分析程序的任务是：不断移进输入符号，识别可归约串并进行归约。分析的方法：根据优先性“高于”来识别可归约串的头，根据优先性“低于”来识别可归约串的尾。各种优先关系已经存于优先关系表中。编译原理长春工业大学计算机科学与工程学院不能识别只由一个非终结符组成的句柄。不能保证每次对句柄进行归约,在算符优先分析过程中,每次归约的符号串,是当前句型的最左素短语。素短语：至少含有一个终结符,且除自身外,不再包含任何其它更小的素短语。最左素短语(leftmostprimephrase)：是指位