跳转至

LL(1)分析法

  • 构造不带回溯的自上而下分析算法
    • 消除文法的左递归性
    • 克服回溯
  • 编译原理重点 LL(1)

    • L:表示从左向右扫描输入串
    • L:最左推导
    • 1:向前看1步

左递归的消除

  • 直接消除在产生式中的左递归:
    • 如非终结符P的规则为:PPα|β
      • 其中β不以P为开头
    • 编译原理重点 我们可以把P的规则等价的改写为如下的非直接左递归形式:

      • PβP
      • PαP|ε

        将左递归变为了右递归

  • 编译原理重点 一般而言,假定P关于的全部产生式是:\(PPα1|Pα2||Pαm|β1|β2||βn\)

    • 消除P的直接左递归性即将规则改写为:\(Pβ1P|β2P||βnPPα1P|α2P||αmP|ε\)
  • 有的文法可能没有直接左递归,但也可能是左递归的:
  • 一个文法消除左递归的条件:
    • 不含以ε为右部的产生式
    • 不含回路:
  • 消除左递归的算法:
    • 将文法G的所有非终结符按照某一种顺序排列,并逐个执行:
    • image.png
    • 化简所得到的文法,去除从开始符号出发永远无法到达的非终结符的产生规则
  • 算法的注意事项:
    • 适用于:消除了PP产生式和不以ε为右部的产生式文法
    • 第二步中所作的工作:
      • 若为直接左递归,则消除直接左递归
      • 若右部的最左符号是非终结符且序号大于左部的非终结符,则不进行替换
      • 序号小于左部的非终结符,则将序号小的非终结符用其右部的串进行替换,然后消除新的直接左递归
      • 这样,每次替换的非终结符均为前面已经处理过的非终结符

消除回溯,提取左公因子

  • 产生回溯的原因:推导时,若产生式存在多个候选式,选择哪个进行推导存在不确定性
  • 编译原理重点 提取左公因子:

    image.png

LL(1)分析条件

  • 编译原理重点 如果一个文法是LL(1)文法,则满足:

    • 文法不含左递归
    • 对于文法中每个非终结符A的各个产生是的候选首符集两两不相交
      • Aα1|α2||αn
      • FIRST(αi)FIRST(αj)=
    • 对于文法中的每个非终结符A,存在某个候选首符集包含ε,则FIRST(αi)FOLLOW(A)=

#编译原理重点 FIRST

  • FIRST(α):可以从α推导得到的串的首符号的集合\(FIRST(α)={a|aa.aVT}\)
  • 算法:
    • 如果X是一个终结符号,那么FIRST(X)=X
    • 如果X是一个非终结符号,且XY1Y2Yk
      • 如果对于某个iαFIRST(Yi)中,且ε在所有的FIRST(Y1)FIRST(Y2)FIRST(Yi1)中,则将a添加到FIRST(X)
    • 如果Xε是一个产生式,则将ε添加到FIRST(X)
  • 主要看产生式左边
  • 自下而上求

#编译原理重点 FOLLOW

  • FOLLOW(A):可能在某些句型中紧跟在A右边的终结符号集合\(FOLLOW(A)={a|SAa,aVT}\)
  • 算法:
    • $添加到FOLLOW(S)中,其中S是开始符号,$是右端的结束标记
    • 如果存在产生式AαBβ,则FIRST(β)中除了ε之外的所有符号都在FOLLOW(B)
    • 如果存在AαB或存在产生式AαBβFIRST(β)中包含了ε可以理解为同一种情况AαB),则将FOLLOW(A)中的所有符号都放在FOLLOW(B)
  • 只看产生式右边
  • 自上而下求 image.png