10.2. LL 分析¶

10.2.1. LL 分析¶

10.2.1.1. LL(k) 分析器¶

自顶向下分析器：开始时栈中只有起始符号，反复替换非终结符，直到生成该字符串为止。
预测分析器（predictive parser）：预测下一条重写规则

注意：为此使用向前看符号
LL 中的第一个 L 表示从左到右读取输入字符串
LL 中的第二个 L 表示产生最左推导

备注

问学生是否知道这是什么
$k$ ：所使用的向前看符号的个数。

有时需要的符号不止一个

10.2.1.2. LL 分析过程¶

将 CFG 转换为 PDA（方法与之前不同）
使用 PDA 和向前看符号
向前看符号是输入字符串中的下一个符号

注意：

PDA 是非确定的，因此我们将向前看下一个输入符号，并用它来确定使用哪一条重写规则。
非确定的，可以使用回溯，但这可能会永远进行下去。
记住：不一定能从 NPDA 构造出确定的 PDA。

10.2.1.3. 将 CFG 转换为 NPDA¶

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

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

备注

只是提一下这些内容，然后画 NPDA。

构造出的 NPDA：

三个状态： $s, q, f$

照常，在状态 $s$ 开始

把 $S$ 压入栈中，进入 $q$

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

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

从栈中弹出 $z$ ，进入 $f$ ，接受

Example 10.2.1

$L = \{a^nbb^n: n \ge 0 \}$

$S \rightarrow aSb \mid b$

注意，这是非确定的。你必须使用向前看符号来决定采用哪条转移，从某种意义上说是通过使用额外的信息来增加确定性。

备注

追踪 aabbb 。

symbol 是保存下一个输入符号的缓冲区（不会立即处理）
通过使用向前看符号，我们已经消除了非确定性。

本文法的分析例程（parsing routine）：

symbol 是向前看符号，$ 是字符串结束标记:

state = s
push(S)
state = q
read(symbol)                               获取前瞻符号
while top-of-stack <> z do                 当栈非空时
   case top-of-stack of
   S: if symbol == a then                  变量的情况
            { pop(); push(aSb) }           将 S 替换为 aSb
         else if symbol == b then
            { pop(); push(b) }             将 S 替换为 b
         else error
      a: if symbol <> a, then error        终结符的情况
         else { pop(); read(symbol) }      弹出 a，获取下一个前瞻符号
      b: if symbol <> b, then error
         else { pop(); read(symbol) }      弹出 b，获取下一个前瞻符号
      end case
end while
pop()                                      从栈中弹出 z
if symbol <> $ then error
state = f

有哪些缺点？

对于较大的文法，case 语句会变得相当长
可以把 case 语句放到一个通用的例程中

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

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

行：变量
列：终结符、$（字符串结束标记）
LL[i,j] 存放某条规则的右端。当规则的左端是表示第 $i$ 行的变量且向前看符号是表示第 $j$ 列的符号时，就把这个右端压入栈中。
如果任何 CFG 都能用这种分析表来描述，那么我们就可以用一个通用的分析器来判断字符串是否属于该语言。
不再需要状态

10.2.1.5. 通用的分析例程¶

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

push(S)
read(symbol)                                         获取向前看符号
while 栈非空 do
   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

备注

对前面的例子，尝试以下追踪：

分析字符串： aabbb

分析字符串： b

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

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

备注

回忆一下分析表是什么。

对每条规则 $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 \{\$\}$
每个未定义的表项都是错误。

Example 10.2.5

$S \rightarrow aSc \mid B$

$B \rightarrow b \mid \lambda$

我们已经为这个文法计算过 FIRST 和 FOLLOW ：

\[\begin{split}\begin{array}{c|l|l} & FIRST & FOLLOW\\ \hline \hline S & a, b, \lambda & \$, c \\ B & b, \lambda & \$, c \\ \end{array}\end{split}\]

计算这个例子的 LL 分析表：

对 $S \rightarrow aSc$ ，

$\mbox{FIRST}(aSc) = \{a\}$ ，所以按步骤 1a 把 $aSc$ 加入 LL[S,a] 。
对 $S \rightarrow B$ ，

$\mbox{FIRST}(B) = \{b, \lambda \}$

$\mbox{FOLLOW}(S) = \{\$, c\}$

按步骤 1a，把 $B$ 加入 LL[S,b]

按步骤 1b，把 $B$ 加入 LL[S,c] 和 LL[S,$]
对 $B \rightarrow b$ ，

$\mbox{FIRST}(b) = \{b\}$ ，所以按步骤 1a 把 $b$ 加入 LL[B,b]
对 $B \rightarrow \lambda$

$\mbox{FIRST}(\lambda) = \{ \lambda \}$ 且 $\mbox{FOLLOW}(B) = \{\$, c\}$ ，所以按步骤 1b 把 $\lambda$ 加入 LL[B,c] ，并把 $\lambda$ 加入 LL[B,$] 。

LL(1) 分析表

\[\begin{split}\begin{array}{c||c|c|c|c} & a & b & c & \$ \\ \hline \hline S & aSc & B & B & B \\ \hline B & \mbox{error} & b & \lambda & \lambda \end{array}\end{split}\]

分析字符串： $aacc$

\[\begin{split}\begin{array}{lcccccccc} &&&&a \\ &&a&&S &S &B \\ &&S& S& c& c& c& c \\ \mbox{Stack:} & \underline{S} & \underline{c} & \underline{c} & \underline{c} & \underline{c} & \underline{c} & \underline{c} & \underline{c} \\ \mbox{symbol:} & a & a & a' & a' & c & c& c& c' \\ \end{array}\end{split}\]

其中 $a'$ 是字符串中的第二个 $a$ ， symbol 是向前看符号。这张表是 LL(1) 表，因为只需要 1 个向前看符号。

Example 10.2.7

构造语言的分析表：

$L = \{a^nb^nca^mcb^m : n \ge 0, m \ge 0\}$

$S \rightarrow AcB$

$A \rightarrow aAb$

$A \rightarrow \lambda$

$B \rightarrow aBb$

$B \rightarrow c$

\(\mbox{FIRST}(A) = \{a, \lambda\}\)
\(\mbox{FIRST}(S) = \{a, c\}\)
注意： \(\lambda\) 不在 \(\mbox{FIRST}(S)\) 中
\(\mbox{FIRST}(B) = \{a, c\}\)
\(\mbox{FOLLOW}(A) = \{b, c\}\)
\(\mbox{FOLLOW}(S) = \{\$\}\)
\(\mbox{FOLLOW}(B) = \{b, \$\}\)

计算分析表：

对 $S \rightarrow AcB$ ，

$\mbox{FIRST}(AcB) = \{a, c\}$ ，所以把 $AcB$ 加入 LL[S,a] 和 LL[S,c]

对 $A \rightarrow aAb$ ，

$\mbox{FIRST}(aAb) = \{a\}$ ，所以把 $aAb$ 加入 LL[A,a]

对 $A \rightarrow \lambda$ ，

$\mbox{FIRST}(\lambda) = \{\lambda\}$ 且 $\mbox{FOLLOW}(A) = \{b, c\}$ ，所以把 $\lambda$ 加入 LL[A,b] 和 LL[A,c]

对 $B \rightarrow aBb$ ，

$\mbox{FIRST}(aBb) = \{a\}$ ，所以把 $aBb$ 加入 LL[B,a]

对 $B \rightarrow c$ ，

$\mbox{FIRST}(c) = \{c\}$ ，所以把 $c$ 加入 LL[B,c]

所有其他表项都是错误。

LL(1) 分析表：

\[\begin{split}\begin{array}{c||c|c|c|c} &a &b &c & \$ \\ \hline \hline S &AcB &\mbox{error} &AcB &\mbox{error} \\ \hline A &aAb &\lambda &\lambda &\mbox{error} \\ \hline B &aBb &\mbox{error} &c &\mbox{error} \\ \end{array}\end{split}\]

分析字符串： $abcacb$

分析字符串： $cc$

分析字符串： $abcab$ （不在语言中）

Example 10.2.8

$L = \{a^nb^nca^mcb^m: n \ge 1, m \ge 1 \}$

\(S \rightarrow AcB\)
\(A \rightarrow aAb\)
\(A \rightarrow ab\)
\(B \rightarrow aBb\)
\(B \rightarrow acb\)

\[\begin{split}\begin{array}{c|l|l} & \mbox{FIRST} & \mbox{FOLLOW} \\ \hline \hline S & a & \$ \\ \hline A & a & c,b \\ \hline B & a & b,\$ \\ \end{array}\end{split}\]

注意，由于没有 $\lambda$ 规则，FIRST 和 FOLLOW 计算起来相当容易！在这种情况下，构造分析表不需要 FOLLOW。

尝试构造 LL(1) 分析表

\[\begin{split}\begin{array}{c||c|c|c|c} &a &b &c & \$ \\ \hline \hline S &AcB &\mbox{error} &\mbox{error} &\mbox{error} \\ \hline A &aAb &\mbox{error} &\mbox{error} &\mbox{error} \\ &ab & & & \\ \hline B &aBb &\mbox{error} &\mbox{error} &\mbox{error} \\ & acb & & & \\ \end{array}\end{split}\]

注意，仅用一个向前看符号，你不知道该用哪条重写规则来替换 $A$ 和 $B$ 。 $A$ 有两个选择，两者都使用 'a' 作为向前看符号。 T[A,a] 在 LL(1) 分析表中有两个表项。因此，不存在 LL(1) 分析表。这意味着该文法不是 LL(1) 的！我们将尝试使用 2 个向前看符号。

例如，字符串 $aabbcaacbb$ 仅用一个向前看符号无法分析。

LL(2) 分析表：

\[\begin{split}\begin{array}{c||c|c|c|c|c|c|c} &aa &ab &ac & a\$ & b & c & \$ \\ \hline \hline S &AcB &AcB & error & error &error &error &error \\ \hline A &aAb &ab & error & error &error &error &error \\ \hline B &aBb &error & acb & error &error &error &error \\ \end{array}\end{split}\]

没有冲突（表中每个表项只有一条规则）。这是 LL(2) 分析器——需要两个向前看符号。

分析字符串： $aabbcacb$

\[\begin{split}\begin{array}{lcccccccccccc} &&&a&&a \\ &&&A&A&b&b\\ &&A & b& b& b& b& b&&&a\\ &&c&c&c&c&c&c&c&&c&c\\ \mbox{Stack:} & \underline{S} & \underline{B}& \underline{B}& \underline{B} & \underline{B}& \underline{B}& \underline{B}& \underline{B}& \underline{B} & \underline{b} & \underline{b} & \underline{b} \\ \mbox{symbol:} & aa & aa &aa & ab & ab & bb & bc& ca& ac &ac & cb & b\$ \\ \end{array}\end{split}\]

注意这是最左推导！还要注意，每当栈顶有变量时，就会使用两个向前看符号。

LL(k) 分析器需要 $k$ 个向前看符号。

备注

提一下，如果文法是左递归的，LL 分析器就无法工作。

注释（Comments）：

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

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

VisFormalLang 形式语言可视化

第 10 章语法分析

10.2. LL 分析¶

10.2.1. LL 分析¶

10.2.1.1. LL(k) 分析器¶

10.2.1.2. LL 分析过程¶

10.2.1.3. 将 CFG 转换为 NPDA¶

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

10.2.1.5. 通用的分析例程¶

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

VisFormalLang 形式语言可视化

第 10 章 语法分析

10.2. LL 分析¶

10.2.1. LL 分析¶

10.2.1.1. LL(k) 分析器¶

10.2.1.2. LL 分析过程¶

10.2.1.3. 将 CFG 转换为 NPDA¶

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

10.2.1.5. 通用的分析例程¶

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

第 10 章语法分析