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

• 

  简述

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

  

  Shift-Reduce 解析

  Shift-reduce 解析使用两个独特的步骤进行自下而上的解析。这些步骤被称为移位步骤和减少步骤。

  • Shift step：移位步是指输入指针前进到下一个输入符号，称为移位符号。该符号被压入堆栈。移位的符号被视为解析树的单个节点。
  • Reduce step：当解析器找到一个完整的语法规则（RHS）并将其替换为（LHS）时，称为reduce-step。当堆栈顶部包含句柄时会发生这种情况。为了减少，在堆栈上执行一个 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

  二	LR
  进行最左推导。	反向进行最右边的推导。
  从堆栈上的根非终结符开始。	以堆栈上的根非终结符结束。
  当堆栈为空时结束。	从一个空堆栈开始。
  使用堆栈来指定仍然可以预期的内容。	使用堆栈来指定已经看到的内容。
  自上而下构建解析树。	自下而上构建解析树。
  连续从堆栈中弹出一个非终结符，并推动相应的右侧。	尝试识别堆栈的右侧，将其弹出，并压入相应的非终结符。
  扩展非终端。	减少非终端。
  当它从堆栈中弹出一个终端时读取终端。	在将终端压入堆栈时读取终端。
  解析树的前序遍历。	解析树的后序遍历。