编译器设计 - 自顶向下解析器

  • 简述

    我们在上一章中学习了自顶向下解析技术解析输入,并从根节点开始构建解析树,逐渐向下移动到叶节点。自顶向下解析的类型如下所示:
    自顶向下解析

    递归下降解析

    递归下降是一种自顶向下的解析技术,从顶部构造解析树,从左到右读取输入。它为每个终端和非终端实体使用程序。这种解析技术递归地解析输入以生成解析树,这可能需要也可能不需要回溯。但是与之相关的语法(如果不考虑左因素)无法避免回溯。一种不需要任何回溯的递归下降解析形式称为predictive parsing.
    这种解析技术被认为是递归的,因为它使用本质上是递归的上下文无关语法。

    回溯

    自上而下的解析器从根节点(开始符号)开始,并将输入字符串与生产规则匹配以替换它们(如果匹配)。要理解这一点,请看下面的 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 Parser 接受 LL 语法。LL文法是上下文无关文法的一个子集,但在获取简化版时有一些限制,以实现简单的实现。LL 语法可以通过两种算法来实现,即递归下降或表驱动。
    LL 解析器表示为 LL(k)。LL(k) 中的第一个 L 是从左到右解析输入,LL(k) 中的第二个 L 代表最左推导,k 本身代表前瞻的数量。一般k = 1,所以LL(k)也可以写成LL(1)。
    LL解析器

    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 是 LL(1) β 是 G 的两种不同产生式:
    • 对于无终结符,α 和 β 都派生以 a 开头的字符串。
    • α 和 β 中最多有一个可以导出空字符串。
    • 如果 β → t,则 α 不会导出任何以 FOLLOW(A) 中的终端开头的字符串。