编译原理自底向上的语法分析2

自底向上分析方法概述自底向上分析是最右推导的逆过程，从构造语法树的观点来讲,是指从树的末端结点开始，逐步向上归约，直至树的根结点，也就是说，从输入串本身开始，朝着开始符号进行归约。直至到达开始符号为止。确定的自底向上分析器通常分为两大类：优先分析器(PrecedenceParser)和LR(k)分析器。4.3自底向上分析的一般原理1自底向上分析的基本思想对于给定语言的文法，自底向上分析的基本思想是：自左向右逐个扫描输入串，一边把输入符号移入分析栈内，一边检查位于栈顶的一串符号是否与某个产生式的右部相同。如果发现相同，就把栈顶符号替换为相应产生式左部的符号，并继续进行判断，上述过程一直重复到输入串已结束，而栈顶恰好为文法的开始符号。2.自底向上分析的过程:移进—归约法移进:一边分析一边往栈里移符号归约:是在栈顶形成可规约串时进行的可规约串:(1)句柄(LR分析法)(2)最左素短语(算符优先分析法)3.移进–归约分析器算法:这个分析器设置了一个符号栈和一个输入缓冲区。设当前输入符号串为。初始状态:栈和输入缓冲区的格局为在符号栈里先放置一个“#”号，输入符号串之后跟着一个“#”号，作为输入符号串的结束符。句子的分析过程：将的符号从左到右逐个移进符号栈，一旦栈顶符号串与某一个产生式右部相匹配成为一个可归约符号串时，则将此符号串归约为一个非终结符，这个非终结符是该产生式左部符号。的符号继续逐个移进符号栈，当栈顶又形成一个可归约的符号串时，则又可将此符号串归约为某一个产生式左部非终结符。结束条件：Z是开始符号，则分析成功，说明符号串是文法的一个句子。如果得不到以上格局，则表明符号串不是文法的句子，存在语法错误。自下而上分析法的主要问题是：如何寻找一个规范句型的句柄以及找到这样的句柄后如何规约它(选用哪个产生式来进行归约)。这正是本章和下章中试图解决的问题。移进-归约过程图4.举例:P69[例4.11]设文法G[A]：1A→aBcDe2B→b3B→Bb4D→d对输入串abbcde进行自底向上的语法分析,检查该符号串是否合法.句子abbcde$分析过程（１页）c进栈cde$$aB5b进栈cde$$aBb4B→b规约bcde$$aB3b进栈bcde$$ab2a进栈bbcde$$a1abbcde$$0动作输入串分析栈步骤B→Bb规约句子abbcde$分析过程(2页)分析成功$$A10e进栈$$aBcDe9e$$aBcD8d进栈e$$aBcd7de$$aBc6所用规则输入串分析栈步骤D→d规约A→aBcDe规约5.结论:在自底向上分析的过程中，如果语法分析程序每次只能面临一种动作选择，要么移进、要么归约，那么这个分析过程就是确定的。如果归约的时候发生冲突,就会发生错误的归约，从而使语法分析无法进行下去。错误归约造成语法分析程序做许多“无用功”，降低了分析效率。造成错误归约的原因是错误地识别了句柄。因此在自底向上分析中，最关键的问题是如何识别句柄。在规范归约分析法中:使用句柄来刻画可归约串;算符优先分析法中:使用最左素短语刻画可归约串。所以，根据可归约串的不同识别方法形成不同的自底向上的语法分析方法简单优先法:是根据文法符号间的优先关系来确定栈顶符号串是否形成最左素短语LR分析法:采用规范句型的活前缀来标识栈顶符号串句柄的形成状态。若形成就规约。复习短语和句柄定义6.1设S是文法G的识别符号，w=xUy是其中的句型，若则称子串是句型xy相对于非终结符U的短语。其中，UVN；x，y(VN∪VT)*。此外，如果有则称子串是句型xy相对于非终结符U的直接短语或简单短语。一个句型的最左直接短语，称为该句型的句柄(Handle),句柄的最右符号称为该句柄之尾。一个规范句型的句柄的右边只包含终结符号。语法树与短语的关系密切。由此，引出下述结论：每个句型(句子)都对应一颗语法树；每颗语法树的末端结点自左至右排列构成一个句型(句子)；每颗子树的末端结点自左至右排列构成一短语；每颗直接子树的末端结点自左至右排列构成一简单短语；最左简单子树的末端结点左至右排列构成一句柄。最左素短语①是一个短语②至少包含一个终结符号③除自身外不再包含其它素短语。例:算术表达式文法G[E]：E→E+TTT→T*FFF→(E)i求句型T+T*F+i的短语、句柄、素短语例1已知句型句型T+T*F+i的语法树如图:短语是：①T+T*F+i②T+T*F③i④T⑤T*F简单短语：①T*F②T③i句柄:T素短语：T*F，i最左素短语：T*FS+ETET+TTFiT*F例2已知句型(a，(T)，(T，S))语法树如右图:短语是：①(a，(T)，(T，S))②a，(T)，(T，S)③a，(T)④(T，S)⑤a⑥(T)⑦T，S简单短语：①a②(T)③T，S句柄：a素短语：①a②(T)③T，S最左素短语：aST()，TS，TST()aT()，TS6.3算符优先分析方法1.方法概述所谓算符优先分析法就是依照算术表达式的四则运算过程而设计的一种语法分析方法,首先要规定运算符之间(确切的说是终结符号之间)的优先关系和结合性质,然后借助这种关系,比较相临两运算符之间的优先级来确定句形的可归约串并进行归约。例如：表达式的文法：G[E]E→E+E|E-E|E*E|E/E|(E)|i文法具有二义性，有不同的规范推导。因而就有不同的规范规约（句柄不是唯一的）。例如：分析句子i+i*i有不同的规范规约，句柄不唯一。1）i+i*i2）E+i*i3）E+E*i4）E+E*E5）E+E6）E1）i+i*i2）E+i*i3）E+E*i4）E*i5）E*E6）E规约过程如下但是若采用算符优先顺序和结合原则的规定，并按这种原则进行规约，那么该句子的规约过程是唯一的。例如我们按先乘除、后加减，同级左结合，有括号先算括号内的，另外规定i的优先级高于其它运算符。可以看出上述规约过程起决定作用的是两个终结符的优先关系，并且归约过程是唯一的。因此算符优先分析法解决了两个问题：（1）（根据优先关系）唯一地确定了句柄。（2）可以分析二义性的文法。（规定的优先关系是避免二义性的条件）2.算符优先文法1．算符文法（OG）：产生式的右部没有两个非终结符直接相邻，中间总有一种运算符相隔，因而可用来描述表达式，这样的文法称为算符文法。2．算符优先文法（OPG）：规定了算符文法当中各终结符号之间的规约先后次序。①是一个算符文法，不含ε产生式②定义了相邻两个终结符号之间的优先关系2.算符优先文法及优先表构造一个文法，如果它的任一产生式的右部都不含两个相继(并列)的非终结符，即不含如下形式的产生式右部：…QR…则我们称该文法为算符文法。约定：a、b代表任意终结符；A、T、R代表任意非终结符；‘…’代表由终结符和非终结符组成的任意序列，包括空字。文法中任何一对终结符a、b，优先关系有四种：1)a=b当且仅当文法G中含有形如A→…ab…或A→…aTb…的产生式（直接相邻）；2)ab当且仅当G中含有形如A→…aT…的产生式，而Tb…或TRb…；3)ab当且仅当G中含有形如A→…Tb…的产生式，而T…a或T…aR。以上为a,b相邻（2、3为间接相邻）。4)a,b无关系。没有S=…ab…或S=…aTb…的产生式（直接相邻）；算符文法中任何两个可能相邻出现的终结符a与b的优先关系三种关系aba的优先级低于ba=ba的优先级等于baba的优先级高于b注意：与数学上的=不同++ab并不意味着ba，如(+和+(算符优先文法的完整定义：P70①a=b当且仅当直接存在产生式A→…ab…或A→…aTb…；②ab当且仅当直接存在产生式A→…aT…，且T=b…或T=Rb…；③ab当且仅当直接存在产生式A→…Tb，且T=…a或T=…aR；④a与b无关系，当且仅当a与b在任何句型中都不相邻。如果假定G是一个不含ε产生式的算符文法一个算符文法G中的任何终结符对(a，b)至多只满足上述四种关系之一：ab，ab，a=b，ab无关系则称G是一个“算符优先文法”。3.算符优先矩阵：在对算符优先文法进行分析的时候，语法分析程序随时都要比较两相邻终结符号之间的优先关系，识别当前句型的最左素短语。为了方便起见，通常用矩阵的形式存放文法中各种可能的关系。矩阵是n*n的，n是文法中终结符的个数。例:算术表达式文法G[E]：E→E+TTT→T*FFF→(E)i文法G（E）的优先矩阵从算符优先文法G构造优先关系表的算法。1)通过检查G的每个产生式的每个候选式，可找出所有满足a=b的终结符对。2.ab当且仅当G中含有形如T→…aA…的产生式，而Ab…或ABb…；3.ab当且仅当G中含有形如T→…Ab…的产生式，而A…a或A…aB。2)确定满足关系和的所有终结符对：1.a=b当且仅当文法G中含有形如A→…ab…或A→…aTb…的产生式；},,|{)(NTVBVaBaAaAaAFIRSTVT而或},,|{)(NTVBVaaBAaAaALASTVT而或}...,|{=)(*TVaaaFIRST比较}...,...|{)(*TVaAaSaAFOLLOW比较非终结符A构造两个集合FIRSTVT(A)和LASTVT(A)有了这两个集合之后，就可以通过检查每个产生式的候选式确定满足关系和的所有终结符对。1)假定有个产生式的一个候选形为…aA…那么，对任何bFIRSTVT(A)，有ab。2)假定有个产生式的一个候选形为…Ab…那么，对任何aLASTVT(A)，有ab。首先讨论构造集合FIRSTVT(A)的算法。按其定义，可用下面两条规则来构造集合FIRSTVT(A)：1.若有产生式A→a…或A→Ba…，则aFIRSTVT(A)；2.若aFIRSTVT(B)，且有产生式A→B…，则aFIRSTVT(A)。},,|{)(NTVBVaBaAaAaAFIRSTVT而或构造集合LASTVT(A)的算法。按其定义，可用下面两条规则来构造集合LASTVT(A)：1.若有产生式A→…a或A→…aB，则aLASTVT(A)；2.若aLASTVT(B)，且有产生式A→…B，则aLASTVT(A)。},,|{)(NTVBVaaBAaAaALASTVT而或使用每个非终结符A的FIRSTVT(A)和LASTVT(A)，就能够构造文法G的优先表。构造优先表的算法是：FOR每条产生式A→X1X2…XnDOFORi:=1TOn-1DOBEGINIFXi和Xi+1均为终结符THEN置Xi=Xi+1IFin-2且Xi和Xi+2都为终结符但Xi+1为非终结符THEN置Xi=Xi+2；IFXi为终结符而Xi+1为非终结符THENFORFIRSTVT(Xi+1)中的每个aDO置Xia；IFXi为非终结符而Xi+1为终结符THENFORLASTVT(Xi)中的每个aDO置aXi+1END例4.12:算术表达式文法G[E]：E→E+TTT→T*FFF→(E)id求每个非终结符的FIRSTVT集和LASTVT集FIRSTVT（E）+∈FIRSTVT（E）FIRSTVT（T）∈FIRSTVT（E）FIRSTVT（T）*∈FIRSTVT（T）FIRSTVT（F）∈FIRSTVT（T）FIRSTVT（F）（∈FIRSTVT（F）id∈FIRSTVT（F）得出FIRSTVT集FIRSTVTLASTVTE{*，+，（，id}T{*,(,id}F{(,id}LASTVT（E）+∈LASTVT（E）LASTVT（T）∈LASTVT（E）LASTVT（T）*∈LASTVT（T）LASTVT（F）∈LASTVT（T）LASTVT（F））∈LASTVT（F）id∈L