ch6 自底向上算符优先语法分析.ppt

文档介绍：自底向上算符优先语法分析第6章*主要内容:规范归约,自上而下的算符优先分析方法及其相关概念。重点掌握:掌握自下而上分析的基本思想,规范规约的概念及过程;算符优先文法、算符优先关系的判定,最左素短语、句柄的定义与判定,构造算符优先关系表,能用算符优先分析法进行表达式分析。*G=({E},{i,+,*,(,)},P,E)P:EE+EEE*E E(E) Ei最左推导:EE*E(E)*E(E+E)*E(i+E)*E(i+i)*E(i+i)*i最右推导:EE*EE*i(E+E)*i(E+i)*i(i+i)*i例:判定输入串(i+i)*i是否是下述文法的句子?结论:自上而下语法分析采用最左推导,每一步推导使用哪个产生式要视当前非终结符匹配输入字符串中的哪个符号来确定。自下而上语法分析是最右推导的逆过程,由输入符号串反向推导到文法的开始符号。*自下而上的语法分析实现思想:“移进-归约”方法设置一个栈,将输入符号逐个移进栈中,栈顶形成某产生式的右部时(句柄),就用左部去代替,称为归约。重复这一过程,直到栈中只剩下文法的开始符号,就确认输入串是文法的句子,分析成功,否则出错。语法树:从树叶开始,逐步向上归约构造分析树,直到形成根结点。是推导的逆过程。核心寻找句柄进行规约。用不同的方法寻找句柄,就可获得不同的分析方法。*最左推导(Left-mostDerive)每一步推导都替换当前句型的最左边的非终结符。——其逆过程称为最右归约最右推导(Right-mostDerive)每一步推导都替换当前句型的最右边的非终结符。——其逆过程称为最左归约(规范归约),得规范句型例:设有文法G[S]:(1)SaAcBe(2)Ab(3)AAb(4)Bd使用最右推导:因为SaAcBeaAcdeaAbcdeabbcde,所以abbcde是文法G的句子。*步骤动作(1)SaAcBe(2)Ab(3)AAb(4)Bd最左归约过程是最右推导的逆过程,对输入串abbcde的归约过程如下:该分析过程反复执行“移进”和“归约”两个动作,直到栈中只有开始符号为止。abAcS1移进aAa移进b4a归约35cAa移进d7cAa归约48BcAa移进e910归约1移进b2a归约23ab移进c6AadBeA*语法分析树的生成演示abbcdeAABSA→bA→AbB→dS→aAcBe(1)SaAcBe(2)Ab(3)AAb(4)Bd*规范归约分析过程具有如下特点:从输入串的开始依次读入单词(移进栈中)。一旦发现可归约串(某个产生式的右端)就立即归约。归约就是将栈顶的一串符号用文法产生式的左部代替,归约可能重复多次。若最终能归约成文法的开始符号,则分析成功。由于总是将句型的最左边的可归约串替换成非终结符,该方法与最右推导对应。关键是如何判断可归约串?*问题的提出:①在构造语法树的过程中,何时归约?当可归约串出现在栈顶时就进行归约。②如何知道在栈顶符号串中已经形成可归约串?如何进行归约?不同的自下而上的分析方法对可归约串的定义是不同的,但分析过程的一个共同特点是:边移进边归约。规范归约:使用句柄来定义,如简单优先分析算符优先分析:使用最左素短语来定义LR分析方法:使用活前缀来定义*规范归约的概念有文法G,开始符号为S,如果有S=>xβy,则xβy是文法G的句型,x,y是任意的符号串如果有S=>xAy,且有A=>β,则β是句型xβy相对于非终结符A的短语如果有S=>xAy,且有A->β,则β是句型xβy相对于A->β的直接短语位于一个句型最左边的直接短语称为句柄.**+*注意:规范规约中每次归约的部分必须是句柄(最右推导)。关键的问题是如何识别句柄*