Как написать рекурсивный цикл while для ариметического вычисления парсера Java - PullRequest
Новая
       35

Как написать рекурсивный цикл while для ариметического вычисления парсера Java

0 голосов
/ 18 апреля 2019

Я написал код для анализатора арифметических вычислений со следующей грамматикой

'exp' :: = term |срок + опыт |term - exp

term :: = целочисленный литерал

И я закончил синтаксический анализатор для одного терма, содержащего только целочисленный литерал, однако я не могу достичь цели операций синтаксического анализа в строковом уравнении.

В этом приложении я пытался проверить, есть ли следующий token подарок, используя метод Tokenizer.hasNext(), и если token имеет тип Token.Type.Add, тогда верните новый Exp стекущий буквенный термин и операция и следующий 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;
        }

1 Ответ

2 голосов
/ 18 апреля 2019

Давайте пройдемся по этому для ввода 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 объект для этого.

...