编译原理清华大学第6章自底向上优先法素材

第6章自底向上优先分析(Bottom-upParsing)6.1概述原理:在采用自左向右扫描，自底向上分析的前提下，该类分析方法是从输入符号串入手，通过反复查找当前句型的句柄（最左简单短语），并使用文法的产生式把句柄归约成相应的非终极符来一步步地进行分析的。最终把输入串归约成文法的开始符号，表明分析成功。所以，任何自底向上分析方法的关键就是要找出当前句型的句柄（或是他的变型），然后根据产生式判别将它归约成非终极符号。两种常用的分析方法：优先分析法和LR分析法。自底向上分析的一般过程：先设置一个寄存符号的栈，称为分析栈。其作用是用来记录分析的历史和指示分析的下一步动作。分析进行时，把输入符号一个一个地按扫描顺序移进栈中，当栈顶符号形成一个句柄（即为某产生式的右部）时，就进行一次归约，把栈顶构成句柄的那个符号串用相应的产生式左部符号来替换。接着再检查在栈顶是否又出现了新的句柄，则再进行归约，直至整个输入符号串处理完。最终如果栈顶为文法的开始符号，则所分析的输入符号串为合法的符号串，报告分析成功,否则，是不合格的符号串，报告错误。给定句型找句柄的步骤：短语简单短语句柄注意：短语、简单短语是相对于句型而言，一个句型可能有多个短语、简单短语，句柄只能有一个。句型的短语、简单短语和句柄定义给定文法G[Z],w=xuy∈V+，为该文法的句型,若Z==xUy,且U==u,则u是句型w相对于U的短语；若Z==xUy,且U==u,则u是句型w相对于U的简单短语。其中U∈VN，u∈V+，x,y∈V***＋直观理解：短语是前面句型中的某个非终结符所能推出的符号串。例：给定文法G：E→T|E+T|E－TT→F|T*F|T／FF→i|(E)符号串（T+i）*i－F是文法G的一个句型，求其短语、简单短语和句柄。EE－TT－TT*F－TF*F－T(E)*F－T(T+T)*F－T(T+F)*F－T(T+i)*F－T(T+i)*i－T(T+i)*i－T解：短语有8个：1.EE，E（T+i）*i－F则有：（T+i）*i－F2.ET－F，T（T+i）*i则有：（T+i）*i3.ET*i－F，T（T+i）则有：（T+i）4.E(E)*i－F，ET+i则有：T+i5.E(E+i)*i－F，ET则有：T6.E(T+F)*i－F，Fi则有：第一个i7.E(T+i)*F－F，Fi则有：第二个i8.E(T+i)*F－T，TF则有：F*+*+*+*+*+*+*+*+其简单短语有4个：1.E(E+i)*i－F,ET则有：T2.E(T+F)*i－F,Fi则有：第一个i3.E(T+i)*F－F,Fi则有：第二个i4.E(T+i)*F－T,TF则有：F句柄有1个：TEE－TTT*FF(E)FiE+TTFi用语法树求短语、简单短语和句柄的方法：1）每个句型都有一棵语法树；2）每棵语法树的叶（从左到右）组成一句型；3）每个子树的叶（从左到右）组成一短语；4）每个简单子树的叶（从左到右）组成一简单短语；5）最左简单子树的叶（从左到右）组成一句柄。例：考虑文法G(E)：E→E+T|TT→T*F|FF→i|(E)并假定输入串为（i+i)*i，考察自底向上的分析过程。分析过程图表：为了具体实现上的方便，统一约定以“#”作为输入串的左右分界符（开始和结束标志）。作为初始状态，先将符号串的开始标志“#”压入分析栈中，作为栈底符号，则分析过程为：步骤分析栈输入串动作1#(i+i)*i#移进2#(i+i)*i#移进3#(i+i)*i#归约4#(F+i)*i#归约5#(T+i)*i#归约6#(E+i)*i#移进7#(E+i)*i#移进8#(E+i)*i#归约9#(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#接受分析过程图表：步骤分析栈输入串动作1#(i+i)*i#移进2#(i+i)*i#移进3#(i+i)*i#归约4#(F+i)*i#归约5#(T+i)*i#归约6#(E+i)*i#移进7#(E+i)*i#移进8#(E+i)*i#归约9#(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。判定候选式是极为简单的事情，但判定句柄就不那么容易。而不同的自底向上方法给出不同的判定方法。从上述例子可知，自底向上方法主要包括以下四个动作：移进：把输入流的头符读到分析栈中。归约：把分析栈顶的句柄归约为一非终极符。接受：分析成功。报错：处理错误。6.2简单优先方法(Simple-precedenceParsing)6.2.1概述简单优先方法是一种简单直观，广为使用的自底向上的分析方法，它是经由算符优先方法变化而来的。这种方法特别有利于分析表达式。大家知道，在做算术式的四则运算时，为了保证计算过程和结果的唯一性，人们作了统一的四则运算规则的规定。这个法则的主要方面就是规定运算符之间的优先顺序。即先乘除后加减，同优先级的运算符先左后右（左结合律）。还有先括号内后括号外的规定。而简单优先方法就是根据上述算术运算的计算过程而设计的一种语法分析方法。这种方法的基本思想为：首先规定文法符号之间的优先关系和结合性质，然后在利用这种关系，通过比较句型中两个相邻的符号之间的优先顺序来确定句型的“句柄”并进行归约。6.2.2相邻关系：设Si和Sj是文法G的任意两个符号，那么它们在句型中可相邻出现的充要条件是必须满足下列条件之一：1、有形如U→…SiSj…的产生式2、有形如U→…SiW…的产生式，且有WSj…+3、有形如U→…VSj…的产生式，且有V…Si+4、有形如U→…VW…的产生式，且有V…Si和WSj…++(1)有形如U→…SiSj…的产生式Uα…SiSj…βSαUβα…SiSj…β图6.1采用U→…SiSj…的推导+Sj…Uα…SiW…β图6.2采用U→…SiW…的推导(2)有形如U→…SiW…的产生式，且有WSj…+SαUβα…SiW…βα…SiSj…β++…SiUα…VSj…β图6.3采用U→…VSj…的推导(3)有形如U→…VSj…的产生式，且有V…Si+SαUβα…VSj…βα…SiSj…β++…SiUα…VW…βSj…图6.4采用U→…VW…的推导(4)有形如U→…VW…的产生式，且有V…Si和WSj…++SαUβα…VWj…βα…SiSj…β++6.2.3优先关系：为了把上述条件加以形式化，引进三种优先关系。其定义如下：当且仅当存在形如下面的产生式U→…SiSj…SiSj＝﹒当且仅当存在形如下面的产生式U→…SiW…的生产式，且有WSj…SiSj+﹒﹤当且仅当存在形如下面的产生式U→…VW…的生产式,且有V…Si和WSj…SiSj+*﹥﹒在实际使用这些优先关系去识别句子时，我们希望采用一种简洁的方法去表示这些关系，优先关系矩阵是一种常用的方式。其定义为：例：设有文法Gz：Z→bMbM→a︱(LL→Ma)则可根据定义求出其优先矩阵来（如下）M〔Si，Sj〕=空当Si与Sj无关系(不相邻出现)时当SiSj当SiSj当SiSj＝﹒﹒﹤﹥﹒＝﹒﹒﹤﹥﹒优先关系矩阵：Z→bMbM→a︱(LL→Ma)ZbMbaZbMb(LZbMb(LMa)＞＞)=＞＞a＜＜＜(＜＜=b＞＞L==MZZMLb(a)...............=.构造优先关系矩阵的一种简便方法：STEP1对每个非终极符W求下面两种集合：STEP2对每个符号对Si,Sj填写优先关系矩阵元素(其中W,V∈VN):ZMLHEADb(,aM,(,aLASTb),L,a)如对Ga我们有：Z→bMbM→a︱(LL→Ma)M[Si,Sj]=，如果有U→…SiW…且Sj∈HEAD(W)M[Si,Sj]=，如果有U→…VW…,且有Si∈LAST(V)和Sj∈HEAD(W)∪{W}M[Si,Sj]=，如果有U→…SiSj…＝﹒﹒﹤﹥﹒HEAD(W)=｛S︱WS…,S∈(VNUVT)｝LAST(W)=｛S︱W…S,S∈(VNUVT)｝++6.2.4简单优先文法的分析方法：(1)简单优先文法的定义：定义：满足下面两个条件的文法称为简单优先文法：(1)任意两个符号至多成立一种优先关系。(2)任意两个产生式具有不同右部。为了处理方便，引进特殊符号#，并定义#S，S#(S∈VNUVT)﹒﹤﹥﹒(2)简单优先文法的句柄这个定理给我们提供确定句柄的一种方法。简单优先文法分析算法的主要思想是找出句柄并归纳之。而给定一个句型X，寻找它的句柄是这样进行的：从左向右进行扫描，每次只查看两个相邻的文法符号，并由此得知什么时候查到句柄的尾Sj，然后再返过头来向句型左端进行加工，仍然只查看相邻的两个运算符，找出句柄的头Si。此时就可以进行归约了。定理：设S1S2…Sn是简单优先文法的规范句型，其子串SiSi+1…Sj是满足下列条件的最左子串：则SiSi+1…Sj定是S1S2…Sn的句柄。证明：略。Si-1SiSiSi+1Si+2…=SjSjSj+1｝＝﹒﹒﹤﹥﹒＝﹒＝﹒(3)分析算法的要点：STEP3:用SiSi+1…Sj去查产生式表的右部，并用相应的左部符号代替(归约)句柄Si…Sj，若查不到，则为出错。STEP4：重复上述过程，直至归约完为止。STEP2：从Sj开始往回(左)找第一个使Si-1Si的Si﹒﹤STEP1：找出第一个使SjSj+1的Sj﹥﹒(4)语法分析程序：首先设置保存句型前端的S栈和输入串后端的T队列；,然后用Sj1,Sj1+1,…Si去查生产式表，若查到有相同右部的产生式即USj1,Sj1+1,…Si,则从栈中退掉子串Sj1,Sj1+1,…Si，并把U进栈；然后转(2)。若查不到转出错处理。(5)若T(j)=‘#’,并且S栈的内容为#Z(Z为文法开始符号)则正确停机。否则，出错停机。(1)置初始状态：S(1):=‘#’,i:=1,j:=1(2)若S(i)与T(j)无任何关系，则出错停机。(3)若S(i)T(j)或S(i)T(j)，则把T(j)送入S栈中，读下一符，转（2）。＝﹒﹒﹤(4)若S(i)T(j)则从S栈顶开始往前栈串Sj1,Sj1+1,…,Si﹥﹒其中Sj1为第一个使Sj1-1Sj1﹒﹤此五部分是语法分析所涉及到的几部分分析栈和输入流中的内容合起来表示当前被归约的句型，每步的动作将由栈顶符号和当前的输入符的优先关系矩阵来确定，如果两种符号之间不存在优先关系，则表示输入符是错误的；而产生式表则用来确定归约时应选用的产生式。分析栈SSi输入流Tj语法分析程序优先关系矩阵产生式表6.3算符优先分析(Operator-precedenceParsing)算符优先分析的基本思想是只规定算符(广义为终结符)之间的优先关系，也就是只考虑终结符之间的优先关系，不考虑非终结符之间的优先关系。在归约过程中只要找到可归约串就归约，并不考虑归约到那个非终结符名，算符优先分析的可归约串不一定是规范句型的句柄，所以算符优先归约不是规范归约。算符优先分析的可归约串是当前符号栈中的符号和剩余的输入符号构成句型的最左素短语。例6.4:若有文法G为：(1)E→E+E(2)E→E*E(3)E→i考察对输入串i1+i2*i3的归约过程。解：归约过程见分析过程图表6.3：在分析到第6步时，栈顶的符号串为E+E，若只从移进-归约的角度讲，栈顶已出现了产生式(1)的右部，可以进行归约，但从通常四则运算的习惯来看应先乘后加，所以应移进，这就提出了算符优先的问题。例6.5:下面给出一个表达式的文法为：E→E+E|E－E|E*E|E/E