编译器设计 - 自底向上分析器

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

移进-归约分析

移进-归约分析使用两个独特的步骤进行自底向上分析。这些步骤称为移进步骤和归约步骤。

• 移进步骤：移进步骤指的是输入指针向下一个输入符号（称为移进符号）的推进。此符号被压入堆栈。移进符号被视为语法树的单个节点。

• 归约步骤：当分析器找到一个完整的语法规则（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