SoraVWV 7 ноя в 18:06

Синтаксический анализатор на стеках и lambda-выражениях (Axolotl)

Средний

4 мин

1.1K

Туториал

В сентябре я опубликовал статью, описывающую теорию синтаксического анализатора на основе Shunting Yard. Эта статья является практическим продолжением, в которой описывается реализация синтаксического анализатора. В ближайшем будущем планируется публикация ряда статей, в которых другие реализации будут основаны на аналогичной теории. В данной статье представлена реализация с использованием lambda-выражений, которая, на мой взгляд, является наиболее простой, но наименее эффективной.

Примеры кода предоставлены на языке Java

Лексический анализатор

В рамках данной статьи лексический анализатор не будет реализован. Для понимания синтаксического анализатора достаточно нескольких интерфейсов и перечисления (enum).

Токен

На этапе синтаксического анализа нам будет нужен только тип токена. Если в языке нет знака ;, можно также добавлять доступ к номеру строки, где находится токен.

Тип токена

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

Группа типов токена

Типы токена удобно разделять на следующие группы:

delimiter — разделители. Например, скобка, запятая, точка с запятой и т.д.
operator — операторы. Например, оператор присваивания, плюс, минус и т.д.
keyword — ключевые и зарезервированные слова, частично определяющие синтаксис языка. Их нельзя использовать в качестве имен переменных, функций и т.д.
identify — имена переменных и функций.
literal — числа, строки, символы и в принципе любые константные значения.

Интерфейс взаимодействия с токенизатором

public interface TokenStream {

    @NonNull Token next();

    Token get();

    boolean hasNext();
}

Token next() — возвращает токен на текущей позиции и переходит к следующему.
Token get() — возвращает токен на текущей позиции без перемещения указателя.
boolean hasNext() — возвращает true, если есть следующий токен.

На этом описание лексического анализатора завершается. Далее перейдем к синтаксическому анализу.

Архитектура синтаксического анализатора

В предыдущей статье рассматривались три стека: стек операторов, стек состояний и результативный стек. В реализации с lambda-выражениями будет использоваться только стек состояний.

Основные элементы синтаксического анализатора

Состояние в данном анализаторе — это обработчик какой-либо структуры синтаксиса или ее части.

Синтаксический анализатор включает:

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

Основные правила реализации

Управляющая часть добавляет только начальное состояние в стек.
Одно и то же состояние не должно повторяться на вершине стека подряд.
Состояние обязано либо исключить себя из стека, либо добавить новые на вершину.

Реализация управляющей части

private final TokenStream stream;

private final Stack<State> states = new Stack<>();

public @NonNull FileNode analyze() {
    FileNode file = new FileNode();
    states.push(new FileState(states));

    while(states.size() != 0) {
        /*
         * Проверяем, не повторилось ли состояние и
         * не замкнулись ли они между собой.
        */
        states.peek().analyze();
    }

    return file;
}

Проверки, описанные в комментариях, необходимы только в том случае, если вы не можете утверждать, что все состояния реализованы корректно (то есть всегда.. но в рамках статьи опустим этот момент).

Помимо этого данная реализация предусматривает восстановление после ошибок. Например, допускается ставить try-catch над выполнением analyze состояния и удаления состояния в случае ошибки (в реализации с восстановлением после ошибок необходимо подправить правило №1). Перед этим необходимо провести восстановление после ошибок в пределах состояния, если это предоставляется возможным.

Реализация состояний и контроллера состояний

Определим State для дальнейшей работы

public interface State {

    void analyze();
}

В реализации контроллера состояний напишем несколько статических методов:

void custom(State state) — добавляет в стек заданное состояние, которое затем себя удаляет.
void body(Consumer<List<Node>> result) — добавляет состояние для обработки тела функции (например, объявления переменных, условий) и передает результат через result.
void expression(Consumer<Expression> result) — добавляет состояние для обработки выражений и передает его через result.

Методы body() и expression() для соответствующих состояний имеют множество тонкостей, и позже им будет посвящена отдельная статья.

Пример реализации if-else

Рассмотрим реализацию для простейшего if-else и предположим, что у нас уже есть состояния для анализа выражений и блоков кода. Чтобы удовлетворить правилам 2 и 3, if-else разбивается на несколько состояний. Добавляем состояния в обратном порядке, учитывая стек:

Обрабатываем TokenType.IF и TokenType.LEFT_PARENT.
Добавляем в стек состояние для expression, направляя результат в объект условной конструкции.
Добавляем состояние для body, направляя результат в объект условной конструкции.
Проверяем наличие TokenType.ELSE. Если else найден, добавляемbody, направляя результат в объект условной конструкции.
Передаем итоговый объект через lambda-выражение.

Записав действия в обратном порядке, получаем следующую реализацию состояния:

  public static void analyze(Consumer<IfStatement> result) {
    IfStatement ifStatement = new IfStatement();

    StateController.custom(() -> result.accept(ifStatement));
    StateController.custom(() -> {
        if (analyzer.boolEat(TokenType.ELSE))
            StateController.body(ifStatement::setElseBody);
    });
    StateController.body(ifStatement::setBody);
    StateController.custom(() -> analyzer.eat(TokenType.RIGHT_PARENT));
    StateController.custom(() -> {
        analyzer.eat(TokenType.IF);
        analyzer.eat(TokenType.LEFT_PARENT);
        StateController.expression(ifStatement::setExpression);
    });
  }

@NonNull Token eat(TokenType type) — возвращает текущий токен и переходит на следующий, если находит его. Если тип не совпал - выдает ошибку.
boolean boolEat(TokenType type) — возвращает true и переходит на следующий токен, если тип совпал. Если тип не совпадает, то выдает false.

Итоги

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

Теги:

Хабы: