java - 如何编写用于算术计算java解析器的递归while循环

Question

我已经使用以下语法编写了算术计算解析器的代码

'exp'::= 术语 |期限 + 经验 |术语 - 表达式

术语::= 整数文字

并且我已经完成了对仅包含整数字面量的单个术语的解析器，但是，我无法实现对字符串方程中的解析操作的目标。

在这个应用程序中，我试图检查是否有下一个 token使用 Tokenizer.hasNext() 呈现方法，如果token类型为Token.Type.Add然后返回一个新的 Exp，其中包含当前的字面术语和操作以及通过 parse() 解析的下一个 Exp。方法。我定义了各种类，例如 Token(String token, Type type),Exp(Term) / Exp(Term,Op,Exp),Term(Lit),Lit(int)

Tokenizer.takeNext()将获取下一个标记并将其从当前标记器缓冲区中删除。 我根本无法解析给定方程中的运算符。

Parsing equation: 73 + 65 
73=73
Parsing equation: 10 - 4
10=10
Parsing equation: 7 + 9 + 10
7=7
Parsing equation: 5 - 1
5=5

这是我从学校讲座中学到的一般方法，这不是作业问题。任何帮助将不胜感激。

public class Token {
    public enum Type {Unknown, Lit, Add, Minus, Multiply, Division};
    private String _token = "";
    private Type _type = Type.Unknown;
}

public enum Operation {
    None (""),
    Add ("+"),
    Sub ("-"),
    Mult ("*"),
    Div ("/");

    String op;

public class Exp {

    Term _term = null;
    Exp _exp = null;
    Operation _op = null;

    public Exp(Term term) {
        _term = term;
        _op = Operation.None;
    }

    public Exp(Term term, Operation op, Exp exp) {
        _exp = exp;
        _term = term;
        _op = op;
    }

     public Exp parse(){
        Exp term = parseTerm();
        while(_tokenizer.hasNext()) {
            Token token = _tokenizer.takeNext();
            if(token.type() == Token.Type.Add) {
                Operation op = Operation.Add;
                _tokenizer.next();
                Exp exp = parse();
                term = new Exp(term._term,op,exp);
                }
            }
        return term;
    }

    // <term>   ::= <integer literal>
    public Exp parseTerm(){
        Exp exp = null;
        String Lit = "";
        while(_tokenizer.hasNext()) {
            Token token = _tokenizer.takeNext();
            if(token.type() == Token.Type.Lit)
                Lit+=token.token();
            else
                parse();
            }
        Lit lit = new Lit(Integer.parseInt(Lit));
        Term term = new Term(lit);
        exp = new Exp(term);
        return exp;
        }

Answer 1

让我们来看看输入 73 + 65 的情况:

您调用parse ，调用 parseTerm 。 parseTerm然后循环标记。对于第一个标记，它是一个文字，因此将其添加到 Lit (PS:变量名以大写字母开头不是好的风格)。然后是+ token 被读取并进入 else ，调用 parse 。现在parse来电 parseLit再次，它读取 65 的文字。 token 流现在为空，因此 parseLit返回。 parse也会返回，因为 token 流仍然为空(请注意，parse中的循环从未进入过)。

从 parse 返回的值至parseLit是文字表达式 65 ，但是parseLit从未真正使用该值。它只是调用 parse并丢弃结果。

现在我们回到了 parseLit 的第一次通话和parse刚刚回来。所以 token 流是空的，我们退出循环。 Lit的内容是“73”，这就是对 parseLit 的调用返回的结果。现在我们回到第一次调用parse ，它只返回 parseLit 的结果因为， token 流又是空的，所以永远不会进入循环。

所以这里的问题是你消耗了所有的输入而没有实际构建用于加法的树。旨在执行此操作的代码(即 while 中的 parse 循环)永远不会运行，因为由于 parseTerm 中的循环，您在进入循环之前已经读取了所有标记。第二次调用 parse (您丢弃其结果)。

您的语法规则 term不使用exp ，所以parseTerm不应该打电话 parse 。而且规则也不是递归的，所以parseTerm不应包含循环。所有这些parseTerm应该做的是读取应该是文字的单个标记，然后返回适当的 Exp对象。