递归下降解析器实现

Question

我希望编写一些递归下降解析器的伪代码。但是我没有编写此类代码的经验。我已经阅读了一些在线示例，但它们仅适用于使用数学表达式的语法。以下是我正在构建解析器的语法规则。

S -> if E then S | if E then S else S | begin S L | print E

L -> end | ; S L

E -> i

我必须编写方法S()、L()和E()，并返回一些错误信息，但是我在网上找到的教程没有什么帮助。有没有人能指点我方向并给我一些示例呢？

我想用C#或Java语法编写它，因为这样更容易理解。

---

更新

public void S() {
    if (currentToken == "if") {
        getNextToken();
        E();

        if (currentToken == "then") {
            getNextToken();
            S();

            if (currentToken == "else") {
                getNextToken();
                S();
                Return;
            }
        } else {
            throw new IllegalTokenException("Procedure S() expected a 'then' token " + "but received: " + currentToken);
        } else if (currentToken == "begin") {
            getNextToken();
            S();
            L();
            return;
        } else if (currentToken == "print") {
            getNextToken();
            E();
            return;
        } else {
            throw new IllegalTokenException("Procedure S() expected an 'if' or 'then' or else or begin or print  token " + "but received: " + currentToken);
        }
    }
}


public void L() {
    if (currentToken == "end") {
        getNextToken();
        return;
    } else if (currentToken == ";") {
        getNextToken();
        S();
        L();
        return;
    } else {
        throw new IllegalTokenException("Procedure L() expected an 'end' or ';' token " + "but received: " + currentToken);
    }
}


public void E() {
    if (currentToken == "i") {
        getNextToken();
        return;
    } else {
        throw new IllegalTokenException("Procedure E() expected an 'i' token " + "but received: " + currentToken);
    }
}

- user1072706

---

我强烈推荐阅读《编译原理》这本书，以便更好地掌握递归下降（和LR）解析工具。它写得很好，并提供了令人印象深刻的语言识别广度。 - sarnold

我强烈建议查看Wikipedia递归下降解析页面底部的外部链接也会有所帮助。 - gbulmer

Answer 1

递归下降解析基本上是将文法中的每个非终结符转换为一个过程，然后在每个过程内部检查当前正在查看的标记是否与对应于该过程的非终结符号右侧所期望看到的内容相匹配。如果匹配，则继续应用该产生式，如果不匹配，则会遇到错误，必须采取一些行动。

因此，在您的情况下，正如您上面提到的那样，您将拥有以下过程：S()、L() 和 E()。我将给出一个示例，说明如何实现 L()，然后您可以尝试自己完成 S() 和 E()。

还需要注意的是，您需要使用其他程序对输入进行分词，然后您只需向该程序请求从输入中获取下一个标记。

/**
 * This procedure corresponds to the L non-terminal
 * L -> 'end'
 * L -> ';' S L
 */ 
public void L()
{
   if(currentToken == 'end')
   {
      //we found an 'end' token, get the next token in the input stream
      //Notice, there are no other non-terminals or terminals after 
      //'end' in this production so all we do now is return
      //Note: that here we return to the procedure that called L()
      getNextToken();
      return; 
   } 
   else if(currentToken == ';')
   {
      //we found an ';', get the next token in the input stream
      getNextToken();
      //Notice that there are two more non-terminal symbols after ';'
      //in this production, S and L; all we have to do is call those
      //procedures in the order they appear in the production, then return
      S();
      L();
      return;
   }
   else
   {
      //The currentToken is not either an 'end' token or a ';' token 
      //This is an error, raise some exception
      throw new IllegalTokenException(
          "Procedure L() expected an 'end' or ';' token "+
          "but received: " + currentToken);
   }
}

现在请尝试使用S()和E()函数，并回复。

另外，正如Kristopher指出的那样，你的语法存在悬挂else的问题，这意味着你有一个以相同方式开始直到某个点的产生：

S -> if E then S 
S -> if E then S else S

如果你的解析器看到了一个'if'标记，那么它应该选择哪个产生式来处理输入呢？答案是它不知道应该选择哪一个，因为与人类不同，编译器无法向前查找输入流以搜索'else'标记。这是一个简单的问题，可以通过应用称为左优化的规则来修复，非常类似于如何分解代数问题。

你所要做的就是创建一个新的非终端符号S'（S-prime），它的右侧将保存那些不通用的产生式部分，这样你的S产生式现在变成了：

S  -> if E then S S'
S' -> else S 
S' -> e   
(e is used here to denote the empty string, which basically means there is no   
 input seen)

- Hunter McMillen

---

我已经更新了我的答案，但是我还没有修复悬挂的else。创建新的非终端符号是解决这个问题的唯一方法吗？我不知道是否允许我更改语法。 - user1072706

递归下降解析器需要是具有预测性的，也就是说它需要知道在每种情况下应该去哪里，应该应用哪个产生式；它没有选项可以说“哎呀，我不应该在这里，我需要返回到调用堆栈”。对于这个问题，您只需检查else是否存在，因为它们位于同一非终端中，但更好的解决方案是修改语法。您上面所做的方式应该可以正常工作。 - Hunter McMillen

Answer 2

这不是最容易入手的语法，因为在你的第一个产生式规则上有无限量的向前看：

S -> if E then S | if E then S else S |  begin S L | print E

考虑

if 5 then begin begin begin begin ...

我们什么时候会决定使用else语句？

另外，请考虑以下内容。

if 5 then if 4 then if 3 then if 2 then print 2 else ...

现在，else是不是应该与if 5 then片段绑定在一起呢？如果不是，那很好，但要明确说明。

你可以根据else规则重写语法（可能需要），等效于：

S -> if E then S (else S)? | begin S L | print E
L -> end | ; S L
E -> i

这可能是您想要的，也可能不是。但是，伪代码在这里有点突出。

define S() {
  if (peek()=="if") {
    consume("if")
    E()
    consume("then")
    S()
    if (peek()=="else") {
      consume("else")
      S()
    }
  } else if (peek()=="begin") {
    consume("begin")
    S()
    L()
  } else if (peek()=="print") {
    consume("print")
    E()
  } else {
    throw error()
  }
}

define L() {
  if (peek()=="end") {
    consume("end")
  } else if (peek==";")
    consume(";")
    S()
    L()
  } else {
    throw error()
  }
}

define E() {
  consume_token_i()
}

对于每个可选项，我创建了一个if语句来查看唯一的前缀。任何匹配尝试的最终else都是一个错误。我在遇到关键字并调用相应的生成规则函数时消耗它们。

从伪代码到真正的代码不是太复杂，但也不是微不足道的。那些Peek和Consume可能实际上不作用于字符串。在令牌上操作要容易得多。简单地遍历句子并将其消耗并不完全等同于解析它。您会希望在消耗这些部分时进行某些操作，可能会构建一个解析树（这意味着这些函数可能返回某些内容）。在高层次上抛出错误可能是正确的，但您需要将一些有意义的信息放入错误中。此外，如果您需要前瞻，事情会变得更加复杂。

当涉及到这些问题时，我会推荐Terence Parr的《语言实现模式》（他编写了antlr，递归下降解析器生成器）。《龙书》（Aho等人在评论中推荐）也很好（它仍然可能是编译器课程中主要的教科书）。

- ccoakley

Answer 3

上学期我在一门编程语言课中教授了解析部分（实际上只是协助）。我非常推荐从我们的网页查看解析幻灯片：这里。对于递归下降解析，您需要问自己以下问题： “我已经解析了一部分非终端符，现在我到了一个能够选择下一步要解析什么的点。接下来我看到什么将决定我处于哪个非终端符中。”

顺便说一下，你的文法展示了一种非常常见的歧义 - “悬挂else”，这种歧义自Algol时代以来一直存在。在移位约简解析器（通常由解析器生成器生成）中，这会产生移位/约简冲突，您通常会选择任意移位而不是缩减，从而得到常见的“最大匹配”原则。（因此，如果您看到“if (b) then if (b2) S1 else S2”，请将其解释为“if (b) then { if (b2) { s1; } else { s2; } }”）

让我们将此从您的文法中删除，并使用稍微简单一些的文法进行工作：

T -> A + T
 |   A - T
 |   A
A -> NUM * A
   | NUM / A
   | NUM

我们还假设NUM是从词法分析器中获取的（即它只是一个标记）。这个语法是LL(1)的，也就是说，你可以使用一个基础的递归下降解析器来解析它。算法的工作方式如下：

parse_T() {
  a = parse_A();
  if (next_token() == '+') {
    next_token();  // advance to the next token in the stream
    t = parse_T();
    return T_node_plus_constructor(a, t);
  }
  else if (next_token() == '-') {
    next_token();  // advance to the next token in the stream
    t = parse_T();
    return T_node_minus_constructor(a, t);
  } else {
    return T_node_a_constructor(a);
  }
}
parse_A() {
  num = token(); // gets the current token from the token stream
  next_token();  // advance to the next token in the stream
  assert(token_type(a) == NUM);
  if (next_token() == '*') {
    a = parse_A();
    return A_node_times_constructor(num, a);
  }
  else if (next_token() == '/') {
    a = parse_A();
    return A_node_div_constructor(num, a);
  } else {
    return A_node_num_constructor(num);
  }
}

在语法中，对于每个非终端符号：首先解析第一个元素，然后查看您需要查看的内容以决定下一步解析什么。重复此过程直到完成！请注意，这种解析通常不适用于算术操作。递归下降解析器（除非使用尾递归技巧）将无法生成左侧派生。特别是，您不能编写类似“a- > a-a”的左递归规则，其中最左关联性确实必要！这就是为什么人们通常使用更高级的解析器生成工具的原因。但是，递归下降技巧仍然值得了解和尝试。

- Kristopher Micinski

---

你可以使用递归下降来生成解析树，然后改变遍历顺序以处理算术。 - Hunter McMillen

@HunterMcMillen，确实如此，这样做是可行的，但对于更复杂的结构来说，这是一种恶劣的hack方法，而当你可以使用解析器生成器时，最好使用它来代替。 - Kristopher Micinski

YACC和Bison是你的好朋友，我同意。当我学习这些东西时，我们遇到了与你上面提到的解析算术问题相同的问题，我们的教授使用访问者模式创建了一个非常优雅的解决方案。 - Hunter McMillen

没错，这正好对应于函数式语言中使用尾递归函数进行处理和后处理的情况。您还可以通过玩一个小技巧来一次性实现它们，这样可以使用尾递归解析器获取最左派生。这就是我在帖子中提到的技术。（道义上它非常相似...） - Kristopher Micinski

@KristopherMicinski 在 if (next_token() == '+') 和 next_token(); // advance to the next token in the stream 中的 next_token() 函数是不同的，对吗？第一个 next_token 意味着在令牌队列中查看一个令牌，而第二个 next_token 意味着 advance_token，这意味着从令牌队列中删除查看到的令牌，并为查看到的令牌设置新值。有时候，我认为“next”这个词很容易让人感到困惑，因为在 Hunter McMillen 的回答中，它只是指“CurrentToken”，而在 ccoakley 的回答中，它指的是“peeked token”，对吗？ - ollydbg23