语法分析自下而上分析ppt课件.ppt

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

1、第五章语法分析-自下而上分析5.1自底向上分析的一般过程：移进-归约分析5.1.1规范归约5.2算符优先分析5.3LR分析法5.4语法分析器的自动产生主要内容若ZS则SL(G[Z])否则SL(G[Z])+G[Z]自底向上分析算法的基本思想：存在主要问题:可归约串的识别问题主要方法:算法优先分析法LR分析法5.1自底向上分析的一般过程所谓自顶向上分析法就是从输入串开始，利用有关规则逐步进行“归约”，又称为移进-归约分析法。特点：边移进边归约。移进—归约分析结构#分析器#符号栈输入串要点：建立符号栈，用来纪

2、录分析的历史和现状，并根据所面临的情况，确定下一步动作是移进还是归约。分析过程：把输入符号串按描述顺序一一地移进符号栈（一次移一个），检查栈中符号，当在栈顶的若干符号形成当前句型的句柄时，就根据规则进行规约，将句柄从符号栈中弹出，并将相应的非终结符号压入栈内（即规则的左部符号），然后再检查栈内符号串是否形成新的句柄，若有就再进行规约，否则移进符号。分析一直进行到读到输入串的右界符为止。最后，若栈中仅含有左界符号和识别符号，则表示分析成功，否则失败。#分析器#符号栈输入串归约（回顾）推导定义1.直接推导“”α

3、→β是文法G的产生式，若有v,w满足：v=γαδ,w=γβδ,其中γ∈V*,δ∈V*(V代表字母表)则称v直接推导到w,记作vw也称w直接归约到v例：G：S→0S1，S→010S100S1100S11000S111000S11100001111S0S1如果移进－归约过程是自顶向下最右推导的逆过程，则称为规范归约。如对最右推导SαAδαβδ来说，一定有A→β规则存在，将句型αβδ中的β用产生式的左部符号代替便得到新句型αAδ，这是一次规范归约，恰好与规范推导相反。5.1.1规范归约*对应的规范归约

4、过程:abbcdeA→baAbcdeA→AbaAcdeB→daAcBeS→aAcBeS归约为开始符号，是合法句子。SaAcBcAbbd句子abbcde的最右推导过程：SaAcBeaAcdeaAbcdeabbcde文法G[S]:S→aAcBeA→Ab

5、bB→d例对应的自下而上分析过程符号栈输入符号串动作＃abbcde＃移进＃abbcde＃移进＃abbcde＃归约(A→b)＃aAbcde＃移进＃aAbcde＃归约(A→Ab)＃aAcde＃移进＃aAcde＃移进＃aAcde＃归约(B→d)＃aAcBe＃移进

6、＃aAcBe＃归约(S→aAcBe)＃S＃接受在移进-归约过程中，何时归约？何时移进？不能只看到栈顶出现某一产生式的右部就用相应产生式归约，如在第5步时，栈中符号是＃aAb，栈顶符号串b,Ab都是产生式的右部符号，这时到底用A→b还是A→Ab归约不能确定。为此引入了可归约串的概念。自下而上分析主要问题主要问题识别“可归约串”。对“可归约串”概念的不同定义，就形成了不同的自下而上的分析方法。在“规范归约”中，则用“句柄”来刻画“可归约串”。在算符优先分析法中我们用“最左素短语”来刻画“可归约串”；短语令G是一个

7、文法，S是文法的开始符，假定是文法G的一个句型，如果有：SA且A则称是句型相对于非终结符A的短语。直接短语特别是，如果有A（即有A→的产生式）则称是句型相对于规则A的直接短语。句柄一个句型的最左直接短语称为该句型的句柄。相关概念*+子树与短语的关系子树语法树的某个结点连同它的所有后代组成了一棵子树，只含有单层分枝的子树称为简单子树。短语在语法树中的识别：短语：子树的末端结点(即树叶)组成的符号串是相对于子树根的短语；直接短语：简单子树的末端结点组成的符号串是相对于简单

8、子树根的直接短语；句柄：最左简单子树的末端结点组成的符号串为句柄。显然从语法树出发寻找短语、直接短语、句柄要直观得多。解:(1)该句型的推导过程为EE+TT+TT*F+TF*F+Ti*F+Ti*i+Fi*i+ii+i并不是该句型的一个短语。文法：ET

9、E+TTF

10、T*FFi

11、(E)对于句型i*i+i，判断i＋i是否是该句型的一个短语。因为尽管有Ei+i,但是,不存在从E(文法开始符）到i*E的推导+例1从语法树中看，i+i不构成一棵子树的所有叶子结点E＋ETFTFiiFi*(2)例2上题

12、文法的另一个句型E+T*F+I,求其含有的短语、直接短语和句柄短语：E+T*F+i,E+T*F,T*F,和i。直接短语：T*F和i。句柄为：T*F。EE＋TE＋TT*FFi注意:一个句型的直接短语可能不只一个，但最左直接短语(即句柄)是惟一的。规范规约就是句柄归约可归约串是句柄。归约过程：裁剪句柄。即把A的子节点从分析树中删除。规范规约的特点句柄为什么可作为可归约串？句柄具有“最左”特性，句柄的“最