Синтаксический анализатор — это часть компилятора, отвечающая за определение главных синтаксических конструкций входного языка.
Общие сведения о синтаксическом анализе
Синтаксический анализ считается самым трудоемким этапом процесса компиляции. К задачам, которые должны выполняться на данном этапе, следует отнести:
- Разборка цепи токенов, которая была сформирована лексическим анализатором.
- Реализация выявления и диагностики синтаксически недопустимых цепочек.
- Создание промежуточного отображения программы в форме тетрад.
- Обнаружение и диагностика семантических ошибок
Главным этапом подготовки к выполнению синтаксического анализа может считаться формирование формальной грамматики и управляющих таблиц анализатора. Формальная грамматика базируется на описании языка в формате Бэкуса-Наура и определяется набором правил, используемых для создания текста входной программы. В соответствии с условиями, формальная грамматика, которая описывает язык, обязана принадлежать классу SLR(1), то есть, восходящему алгоритму синтаксического разбора.
Разработка синтаксического анализатора
Синтаксический анализатор класса SLR(1) можно реализовать на базе конечного детерминированного распознавателя, имеющего стековую организацию магазинной памяти. Основным компонентом подобного распознавателя может считаться управляющая таблица, ставящая в соответствие текущему символу исследуемой цепочки и текущему состоянию автомата совокупность операций, которая позволяет выработать решение о допуске входной цепочки, о наличии ошибки, или переходу автомата в иное состояние. Непосредственно автомат и его управляющую таблицу можно проектировать независимо друг от друга, так как алгоритм распознавания цепочек не обладает зависимостью от конкретной управляющей таблицы.
SLR(1)-автомат выполняет алгоритм вида «перенос-свертка». То есть, по сути, он осуществляет восходящий разбор цепочки и должен свернуть входную цепочку к стартовому символу грамматики. Стратегическим действием такого алгоритма считается свертка определенного во входной цепочке грамматического основания к породившему ее символу. В границах создания программы компиляции, может быть построена такая грамматика входного языка, свертки которой могут быть использованы для генерации промежуточного отображения текста программы. Для этого на базе грамматики должна быть сформирована атрибутно-транслирующая грамматика, а распознающий автомат должен быть дополнен возможностями обработки атрибутов своих состояний.
Главной задачей разработки синтаксического анализатора выступает создание управляющих таблиц, способных обеспечить разбор грамматики входного языка. Известен целый ряд принципиально различных решений данной задачи:
- Применение общеизвестных генераторов кода по входным грамматикам, среди которых самыми распространенными являются Yacc и Bison. Такой подход может считаться очевидным, тем не менее, он является неприемлемым во многих случаях, поскольку данные генераторы реализуют LALR(1) разбор грамматики, а не SLR(1) разбор. Класс грамматик LALR(1) не может считаться подмножеством класса SLR(1), так же как класс SLR(1) не может считаться подмножеством класса LALR(1).
- Разделение грамматики входного языка на определенное число подграмматик, имеющих меньшие размеры. Для всех подграмматик управляющие таблицы могут быть построены вручную или при помощи имеющихся старых программ на математическом обеспечении ЭВМ. Полученные таблицы следует в ручном режиме перенести в код языка программирования.
- Сформировать набор инструментальных средств, позволяющий создавать управляющие таблицы анализатора для грамматик произвольных размеров. В инструментальных средствах может быть предусмотрена автоматическая генерация кода языка программирования.
При разработке вспомогательных инструментальных средств генерации таблиц следует учитывать следующие требования к создаваемой программе:
- Программа обязана выполнять считывание грамматики из файла и формировать пополненную грамматику, необходимую, для того чтобы реализовать алгоритм. Формат файла с входными данными обязан быть не очень сложным, для того чтобы обеспечить возможность заполнения и редактирования в ручном режиме. В программе лучше использовать достаточно несложный текстовый формат xml, содержащий описание терминалов, не терминалов и порождающих правил грамматики.
- Программа обязана выполнять анализ входной грамматики по определению ее принадлежности классу SLR(1). В случае принадлежности программа обязана сформировать управляющие таблицы разбора, а если такая принадлежность не обнаружена, то выводить диагностические сообщения о невозможности формирования таблицы.
- При успешном формировании таблиц программе необходимо выполнить генерацию их отображения в программном коде компилятора. Сформированные файлы должны быть подключены к программе компиляции и осуществлять управление движком синтаксического анализатора.
Функционирование программы по созданию таблиц разбора состоит в исполнении следующих операций:
- Осуществление проверки корректности входной грамматики. Программа может найти некоторые ошибки входной грамматики, делающие дальнейшую обработку просто бессмысленной.
- Осуществить формирование пополненной грамматики. Тривиальное действие по прибавлению одного не терминала и одного порождающего правила в грамматику.
- Осуществить формирование списка грамматических вхождений (LR-Items). Тривиальное действие, предполагающее нумерацию символов, которые входят в порождающие правила грамматики.
- Формирование функции переходов конечного автомата. В программе необходимо реализовать модифицированный алгоритм, в результате работы которого автомат должен получиться детерминированным.
