Синтаксический анализ для самых маленьких. Часть 3.

Итак, наконец-то мы добрались до самого главного - собственно написания синтаксического анализатора. Повторюсь, что результатом работы синтаксического анализатора является абстрактное синтаксическое дерево.





Для построения абстрактного синтаксического дерева воспользуемся методом рекурсивного спуска. Этот метод лучше всего подходит для ручной реализации синтаксического анализатора. Смысл метода интуитивно прост и понятен: на каждый нетерминал грамматики мы пишем метод, реализация которого включает вызовы методов подчиненных нетерминалов.

Напомню, грамматика нашего языка выглядит так:

1. expression =  multExpression (('+'|'-') multExpression)*
2. multExpression = atom (('*'|'/') atom)*
3. atom = NUMBER | '(' expression ')'

Для реализации алгоритма синтаксического анализа напишем класс MathParser, который содержит метод parse:

package ru.blogspot.toolkas.math.lexer;
public class MathParser {
    public Expression parse(List lexems) throws MathParseException;
}

Таким образом, синтаксический анализатор принимает лист лексем от лексического анализатора и возвращает Expression, который воплощает в себе синтаксическую структуру математического выражения.
Разберем подробнее классы и структуры синтаксического анализатора.

MathParseException - класс исключения при возникновении ошибки синтаксического анализа (другими словами - при несоответствии входного потока лексем грамматике языка)

package ru.blogspot.toolkas.math.parser;

public class MathParseException extends Exception {
    public MathParseException() {
    }

    public MathParseException(String message) {
        super(message);
    }

    public MathParseException(String message, Throwable cause) {
        super(message, cause);
    }

    public MathParseException(Throwable cause) {
        super(cause);
    }

    public MathParseException(String message, Throwable cause, boolean enableSuppression, boolean writableStackTrace) {
        super(message, cause, enableSuppression, writableStackTrace);
    }
}

Expression - интерфейс, описывающий любой синтаксический элемент программы, который может иметь значение (в том числе и все выражение в целом):

package ru.blogspot.toolkas.math.parser.ast;

public interface Expression {
    double eval() throws Exception;
}

Метод eval() позволяет получить значение выражения.

Итак, согласно грамматике языка метод parse будет иметь следующую реализацию:

public Expression parse(List lexems) throws MathParseException {
    Expression result = expression(lexems);

    consume(lexems, Token.EOF);

    return result;
}

Метод expression умеет разбирать нетерминал expression.
Метод consume читает из потока лексем очередную лексему и проверяет, что эта лексема типа EOF. Если это не так - происходит ошибка синтаксического анализа.

Теперь рассмотрим метод expression. Реализация этого метода должна соответствовать правилу грамматики:

1. expression =  multExpression (('+'|'-') multExpression)*

Говоря обычными словами: expression - это или одиночный multExpression или последовательность multExpression, разделенные знаком '+' или '-'.

Таким образом метод expression можно написать так:

private Expression expression(List lexems) throws MathParseException {
    Expression result = multExpression(lexems);

    while (true) {
    if (check(lexems, Token.OPERATOR, "+")) {
        Expression right = multExpression(lexems);
        result = new Add(result, right);
            continue;
        }

        if (check(lexems, Token.OPERATOR, "-")) {
            Expression right = multExpression(lexems);
            result = new Minus(result, right);
            continue;
        }

        break;
    }
    return result;
}

Классы Add и Minus выглядят так:

package ru.blogspot.toolkas.math.parser.ast;

public class Add implements Expression {
    private final Expression left;
    private final Expression right;

    public Add(Expression left, Expression right) {
        this.left = left;
        this.right = right;
    }

    public Expression getLeft() {
        return left;
    }

    public Expression getRight() {
        return right;
    }

    @Override
    public double eval() throws Exception {
        return left.eval() + right.eval();
    }
}

и

package ru.blogspot.toolkas.math.parser.ast;

public class Minus implements Expression {
    private final Expression left;
    private final Expression right;

    public Minus(Expression left, Expression right) {
        this.left = left;
        this.right = right;
    }

    public Expression getLeft() {
        return left;
    }

    public Expression getRight() {
        return right;
    }

    @Override
    public double eval() throws Exception {
        return left.eval() - right.eval();
    }
}

Метод check читают следующую лексему, проверяет ее тип и значение. Если они соответствуют переданным в метод check аргументам - анализатор возвращает true и переходит к следующей лексеме. Если же не соответствуют - метод check возвращает false.

Перейдем к методу multExpression. Ему соответствует правило грамматики:

1. multExpression = atom (('*'|'/') atom)*

Реализация этого метода очень похожа на реализацию метода expression:

private Expression multExpression(List lexems) throws MathParseException {
    Expression result = atom(lexems);

    while (true) {
    if (check(lexems, Token.OPERATOR, "*")) {
        Expression right = atom(lexems);
        result = new Multiply(result, right);
            continue;
        }

        if (check(lexems, Token.OPERATOR, "/")) {
            Expression right = atom(lexems);
            result = new Divide(result, right);
            continue;
        }

        break;
    }

    return result;
}

Классы Multiply и Divide устроены аналогично классам Plus и Minus.

Осталось последнее правило грамматики:

1. atom = NUMBER | '(' expression ')'

И ему соответствует метод atom:

 private Atom atom(List lexems) throws MathParseException {
    if (check(lexems, Token.NUMBER)) {
        double value = Double.parseDouble(prev(lexems).getValue());
        return new NumberAtom(value);
    } else if(check(lexems, Token.BRACKET, "(")) {
        Expression expression = expression(lexems);
        consume(lexems, Token.BRACKET, ")");
        return new ExpressionAtom(expression);
    }

    throw new MathParseException("unexpected atom lexem: " + current(lexems));
}

Исходный код используемых классов:
Atom - базовый класс выражений, выражаемых методом atom.

package ru.blogspot.toolkas.math.parser.ast;

public abstract class Atom implements Expression {

}

NumberAtom - число, представляемое токеном NUMBER.

package ru.blogspot.toolkas.math.parser.ast;

public class NumberAtom extends Atom {
    private final double value;

    public NumberAtom(double value) {
        this.value = value;
    }

    public double getValue() {
        return value;
    }

    @Override
    public double eval() throws Exception {
        return value;
    }
}

ExpressionAtom - expression в круглых скобках.

package ru.blogspot.toolkas.math.parser.ast;

public class ExpressionAtom extends Atom {
    private final Expression expression;

    public ExpressionAtom(Expression expression) {
        this.expression = expression;
    }

    @Override
    public double eval() throws Exception {
        return expression.eval();
    }
}

Также синтаксический анализатор содержит вспомогательные методы check, consume и так далее, реализацию которых можно посмотреть на GitHub, а тут можно посмотреть модульные тесты для него.

Вычисление результата

Теперь, когда синтаксический анализатор готов, перейдем к цели нашей программы - вычислению выражения. Для этого напишем 2 класса:

MathEvaluator - класс, который инкапсулирует в себе лексический анализ, синтаксический анализ и непосредственно вычисление результата:

package ru.blogspot.toolkas.math.evaluator;

import ru.blogspot.toolkas.math.lexer.Lexem;
import ru.blogspot.toolkas.math.lexer.MathLexer;
import ru.blogspot.toolkas.math.parser.MathParser;
import ru.blogspot.toolkas.math.parser.ast.Expression;

import java.util.List;

public class MathEvaluator {
    public double eval(String line) throws Exception {
        MathLexer lexer = new MathLexer(line);
        List lexems = lexer.tokenize();

        MathParser parser = new MathParser();
        Expression expression = parser.parse(lexems);

        return expression.eval();
    }
}

MathConsole - класс, который читает введенные выражения пользователя и выдает результат:

package ru.blogspot.toolkas.math;

import ru.blogspot.toolkas.math.evaluator.MathEvaluator;

import java.util.Scanner;

public class MathConsole {
    public static void main(String[] args) throws Exception {
        MathEvaluator evaluator = new MathEvaluator();
        try (Scanner scanner = new Scanner(System.in)) {
            System.out.println("expr>>");
            while (scanner.hasNextLine()) {
                String line = scanner.nextLine();

                if (line == null) {
                    continue;
                }

                if ("exit".equals(line.trim())) {
                    break;
                }

                double value = evaluator.eval(line);
                System.out.println(value);
                System.out.println("expr>>");
            }
        }
    }
}

Заключение

Итак, на этом краткое погружение в теорию и практику синтаксического анализа считаю завершенным.  Мы написали построчный калькулятор арифметических выражений, создали лексический анализатор, синтаксический анализатор, строящий абстрактное синтаксическое дерево методом рекурсивного спуска. Надеюсь, что информация, изложенная в этих статьях, кому-то окажется полезной и интересной. Удачи в исследованиях!

P.S. для прагматиков

Все описанное выше интересно, если вы хотите изучить лексический и синтаксический анализ изнутри. Если же вы нацелены на результат, то милости прошу - используйте готовые и проверенные временем инструменты:

• Lex
• Yacc
• Antlr
• Javacc
• Flex

И многие многие другие)))