Синтаксический анализатор — модифицированный Shunting Yard

Перед чтением статьи рекомендуется изучить следующие материалы:

• алгоритм Дейкстры

• Shunting Yard Algorithm

Модифицированный Shunting Yard — это алгоритм синтаксического анализа, который расширяет алгоритм Дейкстры для работы не только с операторами и операндами, но и с более сложными синтаксическими конструкциями. Он сочетает элементы восходящего синтаксического анализа с ручным управлением состояниями для построения абстрактного синтаксического дерева (AST). В отличие от традиционного Shunting Yard, который фокусируется на арифметических выражениях, модифицированная версия может обрабатывать сложные конструкции языков, такие как блоки кода, вызовы функций, условия и прочие структуры.

Описание алгоритма

Алгоритм работает с тремя основными стеками:

• Стек операторов — хранит операторы выражений.

• Стек состояний — отслеживает текущий контекст анализа, например, в каком синтаксическом блоке находится парсер (вызов функции, условие, цикл).

• Результативный стек — хранит операнды, промежуточные результаты и узлы AST.

Шаг 1: Инициализация

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

Шаг 2: Чтение токенов

Лексический анализатор подает на вход синтаксическому анализатору последовательность токенов — это могут быть операнды, операторы, а также ключевые слова языка, такие как if, while, fn, скобки и другие конструкции.

Шаг 3: Обработка токенов

• Операнды (например, идентификаторы, литералы или вызовы функций) добавляются в результативный стек.

• Операторы (например, арифметические, логические или присваивания) обрабатываются с учетом их приоритета. Если оператор на вершине стека операторов имеет приоритет выше или равен текущему оператору, производится редукция: извлекаются операторы и операнды из стеков, и на их основе строится узел AST.

• Управляющие конструкции (например, if, while, вызовы функций) меняют состояние синтаксического анализатора через стек состояний. Открытие новой конструкции (например, открывающая скобка в вызове функции) добавляет новое состояние в стек состояний, а закрытие конструкции (например, закрывающая скобка) инициирует редукцию.

Шаг 4: Переходы состояний

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

Шаг 5: Редукция

Когда завершается разбор синтаксической конструкции, начинается процесс редукции. Оператор извлекается из стека операторов, операнды — из результативного стека, и на основе этих данных создается узел AST. Этот узел возвращается обратно в результативный стек, где позже будет использован для создания более высокоуровневых структур.

Шаг 6: Завершение анализа

После того, как все токены обработаны, анализатор завершает работу, выполняя редукцию оставшихся операторов и операндов в стеке. Это завершает построение AST, представляющего исходное выражение или программу.

Шаг 7: Восстановление после ошибок

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

Пример работы алгоритма

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

Пример программы:

if (x > 10) {
  y = func(a + b * c)
}

Алгоритм будет работать следующим образом:

1. Чтение токенов:

   • if → добавляется в стек состояний, указывая, что начинается условная конструкция.

   • ( → добавляется в стек операторов.

   • x, >, 10 → операнды и оператор добавляются в соответствующие стеки.

   • ) → редукция условия: оператор > извлекается, строится узел AST для сравнения x > 10.

2. Внутри блока if:

   • y = → оператор присваивания добавляется в стек операторов.

   • func( → состояние изменяется на вызов функции.

   • Аргументы функции разбираются с помощью стандартного Shunting Yard: сначала вычисляется выражение a + b * c, затем строится узел AST для вызова func.

3. Редукция:

   • В конце конструкции if, закрывающая скобка вызывает редукцию всех оставшихся операций и состояний, завершая построение AST.

Заключение

Алгоритм модифицированного Shunting Yard был описан на абстрактном уровне, поскольку его основная цель — обеспечить гибкость и возможность дальнейшего модифицирования в зависимости от специфики синтаксического анализа конкретного языка программирования. Данный подход является базовой структурой, которая может быть адаптирована под различные синтаксические конструкции. Фактическая реализация и расширение алгоритма будут зависеть от требований грамматики и особенностей анализируемого языка, что позволяет использовать его как основу для создания более сложных и мощных анализаторов.