编译原理（四）自顶向下语法分析方法、LL(1)文法的判别、非LL(1)文法转换为LL(1)文法

柔光的暖阳◎ 2023-02-18 14:29 105阅读 0赞

本文要点

  1. 理解 “能使用自顶向下分析技术的文法必须是LL(1)文法”
  2. LL(1)文法的充要条件
  3. LL(1)文法的判别
  4. 某些 非LL(1)文法 到 LL(1)文法 的等价变换
    1.提取左公共因子
    2.消除左递归（直接左递归、间接左递归）
  5. 不确定的自顶向下分析思想
  6. 确定的自顶向下分析方法
    1.递归子程序法
    2.预测分析法[判别LL(1)文法；构造预测分析表；分析输入串]
    在这里插入图片描述

4.1 确定的自顶向下分析思想

主要思想：
从文法的开始符号出发，如何根据当前的单词符号，
唯一地确定选用哪个产生式来替换相应的VN向下推导。
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

4.2 LL(1)文法的判别

判别步骤：

  1. 求出能推出ε的非终结符
  2. 计算FIRST集
  3. 计算FOLLOW集
  4. 计算SELECT集
  5. 判别是否是LL(1)文法
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

4.3 某些非LL(1)文法到LL(1)文法的等价变换

在这里插入图片描述

4.3.1 提取左公共因子

在这里插入图片描述
在这里插入图片描述

4.3.2 提取隐含的左公共因子

在这里插入图片描述

4.3.3 不能在有限步骤内提取完左公共因子的文法

在这里插入图片描述

4.3.4 消除左递归

在这里插入图片描述

4.3.5 消除直接左递归

在这里插入图片描述

4.3.6 消除间接左递归

在这里插入图片描述

4.3.7 消除文法中一切左递归

在这里插入图片描述
在这里插入图片描述

4.4 确定的自顶向下分析方法

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
构造预测分析表的方法：
对每个VT或“#”用符号a表示。
若a∈SELECT（A–>α），则把A–>α放入M[A,a]中。
（所有空白的M[A,a]表示出错。）
在这里插入图片描述
在这里插入图片描述

4.5 不确定的自顶向下分析思想

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

发表评论

表情：
评论列表 （有 0 条评论，105人围观）

还没有评论，来说两句吧...

相关阅读

    相关 LL（1）文法 JAVA

    E文法表达式类 G 定义文法类 LL 文法分析类 ， 包含对First,Follow,Select集合的求解以及对表达式的分析函数  Main测试分析程序，并输出结果

    灰太狼灰太狼/ 0 赞/ 232 阅读

    相关 LL(1)文法

    文章目录 预测分析法的工作过程 S\_文法（简单的确定性文法） 什么时候使用$\\epsilon$产生式？ 非终结符的后继符号集 产生式的可

    川长思鸟来川长思鸟来/ 0 赞/ 398 阅读