parsing - 递归下降解析器的实现

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);
    }
}

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()，然后回发。

正如克里斯托弗指出的，你的语法有一种叫做悬空 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)