LL(1)文法

自顶向下分析法希望文法满足的条件

从左至右扫描输入串,寻找它的一个最左推导;对于G的每个非终结符A,若A有多个不同的候选式时,在选择产生某个终结符号时能唯一选定一个。给定文法S→cAd,A→ab|a,A的候选式ab和a具有相同首部终结符号,LL(1)文法希望避免这种文法。

串首终结符集-FIRST集

FIRST(α)即关于α的所有产生式右部第一个遇到终结符。FIRST(α)={a|α=*>a…,a∈$V_t$*}

求FIRST集的算法

  • 令α=$X_1$…$X_n$
  • 初值:
    • FIRST(α)=FIRST($X_1$)-{ε}
    • k=1
  • 循环
    • while ε∈FIRST($X_k$) && k<n do
      • FIRST(α)=FIRST(α)∪(FIRST($X_{k+1}$)-{ε})
      • k = k+1
  • 结束
    • if k==n && ε∈FIRST($X_k$) then FIRST(α)=FIRST(α)∪{ε}

非终结符后继符号集-FOLLOW集

FOLLOW(A)即非终结符A的后续符号集。FOLLOW(A)={a|S=>…Aa…,a∈$V_t$\}

求FOLLOW集的算法

  • 若B→αAaβ,a是终结符,则把a放入FOLLOW(A)中
  • 若B→αAXβ,X是非终结符,则把FIRST(Xβ)放入FOLLOW(A)中
  • 若B→αA或B→αAβ,但β=>ε,则把FOLLOW(B)放入FOLLOW(A)中
  • 若S是开始符,则$∈FOLLOW(S)
  • 若A→αBβ,则FIRST(β)中除了ε之外所有符号均在FOLLOW(B)中
  • 若A→αB或A→αBβ,且FIRST(β)包含ε,则FOLLOW(A)所有符号均在FOLLOW(B)中

产生式可选集-SELECT集

  • 产生式A→β的可选集是指可以选用该产生式进行推导时对应的输入符号集合,记为SELECT(A→β)
    • SELECT(A→αβ)={α}
    • SELECT(A→ε)=FOLLOW(A)

LL(1)文法

对G中任意变量A,A→$a_1$|$a_2$|…|$a_n$是A的所有产生式,若他们满足

  • FIRST($a_i$)∩FIRST($a_j$) =Φ i≠ j
  • 当ε∈FIRST($a_j$)时,FOLLOW(A)∩FIRST($a_j$)=Φ

则称G为LL(1)文法。

LL(1)文法分析原理