使用递归语法的自顶向下解析

Question

我在学校有一个作业告诉我们在 Java 中创建一个遵循以下语法的自上而下的解析器：

    assign = id , '=' , expr , ';' ;
    expr = term , [ ( ’+’ | ’-’ ) , expr ] ;
    term = factor , [ ( ’*’ | ’/’) , term] ;
    factor = int | ’(’ , expr , ’)’ ;

我想我已经理解了解析的基本概念，例如"if we have an id, check if the next token is a '=' and the next is an expr, and if the next after that is a ';'"。正确吗？

现在，如果我想检查传入的输入是否是表达式：

我检查标记以查看是否存在术语，然后检查是否存在“+标记”或“-标记”，最后检查是否存在 "expr"。但是，如果我检查那里是否有 "expr"，它将循环，并最终再次检查是否有 "expr"，然后一次又一次。

我不明白我怎样才能让它也起作用？有人可以帮助我吗？

亲切的问候，

Answer 1

OP 似乎担心如果他的 expr 规则代码调用 expr 的解析规则，它会陷入无限循环。

他不用担心！

这需要一些思考，但调用 C1 时实际发生的是被调用的 expr 规则测试一个术语。如果那是包含 expr 的加数集中的最后一项，则不会有后续的 plus/minus，C1 调用将终止，并且 return 到父解析例程，然后完成。没有循环。

如果不是最后一个术语，该术语将被解析，plus/minus将被看到，并且C1实例将再次调用C2返回expr .此递归就像一个循环迭代，并按照我们所描述的方式进行处理。

应该可以正常工作。

使用递归语法的自顶向下解析

Top-Down Parsing with recursive grammar

java

grammar

parsing

recursive-descent

topdown