递归下降解析器实现

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(),和后背部.

另外,正如克里斯托弗指出你的语法有一种叫做悬挂的其他东西,意味着你有一个以相同的东西开头的作品:

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

因此,如果您的解析器看到"if"令牌,那么这会产生问题,它应该选择哪个生产处理输入？答案是它不知道选择哪一个,因为与人类不同,编译器无法向前看输入流以搜索"其他"令牌.这是一个通过应用称为Left-Factoring的规则来修复的一个简单问题,非常类似于您如何考虑代数问题.

您所要做的就是创建一个新的非终端符号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)

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 ...

我们什么时候确定这个愚蠢的其他？

另外,考虑一下

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

那么,是不是else应该绑定到if 5 then片段？如果没有,那实际上很酷,但要明确.

您可以将您的语法(可能取决于其他规则)等效地重写为:

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语句.任何匹配尝试的最后一个总是错误.当我遇到它时,我使用关键字并调用与生产规则相对应的函数.

从伪代码转换为实际代码并不是太复杂,但它并非无足轻重.那些偷看和消耗可能实际上并不是在字符串上操作.在令牌上操作要容易得多.简单地走一个句子并消费它与解析它并不完全相同.你需要做一些事情,因为你消耗了碎片,可能会建立一个解析树(这意味着这些函数可能返回一些东西).抛出错误可能在高级别上是正确的,但是您想要在错误中添加一些有意义的信息.而且,如果你需要前瞻,事情会变得更加复杂.

在查看这些问题时,我会推荐Terence Parr(编写antlr,一个递归下降解析器生成器的人)的语言实现模式.龙书(Aho,等人,在评论中推荐)也很好(它仍然可能是编译器课程中的主要教科书).