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

В сентябре я опубликовал статью, описывающую теорию синтаксического анализатора на основе 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-выражениями будет использоваться только стек состояний.

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

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

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

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

2. Состояния, содержащие основной метод для анализа части конструкции.

3. Контроллер состояний, который хранит шаблоны и часто используемые состояния.

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

1. Управляющая часть добавляет только начальное состояние в стек.

2. Одно и то же состояние не должно повторяться на вершине стека подряд.

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

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

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 разбивается на несколько состояний. Добавляем состояния в обратном порядке, учитывая стек:

1. Обрабатываем TokenType.IF и TokenType.LEFT_PARENT.

2. Добавляем в стек состояние для expression, направляя результат в объект условной конструкции.

3. Добавляем состояние для body, направляя результат в объект условной конструкции.

4. Проверяем наличие TokenType.ELSE. Если else найден, добавляемbody, направляя результат в объект условной конструкции.

5. Передаем итоговый объект через 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.

Итоги

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