2.1.1. LL(k) 分析器¶

• 自顶向下分析器：开始时栈中只有起始符号， 反复替换非终结符，直到生成该串为止。

• 预测分析器（predictive parser）：预测下一条重写规则

  注意：为此使用向前看符号

• LL 中的第一个 L 表示从左到右读取输入串

• LL 中的第二个 L 表示产生最左推导

  备注

  问学生是否知道这是什么

• \(k\) ：所使用的向前看符号的个数。

  有时需要的符号不止一个

2.1.2. LL 分析过程¶

• 将 CFG 转换为 PDA（方法与之前不同）

• 使用 PDA 和向前看符号

• 向前看符号是输入串中的下一个符号

注意：

• PDA 是非确定的，因此我们将向前看下一个输入 符号，并用它来确定使用哪一条重写规则。

• 非确定的，可以使用回溯，但这可能会永远 进行下去。

• 记住：不一定能从 NPDA 构造出确定的 PDA。

2.1.3. 将 CFG 转换为 NPDA¶

注意：这不是我们之前使用的构造方法。 这种方法适用于任何 CFG，即使是那些不属于 GNF 的 CFG。

想法：要用 CFG 推导一个串，从 起始符号开始，反复应用产生式 规则，直到推导出该串为止。 为了用 NPDA 模拟这个过程，开始时把 起始符号压到栈上。 每当要应用产生式规则 \(A \rightarrow w\) 时， 变量 \(A\) 应该在栈顶。 弹出（或替换） \(A\) ，并把该规则的右端 \(w\) 压到栈上。 每当栈顶是终结符时，如果它与输入串的下一个 符号匹配，则把它从栈中弹出。 如果不匹配，那么这个串不属于该文法的 语言。 如果从起始符号 \(S\) 开始，可以应用替换 规则，匹配输入串中的所有终结符并清空 栈，那么这个串就属于该语言。

构造出的 NPDA：

• 三个状态： \(s, q, f\)

  照常，在状态 \(s\) 开始

  把 \(S\) 压入栈中，进入 \(q\)

  所有重写规则都在状态 \(q\) 中： 如果重写规则的左端在栈顶，则用重写规则的右端替换它，并保持在状态 \(q\)

  \(q\) 中识别终结符的附加规则： 读取输入符号，弹出输入符号，保持在状态 \(q\)

  从栈中弹出 \(z\) ，进入 \(f\) ，接受

2.1.4. LL 分析表：二维数组¶

当文法较大时，分析例程会有很多 case 分支。 另一种做法是把要应用的规则的信息存储在 一张表中。

• 行：变量

• 列：终结符、$（串结束标记）

• LL[i,j] 存放某条规则的右端。 当规则的左端是表示第 \(i\) 行的变量且向前看符号是表示第 \(j\) 列的符号时，就把这个右端压入栈中。

• 如果任何 CFG 都能用这种分析表来描述， 那么我们就可以用一个通用的分析器来判断串 是否属于该语言。

• 不再需要状态

2.1.5. 通用的分析例程¶

想法：要用适当的右端替换栈顶的变量，使用向前看 符号和左端在 LL 分析表中查找右端。 （LL[,] 就是分析表。）:

push(S) read(symbol)                                         当栈非空时获取向前看符号
   case 栈顶元素为
      终结符：
         if 栈顶元素 == symbol
            then { pop(); read(symbol) }             弹出终结符并获取下一个向前看符号
         else
            error
      非终结符：
         if LL[栈顶元素，symbol] <> error
            then { pop(),                            弹出左部
                   push(LL[栈顶元素，symbol]) }   压入右部
            else
               error
       end case
end while if symbol <> $, then error

我们将使用 FIRST 和 FOLLOW 这两个函数来帮助 计算分析表。

2.1.6. 构造 LL 分析表 LL[rows,cols]¶

1. 对每条规则 \(A \rightarrow w\)

   1. 对 FIRST(w) 中的每个 a

      把 w 加入 LL[A,a]
   2. 如果 \(\lambda\) 在 FIRST(w) 中

      对 FOLLOW(A) 中的每个 \(b\) ，把 \(w\) 加入 LL[A,b]

      其中 \(b \in T \cup \{\$\}\)

2. 每个未定义的表项都是错误。

注释（Comments）：

有些 CFL 没有 LL(k) 分析器

有些语言，某些文法有 LL(k) 分析器，而另一些文法没有。