这一节会介绍自顶向下解析器的非递归预测方法，这个方法和递归下降比较解决，但是他不会对若干产生式进行尝试，并且没有回溯，通过向前看一些记号来预测需要用到的产生式。

LL(1)语法

LL(k)语法是指：
L-means"left-to-right'’ scan of input
L-meanss "leftmost derivation"
k-means“predict based on k tokens of lookahead"

LL(1)就是最左推导，并且只提前看一个符号。

为了实现不用回溯，我们需要定义两个集合$First$和$Follow$。

$FIRST$集合

$FIRST(α)$ 定义为可以从 $α$ 推导出的所有可能的终结符串的第一个符号的集合，其中 $α$ 是任意的文法符号串。

计算规则：

1. 如果 $X$ 是终结符，则 $FIRST(X) = {X}$
2. 如果 $X$ 是非终结符且 $X → ε$，则 $ε ∈ FIRST(X)$
3. 如果 $X$ 是非终结符且 $X → Y1Y2...Yk$：
   • 将 $FIRST(Y1) - {ε}$加入 $FIRST(X)$
   • 如果 $ε ∈ FIRST(Y1)$，则将 $FIRST(Y2) - {ε}$ 加入 $FIRST(X)$
   • 以此类推，直到某个 $Yi$不包含 $ε$
   • 如果所有 $Yi$ 都包含 $ε$，则将 $ε$ 加入 $FIRST(X)$

示例： 给定文法：
$E \to TE'$
$E' \to +TE' | \epsilon$
$T \to FT'$
$T' \to *FT' | \epsilon$
$F \to (E) | id$

计算FIRST集合：
FIRST(F) = { (, id }
FIRST(T') = { *, ε }
FIRST(T) = FIRST(F) = { (, id }
FIRST(E') = { +, ε }
FIRST(E) = FIRST(T) = { (, id }

$FOLLOW$集合

$FOLLOW(A)$ 定义为在某些句型中紧跟在非终结符A后面的终结符的集合。

计算规则：

1. 将$放入 $FOLLOW(S)$，其中S是开始符号
2. 如果存在产生式 $A → αBβ$：
   • 将 $FIRST(β) - {ε}$加入 $FOLLOW(B)$
   • 如果 $ε ∈ FIRST(β)$，则将 $FOLLOW(A)$ 加入 $FOLLOW(B)$
3. 如果存在产生式 $A → αB$，则将 $FOLLOW(A)$ 加入 $FOLLOW(B)$

示例： 继续使用上面的文法，计算FOLLOW集合：
FOLLOW(E) = { $, ) }
FOLLOW(E') = FOLLOW(E) = { $, ) }
FOLLOW(T) = { +, $, ) }\d FOLLOW(T') = FOLLOW(T) = { +, $, ) }
FOLLOW(F) = { *, +, $, ) }

LL(1)分析表的构建

利用 $FIRST$ 和 $FOLLOW$ 集合，我们可以构建LL(1)分析表，表中行是非终结符，列为终结符或者开始符号$：

1. 对于每个产生式 $A → α$：
   • 对 $FIRST(α)$ 中的每个终结符 $a$，将 $A → α$ 加入 $M[A,a]$
   • 如果 $ε ∈ FIRST(α)$，则对 $FOLLOW(A)$ 中的每个终结符 $b$，,将 $A → α$ 加入M[A,b]
2. 所有未定义的条目标记为error

LL(1)文法的条件：

1. 无左递归
2. 对于每个非终结符A和每个输入符号a，M[A,a]最多包含一个产生式

并且任何两个产生式A→α|β都满足下列条件:

1. $FIRST(α) \cap FIRST(β)= \emptyset$
2. 若β=>*ε，那么 $FIRST(α) \cap FOLLOW(A) = \emptyset$

第一点意味这每次选择的时候，需要唯一选择 第二点也意味需要唯一选择。

• 假设 $FIRST(α) \cap FOLLOW(A)= \emptyset$
• $α ∈ FIRST(α): A =>*aα'$
• $α ∈ FOLLOW(A): B =>*... A a.$
• 由于 $β→*ε$，所以遇到 $α$ 时，无法判断用哪一个产生式
• 可以用 $A→α$ 来对 $A$ 进行展开
• 亦可以用 $A→β$ 和 $β=*ε$ 最后把 $A$ 消掉

更新日志

2025/1/12 02:51

查看所有更新日志

• 578c3-更新自底向上和LR(1)语法于 2025/1/12