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

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

1、自顶向下（Top-Down）语法分析第六讲基本思想自顶向下预测分析LL(1)分析自顶向下语法分析带回溯的自顶向下分析文法变换：消除左递归、提取左公因子LL(1)分析中的出错处理基本思想核心问题：句型分析对任意上下文无关文法G=(V，T，P，S)和任意wT*，是否有wL(G)？若成立，则给出分析树或（最左）推导步骤；否则，进行报错处理。两种实现途径自顶向下（top-down）分析自底向上（bottom-up）分析语法分析从文法开始符号出发进行推导；每一步推导都获得文法的一个句型；直到产生出一个句子，恰好是所期望的终结符串每一步推导是对当前句型中剩余的某个非终结符进行扩展，即用

2、该非终结符的一个产生式的右部替换该非终结符如果不存在任何一个可以产生出所期望的终结符串的推导，则表明存在语法错误自顶向下分析思想基本思想自顶向下分析举例S（SAB）AB（AaA）aAB（Bb）aAb（AaA）aaAb（AaA）aaaAb（A）aaab文法G（S）:SABAaA

3、Bb

4、bB单词序列aaab的一个自顶向下分析过程基本思想两类非确定性在每一步推导中，选择对哪一个非终结符、哪一个产生式都可能是非确定的分析成功的结果：得到一个推导一般方法带回溯的自顶向下分析举例S（1）AB（2）aAB（5）aAbB（2）aaAbB（2）aaaA

5、bB（3）aaabB（回溯）……复杂度很高失败条件较复杂文法G（S）:（1）SAB（2）AaA（3）A（4）Bb（5）BbB单词序列aaab的一个自顶向下分析过程带回溯的自顶向下分析仅有产生式选择是非确定的在每一步推导中，总是对最左边的非终结符进行替换，但选择哪一个产生式是非确定的分析成功的结果：得到一个最左推导原理：每个合法的句子都存在至少一个起始于开始符号的最左推导；一个终结符串，只要存在一个起始于开始符号的最左推导，它就是一个合法的句子从左向右扫描输入单词，失败条件较简单改进的方法带回溯的自顶向下分析改进的方法举例S（1）AB（2）aAB（3）aB（回溯

6、）aAB（2）aaAB（2）aaaAB（3）aaaB（5）aaabB（回溯）aaaB（4）aaab（成功）文法G（S）:（1）SAB（2）AaA（3）A（4）Bb（5）BbB单词序列aaab的一个自顶向下分析过程带回溯的自顶向下分析复杂度降低失败条件简化非终结符选择和产生式选择都是确定的在每一步推导中，总是对最左边的非终结符进行展开，且选择哪一个产生式是确定的，因此是一种无回溯的方法从左向右扫描，可能向前查看（lookahead）确定数目的单词分析成功的结果：得到唯一的最左推导分析条件：对文法需要有一定的限制确定的自顶向下分析自顶向下预测分析举例（向前查看2个

7、单词）S（1）AB（2）aAB（2）……anAB（3）anB（5）anbB（5）……anbm-1B（4）anbm（成功）文法G（S）:（1）SAB（2）AaA（3）A（4）Bb（5）BbB单词序列anbm（n0,m0）的预测分析过程只要向前查看2个单词，就可预测分析L(G)中所有句子自顶向下预测分析左递归带来的问题文法G（S）:（1）SSa（2）Sb考虑下列文法识别ban的分析过程S（1）Sa（1）Saa（1）Saaa（1）……San（2）ban但是：无论向前查看的单词数确定为多少，都无法满足预测分析L(G)中所有句子的需求需要向前查看n+2

8、个单词，才能确定这样的推导序列自顶向下预测分析要求文法不含左递归例：直接左递归可以通过文法变换消除左递归专门讨论例：间接左递归PPaPb……PAaAPb……自顶向下预测分析左公因子带来的问题文法G（S）:SabAabBAaBb如下文法需要向前查看3个单词来预测分析L(G)中的句子文法G（S）:SaAbaAcAaaA对于如下文法无法确定需要向前查看多少个单词来预测分析L(G)中的句子自顶向下预测分析通常要求文法不含左公因子可以通过文法变换消除左公因子专门讨论自顶向下预测分析应用较普遍的自顶向下预测分析是LL（1）分析要求文法一定是LL（1）文法专门讨论自顶

9、向下预测分析第一个“L”,代表从左（Left）向右扫描单词第二个“L”,代表产生的是最左（Leftmost）推导“1”代表向前查看（lookahead）一个单词LL（1）的含义LL（1）分析要求文法是LL（1）的什么是LL（1）文法？先引入两个重要概念对文法的限制LL（1）分析First集合Follow集合两个重要概念LL（1）分析定义设G=（VT，VN，P，S）是上下文无关文法对(VTVN)*，First（）={a*a,aVT,(VTVN)*,或者*ε时a=ε}