Синтаксический анализ для самых маленьких. Часть 2. Пишем лексический анализатор

В прошлой статье мы кратко обсудили процесс анализа выражений и составили грамматику нашего калькулятора. В этой статье - мы напишем код лексического анализатора.

Код будем писать на Java 8.



Итак, лексический анализатор - это программа, которая преобразует поток символов в поток лексем.
Лексемы могут принадлежать к разным классам. При этом в процессе анализа может возникнуть ошибка. Для того, чтобы выразить эти концепции явно в коде, создадим следующие классы:

TokenizeException - класс исключения при возникновении ошибки лексического анализа:

package ru.blogspot.toolkas.math.lexer;

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

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

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

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

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

Token - перечисление, которое содержит список токенов:

package ru.blogspot.toolkas.math.lexer;

public enum Token {
    NUMBER, OPERATOR, BRACKET, EOF;
}

Lexem - класс лексемы, который хранит тип лексемы (токен) и значение:

package ru.blogspot.toolkas.math.lexer;

public class Lexem {
    private final Token token;
    private final String value;

    public Lexem(Token token, String value) {
        this.token = token;
        this.value = value;
    }

    public Token getToken() {
        return token;
    }

    public String getValue() {
        return value;
    }

    @Override
    public String toString() {
        return "Lexem{" +
                "token=" + token +
                ", value='" + value + '\'' +
                '}';
    }
}

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

package ru.blogspot.toolkas.math.lexer;
public class MathLexer {
    public List tokenize() throws TokenizeException;
}

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

Не будем тянуть рекурсию за хвост - сразу приведу полный код лексического анализатора:

package ru.blogspot.toolkas.math.lexer;

import org.apache.commons.lang.StringUtils;

import java.util.ArrayList;
import java.util.List;
import java.util.Objects;

public class MathLexer {
    private TokenizeState state = TokenizeState.DEFAULT;
    private String expression;
    private String value = "";
    private int position = -1;

    public MathLexer(String expression) {
        Objects.requireNonNull(expression, "expression can't be null");
        this.expression = expression;
    }

    public List tokenize() throws TokenizeException {
        List lexems = new ArrayList<>();

        int ch;
        while ((ch = get()) != -1) {
            Lexem lexem = nextLexem(ch);
            if (lexem != null) {
                lexems.add(lexem);
            }
        }

        if (state != TokenizeState.DEFAULT) {
            Lexem lexem = nextLexem(ch);
            if (lexem != null) {
                lexems.add(lexem);
            }
        }

        if (StringUtils.isNotBlank(value)) {
            throw new TokenizeException("can't parse '" + value + "'");
        }

        lexems.add(new Lexem(Token.EOF, null));

        return lexems;
    }

    private Lexem nextLexem(int b) throws TokenizeException {
        char ch = (char) b;

        switch (state) {
            case DEFAULT:
                if (Character.isDigit(ch)) {
                    state = TokenizeState.NUMBER_START;
                    position -= 1;
                } else if (ch == '+' || ch == '-' || ch == '*' || ch == '/') {
                    state = TokenizeState.OPERATOR;
                    position -= 1;
                } else if (ch == '(' || ch == ')') {
                    state = TokenizeState.BRACKET;
                    position -= 1;
                } else if (Character.isWhitespace(ch)) {
                    return null;
                } else {
                    throw new TokenizeException(
                            "unexpected character '" + ch + 
                                    "' in state " + state
                    );
                }
                break;
            case NUMBER_START:
                if (Character.isDigit(ch)) {
                    value += ch;
                } else if (ch == '.') {
                    value += ch;
                    state = TokenizeState.NUMBER_END;
                } else {
                    return createToken(Token.NUMBER, true);
                }
                break;
            case NUMBER_END:
                if (Character.isDigit(ch)) {
                    value += ch;
                } else {
                    return createToken(Token.NUMBER, true);
                }
                break;
            case OPERATOR:
                if (ch == '+' || ch == '-' || ch == '*' || ch == '/') {
                    value += ch;
                    return createToken(Token.OPERATOR, false);
                }

                break;
            case BRACKET:
                if (ch == '(' || ch == ')') {
                    value += ch;
                    return createToken(Token.BRACKET, false);
                }

                break;
        }
        return null;
    }

    private int get() {
        position += 1;
        return position < expression.length() ?
                expression.charAt(position) : -1;
    }

    private Lexem createToken(Token token, boolean back) {
        Lexem lexem = new Lexem(token, value);
        value = "";

        state = TokenizeState.DEFAULT;
        if (back) {
            position -= 1;
        }
        return lexem;
    }

    private enum TokenizeState {
        DEFAULT, NUMBER_START, NUMBER_END, OPERATOR, BRACKET;
    }
}

Теперь разберем приведенный выше код.
В основе лексического анализатора лежит алгоритм конечного автомата. Конечный автомат в нашем случае имеет следующие состояния:

• DEFAULT - стартовое состояние конечного автомата;
• NUMBER_START - анализ целой части числа;
• NUMBER_END - анализ дробной части числа;
• OPERATOR - анализ оператора;
• BRACKET - анализ скобок;

Лексический анализатор переходит из состояния в состояние при встрече определенных символов. 

Правила перехода из состояния в состояние можно описать так:

• DEFAULT. Получен символ цифры => переход в NUMBER_START;
• DEFAULT. Получен '+' => переход в OPERATOR;
• DEFAULT. Получен '-' => переход в OPERATOR;
• DEFAULT. Получен '*' => переход в OPERATOR;
• DEFAULT. Получен '/' => переход в OPERATOR;
• DEFAULT. Получен '(' => переход в BRACKET;
• DEFAULT. Получен ')' => переход в BRACKET;
• DEFAULT. Получен ' ' => переход в DEFAULT. Пропуск символа;
• DEFAULT. Получен любой другой символ => ошибка;
• NUMBER_START. Получена цифра => переход в NUMBER_START
• NUMBER_START. Получена точка=> переход в NUMBER_END;
• NUMBER_START. Получен любой другой символ => переход в DEFAULT.
• NUMBER_END. Получена цифра => переход в NUMBER_END;
• NUMBER_END. Получен любой другой символ => переход в DEFAULT;
• OPERATOR. Получен '+' => переход в DEFAULT;
• OPERATOR. Получен '-' => переход в DEFAULT;
• OPERATOR. Получен '*' => переход в DEFAULT;
• OPERATOR. Получен '/' => переход в DEFAULT;
• BRACKET. Получен '(' => переход в DEFAULT;
• BRACKET. Получен ')' => переход в DEFAULT;

В процессе перехода из состояния в состояние лексический анализатор иногда делает откат в чтении на символ назад - position -= 1 - для того, чтобы передать символ повторно на анализ в другом состоянии после перехода.

Также в процессе создаются лексемы - createToken(Token.BRACKET, false) - что и является конечной целью создания лексического анализатора.  

На этом, я завершаю статью про лексический анализатор. Исходный код приведенных выше классов доступен на GitHub. Там же доступен исходный код модульных тестов нашего лексического анализатора, ибо - код без тестов не код, а просто нагромождение символов(((

В следующей части мы перейдем к реализации синтаксического анализатора и построению абстрактного синтаксического дерева. Всем добра))