编译原理 教学课件 作者 王生原 董渊 杨萍 张素琴 slide07.ppt

《编译原理 教学课件 作者 王生原 董渊 杨萍 张素琴 slide07.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、自底向上（Bottom-Up）语法分析第七讲移进归约分析LR分析自底向上语法分析自底向上分析思想二义文法在LR分析中的应用LR分析中的出错处理几类分析文法之间的关系自底向上分析思想核心问题：句型分析对任意上下文无关文法G=(V，T，P，S)和任意wT*，是否有wL(G)？若成立，则给出分析树或（最左）推导步骤；否则，进行报错处理。两种实现途径自顶向下（top-down）分析自底向上（bottom-up）分析语法分析从所要分析的终结符串开始进行归约；每一步归约是在当前串中找到与某个产生式的右部相匹配的子串，然后将该子串用这一产生式的左部非终结符进行替换；如果找不

2、到这样的子串，则回退到上一步归约前的状态，选择不同的子串或不同的产生式重试；重复上一步骤，直到归约至文法开始符号；如果不存在任何一个这样的归约，则表明该终结符串存在语法错误自底向上分析的一般过程自底向上分析思想自底向上分析举例aaab（A）aaaAb（AaA）aaAb（AaA）aAb（Bb）aAB（AaA）AB（SAB）S文法G（S）:SABAaA

3、Bb

4、bB单词序列aaab的一个自底向上分析过程自底向上分析思想在每一步归约中，选择哪一个产生式以及匹配哪一个位置上的子串都可能是非确定的这些非确定性导致分析过程会有很高的复杂性自底向上

5、分析中的非确定性自底向上分析思想改进的方法自底向上分析思想选择“可归约串”进行归约在实用的自底向上分析中，总是选择某个“可归约串”进行归约，可大大减少回溯对于一个句型而言，“可归约串”一定是该句型的短语对于文法G[S]，若SαAδ且Aβ，则称β是句型αβδ相对于非终结符A的短语+举例：短语文法G（S）:（1）SAB（2）AaA（3）A（4）Bb（5）BbB对于右边的文法G(S),句子aaab的短语有：：aaab；a：aaab；aa：aaab；aaa：aaab；aaab：aaabb：aaab句型aaAb的短语有：aA：aaAb；aaA：a

6、aAb；aaAb：aaAbb：aaAb自底向上分析思想AaABSbAaAa直接短语自底向上分析思想对于文法G=(VN,VT,P,S)，以及,β,δ(VNVT)*若SαAδ且Aβ，则称β是句型αβδ相对于非终结符A的直接短语直接短语的作用作为当前句型的一步“可归约串”举例：直接短语自底向上分析思想文法G（S）:（1）SAB（2）AaA（3）A（4）Bb（5）BbB对于右边的文法G(S)句子aaab的直接短语有：：aaab；b：aaab句型aaAb的直接短语有：aA：aaAb；b：aaAbAaABSbAaAa句柄自底向上分析思想rm对于

7、文法G=(VN,VT,P,S),以及,β(VNVT)*,wVT*若SαAw且Aβ，则称β是右句型αβw相对于非终结符A的句炳句柄的作用作为当前句型最左的一步“可归约串”举例：句柄自底向上分析思想文法G（S）:（1）SAB（2）AaA（3）A（4）Bb（5）BbB对于右边的文法G(S),句子aaab的直接短语有：：aaab；b：aaabaaab的句柄：右句型aaAb的直接短语有：aA：aaAb；b：aaAbaaAb的句柄：aAaaabaaaAbaaAbABSaAbAbrmrmrmrmrmrm举例：句柄不一定唯一自底向上分析思想

8、对于右边的文法G(S),句子aaab的直接短语有：：aaab；b：aaabaaab的句柄：右句型aaAb的直接短语有：aA：aaAb；aaA：aaAb；b：aaAbaaAb的句柄：aA，aaA文法G（S）:（1）SAB（2）AaA（3）AaaA（4）A（5）Bb（6）BbB不唯一的原因：G（S）是二义文法，右句型的最右推导有多个举例:最右推导与最左归约自底向上分析思想G(S):S(L)

9、aLL,S

10、S自底向上分析的实现技术自底向上分析思想移进归约（shift-reduce）分析技术LR分析和算符优先分析（参见清华教材第6章）采用移进归约分

11、析技术与自顶向下技术相比自底向上分析思想功能较强大原因在于推导和归约过程有如下差别：推导时仅观察可推导出的输入串的一部分，而归约时可归约的输入串整体已全部出现构造较复杂不适合手工构造但存在很好的自动构造技术（如Yacc工具采用LALR分析技术）利于出错处理输入符号查看后才被移进借助一个下推栈（分析栈）和一个基于有限状态控制的分析引擎分析引擎根据当前状态、下推栈当前状态/内容、剩余输入单词序列来确定如下动作之一，然后进入新状态：Reduce:依确定的产生式序列对位于栈顶的短语进行归约Shift:从输入序列移进一个单词Error:发现语法错误，进行错误处理/恢复Ac