如何为arimethic计算java解析器编写递归while循环

Question

我已经为算术计算解析器编写了具有以下语法的代码

'exp':: = term | term + exp | term - exp

term :: =整数文字

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

在这个应用程序中，我试图通过使用token方法检查是否存在下一个Tokenizer.hasNext()，如果token是Token.Type.Add类型然后返回一个新的Exp与当前的字面术语和操作和下一个解析通过parse()方法。我已经定义了各种类，如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：对于以大写字母开头的变量名称，它不是好的样式）。然后读取+标记并进入else，调用parse。现在，parse再次调用parseLit，其中读取了65的字面值。令牌流现在为空，因此parseLit返回。 parse也返回，因为令牌流仍然是空的（请注意，从未输入parse中的循环）。

从parse返回到parseLit的值是文字表达式65，但parseLit实际上从未使用过该值。它只是调用parse并抛出结果。

所以现在我们回到parseLit的第一个电话，parse刚刚回来。因此令牌流为空，我们退出循环。 Lit的内容是“73”，所以这是从parseLit这个调用返回的内容。现在我们返回第一次调用parse，它只返回parseLit的结果，因为令牌流是空的，所以循环永远不会进入。

所以这里出了问题的是你消耗了所有的输入而没有实际构建树来进行添加。意图执行该操作的代码（即while中的parse循环）永远不会运行，因为你已经在它进入循环之前已经读过所有标记因为parseTerm中的循环和第二次调用parse（其结果你丢弃） ）。

你的term的语法规则不使用exp，所以parseTerm不应该调用parse。规则也不是递归的，所以parseTerm不应该包含循环。 parseTerm应该做的就是读取一个应该是文字的标记，然后返回相应的Exp对象。