Написание простого DSL компилятора на Delphi (4. Парсер)

Перевод поста Writing a Simple DSL Compiler with Delphi (4. Parser).

Эта статья представляет собой описание парсера используемого для моего игрушечного языка программирования. Если вы только начинаете читать эту серию, то я бы рекомендовал вам начать с этого поста.

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

После перерыва я вернулся к серии про мой "игрушечный компилятор". Сейчас я опишу работу парсера — части кода которая читает входной поток (обычно в форме токенов) и генерирует внутреннее представление программы (в моём случае абстрактное синтаксическое дерево).

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

Мой парсер представлен как очень простой интерфейс. Он будет принимать код для разбора (как строку), ссылку на токинизатор которые должен использоваться для чтения входного потока и ссылку на корневой элемент результирующего AST. Функция вернёт False если разбор не удастся, в этом случае вызывающая сторона может преобразовать интерфейс парсера к ISimpleDSLErrorInfo для получения большей информации об ошибке.

Так как программа на моём языке содержит только функции, то реализация функции Parse очень простая. Она заполняет несколько полей чтобы любая часть парсера имела доступ до соответствующей информации, инициализирует буфер предварительного просмотра (FLookaheadIdent) и разбирает функцию за функцией пока разбор не будет ошибки или токинезатор не сообщит что он достиг конца кода.

Я не собираюсь показывать весь код парсера в этой короткой статье, только метод ParseFunction. Он ожидает найти идентификатор (название функции), с последующей левой круглой скобкой, с последующим, возможно пустым, списком разделённым запятыми идентификаторов (параметры функции), с последующей круглой закрывающейся скобкой и последующим блоком (тело функции).

ParseFunction сначала берет идентификатор (название функции). Затем создаёт запись в глобальной таблице функций потому что она может нам понадобится в других частях парсера если функция рекурсивно вызывает себя. По этой же причине она также будет сохранять интерфейс элемента AST функции в FContext.CurrentFunc.

Затем она проверяет токен tkLeftParen. Если он присутствует, она войдёт в цикл с поиском идентификаторов (названий параметров) либо закрывающей скобки (конец списка параметров) и сохранит все имена параметров в AST (func.ParamNames.Add).

Если всё хорошо, она вызовет ParseBlock для разбора тела функции и сохранит результат в AST (func.Body := block).

Токены всегда выбираются функцией FetchToken которая принимает список допустимых токенов, пропуская все пробелы и возвращает найденную пару токен\идентификатор (или набор информации об ошибке включая положение в коде если встретился ошибочный токен).

Так же как токинезатор, парсер использует подход "помести назад" (push back). Когда он обнаруживает что прочитал лишний токен, он может поместить его обратно вызовом PushBack. Функция GetToken сначала смотрит в этот буфер и вызывает tokenizer.GetToken если буфер пустой.

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

Если вы нашли ошибку, пожалуйста, выделите фрагмент текста и нажмите Ctrl+Enter.

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *