编译原理 - 自顶向下解析

我们在上一章了解到，自顶向下解析技术从根节点开始解析输入，逐步向下移动到叶节点，构建语法树。自顶向下解析的类型如下所示

递归下降解析

递归下降是一种自顶向下的解析技术，它从顶部构建语法树，并从左到右读取输入。它为每个终结符和非终结符实体使用过程。这种解析技术递归地解析输入以生成语法树，这可能需要或不需要回溯。但是，与其相关的语法（如果不是左因子化）则无法避免回溯。一种不需要任何回溯的递归下降解析形式称为预测解析。

这种解析技术被认为是递归的，因为它使用了本质上是递归的上下文无关文法。

回溯

自顶向下解析器从根节点（开始符号）开始，并将输入字符串与产生式规则匹配以替换它们（如果匹配）。要理解这一点，请考虑以下 CFG 示例

S → rXd | rZd
X → oa | ea
Z → ai

对于输入字符串：read，自顶向下解析器将表现如下

它将从产生式规则中的 S 开始，并将它的结果与输入的最左字母（即“r”）匹配。S 的产生式 (S → rXd) 与其匹配。因此，自顶向下解析器将前进到下一个输入字母（即“e”）。解析器尝试展开非终结符“X”并从左侧检查其产生式 (X → oa)。它与下一个输入符号不匹配。因此，自顶向下解析器回溯以获得 X 的下一个产生式规则 (X → ea)。

现在解析器以有序的方式匹配所有输入字母。字符串被接受。

预测分析器

预测分析器是一种递归下降分析器，它能够预测要用于替换输入字符串的产生式。预测分析器不会出现回溯问题。

为了完成其任务，预测分析器使用一个向前看指针，该指针指向下一个输入符号。为了使分析器免于回溯，预测分析器对语法施加了一些约束，并且只接受称为 LL(k) 语法的语法类别。

预测分析使用堆栈和分析表来分析输入并生成语法树。堆栈和输入都包含一个结束符号$，表示堆栈为空且输入已消耗。解析器参考分析表来根据输入和堆栈元素组合做出任何决策。

在递归下降分析中，解析器可能有多个产生式可供选择，用于单个输入实例，而在预测分析中，每个步骤最多只有一个产生式可供选择。在某些情况下，可能没有与输入字符串匹配的产生式，导致解析过程失败。

LL 分析器

LL 分析器接受 LL 语法。LL 语法是上下文无关语法的子集，但有一些限制以获得简化版本，以便于实现。LL 语法可以通过递归下降或表驱动两种算法来实现。

LL 分析器表示为 LL(k)。LL(k) 中的第一个 L 表示从左到右解析输入，第二个 L 表示最左推导，k 本身表示向前看的数量。通常 k = 1，因此 LL(k) 也可写为 LL(1)。

LL 解析算法

为了方便解释，我们可以坚持使用确定性 LL(1) 分析器，因为表的规模会随着 k 值的增加呈指数增长。其次，如果给定的语法不是 LL(1)，那么通常它对于任何给定的 k 来说也不是 LL(k)。

以下是 LL(1) 解析算法

Input: 
   string ω 
   parsing table M for grammar G

Output:
   If ω is in L(G) then left-most derivation of ω,
   error otherwise.

Initial State : $S on stack (with S being start symbol)
   ω$ in the input buffer

SET ip to point the first symbol of ω$.

repeat
   let X be the top stack symbol and a the symbol pointed by ip.

   if X∈ Vt or $
      if X = a
         POP X and advance ip.
      else
         error()
      endif
      
   else	/* X is non-terminal */
      if M[X,a] = X → Y1, Y2,... Yk    
         POP X
         PUSH Yk, Yk-1,... Y1 /* Y1 on top */
         Output the production X → Y1, Y2,... Yk 
      else
         error()
      endif
   endif
until X = $	/* empty stack */

如果 A → α | β 是 G 的两个不同的产生式

• 则对于任何终结符，α 和 β 都不推导出以 a 开头的字符串。

• α 和 β 中最多只有一个可以推导出空字符串。

• 如果 β → t，则 α 不推导出以 FOLLOW(A) 中的终结符开头的任何字符串。