编译器设计 - 自下而上的解析器

自下而上的解析从树的叶节点开始，向上进行，直到到达根节点。在这里，我们从一个句子开始，然后以相反的方式应用生成规则以到达起始符号。下图描述了可用的自下而上的解析器。

移位归约解析

移位归约解析使用两个独特的步骤进行自下而上的解析。这些步骤称为移位步骤和归约步骤。

• 移位步骤：移位步骤是指将输入指针推进到下一个输入符号，称为移位符号。此符号被推送到堆栈上。移位后的符号被视为解析树的单个节点。

• 归约步骤：当解析器找到完整的语法规则 (RHS) 并将其替换为 (LHS) 时，这称为归约步骤。当堆栈顶部包含句柄时，就会发生这种情况。为了归约，在堆栈上执行 POP 函数，弹出句柄并将其替换为 LHS 非终结符。

LR 解析器

LR 解析器是一种非递归、移位归约、自下而上的解析器。它使用广泛的上下文无关语法，这使其成为最有效的语法分析技术。LR 解析器也称为 LR(k) 解析器，其中 L 代表从左到右扫描输入流； R 代表反向构造最右派生，k 表示做出决策的前瞻符号数量。

有三种广泛使用的算法可用于构造 LR 解析器：

• SLR(1) – 简单 LR 解析器：
  • 适用于最小的语法类
  • 状态数很少，因此表非常小
  • 构造简单快速
• LR(1) – LR 解析器：
  • 适用于完整的 LR(1) 语法集
  • 生成大型表格和大量状态
  • 构造缓慢
• LALR(1) – 前瞻 LR 解析器：
  • 适用于中间语法的大小
  • 状态数与 SLR(1) 相同

LR 解析算法

这里我们描述了 LR 解析器的骨架算法：

token = next_token()

repeat forever
   s = top of stack
   
   if action[s, token] = “shift si” then
      PUSH token
      PUSH si 
      token = next_token()
      
   else if action[s, token] = “reduce A::= β“ then 
      POP 2 * |β| symbols
      s = top of stack
      PUSH A
      PUSH goto[s,A]
      
   else if action[s, token] = “accept” then
      return
      
   else
      error()

LL 与 LR