Построение синтаксического анализатора методом рекурсивного спуска с использованием МП-автомата

Введение

Одним из простейших способов построения синтаксического анализа по LL(1)-грамматике является метод рекурсивного спуска. Этот метод реализуется на любом императивном языке программирования, в котором есть возможность рекурсивного вызова функций или процедур. Недостатком метода является смешение алгоритма и правил грамматики в коде получаемого анализатора, что ведет к снижению читаемости и мобильности исходного кода и, как следствие, к ошибкам при разработке. Предлагаемый способ позволит формализовать процесс программирования синтаксического анализатора благодаря использованию абстракции МП-автомата.

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

Использование приведенного в статье метода позволит получать доказуемо правильный код программы.

Объекты и методы исследования

Различные методы синтаксического анализа с использованием формальных грамматик широко используются для разработки компиляторов [1, с. 35]. Кроме того, часть этих методов можно применять для проверки корректности:

• вводимой информации,
• передаваемых данных,
• интерфейсных программных взаимодействий.

Формализация правил проверок в форме контекстно-свободной грамматики LL(1) [2, с. 96] позволяет реализовать синтаксический анализатор (распознаватель, парсер) на любом алгоритмическом языке высокого уровня, используя метод рекурсивного спуска [1, с. 120].

Кроме того, известно соответствие LL(1)-грамматики и МП-автомата [2, с. 79]. Совмещение обоих подходов, как будет показано ниже, позволяет формализовать, а при необходимости автоматизировать разработку программ, реализующих метод рекурсивного спуска.

Удобство LL(1)-грамматик выражено в том, что для выбора применяемого правила достаточно иметь информацию об одном входном символе. Конечно, это накладывает дополнительные требования к формированию правил грамматики [1, с. 115], но в случаях простых синтаксических разборов ограничения несущественны.

Для примера составим правила LL(1)-грамматики для упрощенного варианта SQL-запроса «select»:

«select столбец1, столбец2, … from таблица1, таблица2, …»

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

• вместо токена «select» будем использовать символ «s»,
• вместо токена «from» будем использовать символ «f»,
• вместо названий полей символы «a» или «b»,
• «$» будет обозначать конец строки.

С учетом указанных замен распознаваемая в примерах строка будет иметь форму: «s a,b,a,a f a,a,a,b,b,b,a$».

LL(1)-грамматика, по которой будем строить синтаксический анализатор, получается следующей:

1. S → sXfX
2. X → AY
3. Y → ,AY
4. Y → ɛ
5. A → a
6. A → b

В приведенных выше правилах заглавными буквами указаны нетерминальные символы, маленькими буквами – терминальные, то есть составляющие входную строку. «Ɛ» – пустой символ, и правило 4, соответственно, аннулирующее.

Выстраиваемый далее МП-автомат, эквивалентный LL(1)-грамматике, состоит из следующих элементов:

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

Входные символы: символы из входной строки, то есть терминальные, с точки зрения МП-автомата записаны на входную ленту.

Магазинные символы: все нетерминальные символы грамматики и терминальные символы, которые могут находиться не на первом месте в правой части правил грамматики.

Состояния:

• рабочее состояние,
• состояние «синтаксическая ошибка»,
• состояние «успешное завершение».

Переход в состояние «синтаксическая ошибка» производится, если входная цепочка символов не соответствует правилам грамматики, по которым построен МП-автомат.

Возможные в рабочем состоянии действия со стеком и с входной лентой приведены в таблице.

Таблица

Действия МП-автомата в рабочем состоянии

Действие	Обозначение
Вытолкнуть из стека символ
Заменить символ в стеке цепочкой символов
Сдвиг вправо по входной ленте
Не двигать входную ленту (стоять на месте)
Переход в состояние «синтаксическая ошибка»	-
Переход в состояние «успешное завершение»	+

В состояниях «синтаксическая ошибка» и «успешное завершение» автомат не выполняет никаких действий вне зависимости от входной ленты и состояния стека. Эти состояния сигнализируют о результате синтаксического анализа. Результаты работы МП-автомата выражены именно состояниями, а не выходными сигналами, чтобы не нарушать классическую модель МП-автомата, не подразумевающую выходных сигналов.

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

Пример функции переходов, заданной в табличной форме, приведен на рис. 1.

Рис. 1. Таблица переходов

По таблице переходов можно проследить сразу все составляющие МП-автомата: магазинные и входные символы, действия с магазином и переходы между состояниями.

Построение МП-автомата по LL(1)-грамматике в целом соответствует устоявшейся практике [3, c. 44], но приведем это построение в разрезе построения таблицы переходов для удобства дальнейшей разработки программы, реализующей метод рекурсивного спуска.

Для построения МП-автомата выделим четыре вида правил LL(1)-грамматик:

1. Правила LL(1)-грамматики, в которых левая часть начинается с терминального символа;
2. Правила LL(1)-грамматики, в которых левая часть начинается с нетерминального символа;
3. Правила LL(1)-грамматики, в которых левая часть содержит один терминальный символ;
4. Аннулирующее правило LL(1)-грамматики.

Правила первого вида имеют форму:

A → xB

В формуле использованы следующие обозначения:

A – одиночный нетерминальный символ,

x – одиночный терминальный символ,

B – цепочка любых символов.

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

Рис. 2

Правила второго вида имеют форму:

A → СB

В формуле использованы следующие обозначения:

A – одиночный нетерминальный символ,

С – одиночный нетерминальный символ,

B – цепочка любых символов.

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

Рис. 3

На рис. 3 x принадлежит множеству первых символов сверток, полученных из С.

Правила третьего вида имеют форму:

A → x

В формуле использованы следующие обозначения:

A – одиночный нетерминальный символ,

x – одиночный терминальный символ.

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

Рис. 4

Правила четвертого вида (аннулирующие) имеют форму:

A → ɛ

В формуле использованы следующие обозначения:

A – одиночный нетерминальный символ,

ɛ – пустой символ.

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

Рис. 5

При этом x принадлежит множеству первых символов следующих за A в cвертках рассматриваемой грамматики.

Кроме действий (ячеек таблицы переходов), непосредственно составленных в соответствии с правилами грамматики, необходимо МА-автомат дополнить следующими действиями.

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

Рис. 6

Для ячейки таблицы переходов, соответствующей концу входной ленты и символу конца магазина, указывается действие – переход в состояние «успешное завершение» согласно рис. 7.

Рис. 7

Для остальных незаполненных ячеек указывается переход в состояние «синтаксическая ошибка».

Для начала синтаксического разбора в магазин должен быть загружен начальный нетерминальный символ, МП-автомат находится в состоянии «рабочее состояние».

Для примера с грамматикой SQL-запроса «select» МП-автомат будет выглядеть как показано на рис. 8.

Рис. 8

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

Основные правила построения программы, реализующей метод рекурсивного спуска:

• каждому магазинному символу должна соответствовать функция в языке программирования;
• очередной входной символ должен быть доступен глобально для всех функций;
• сдвиг по входной ленте реализуется через вызов функции получения следующего символа или вызов лексического анализатора для получения очередной лексемы/токена;
• повторяя принцип синтаксического разбора с помощью МП-автомата, в начале программы необходимо вызвать функцию, реализующую начальный нетерминальный символ, а по завершению этой функции (что соответствует пустому магазину) проверить достижение конца входной строки;
• выталкиванию символа из стека соответствует завершение функции, а помещению символа в стек – вызов функции, что сочетается с принципом помещения в стек записей активации функций в ряде языков программирования, например, в Си.

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

В примере с SQL-запросом одним из магазинных символов является «Y». Код функции, реализующей этот магазинный нетерминальный символ, определяется столбцом «Y» таблицы переходов на рис. 8.

Тело соответствующей функции для Си-подобных языков должно выглядеть следующим образом:

switch( x ) {
          case 'f': yylex(); break;
          default: stateerr(); break;
}

Здесь yylex() – функция получения следующего входного символа, с точки зрения МП-автомата – сдвиг по входной ленте. Выталкивание символа из стека – видно, что никакая больше функция не вызывается, значит выполнение функции завершится. Если входной символ отличен от «f», выполнятся действия по конструкции «default» – выполнится функция, соответствующая переходу в состояние «синтаксическая ошибка».

Функции, определяющие нетерминальные магазинные символы, строятся по следующим правилам:

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

В примере с SQL-запросом в стек помещается терминальный символ «f». Код функции определяется столбцом «f» таблицы переходов на рис. 8.

Тело соответствующей функции для Си-подобных языков должно выглядеть следующим образом:

         switch( x ) {
                   case 'f': break;
                   case '$': break;
                   case ',': yylex(); A(); Y(); break;
                   default: stateerr(); break;
}

В этом коде, как и в таблице переходов МП-автомата, для входных символов «f» и «$» (конец строки/ленты) лента стоит на месте (не вызывается функция получения очередного входного символа «yylex()»), выталкивается нетерминальный символ «Y» из стека (функция завершается). А при входном символе «,» (запятая) производится сдвиг по ленте (вызов функции получения очередного входного символа), текущий символ магазина «Y» заменяется на «А» и «Y» (вызов функций «А()», «Y()» и последующее завершение текущей функции «Y()»). Если входной символ отличен от {«f»,«$»,','}, выполнятся действия по конструкции «default» – выполнится функция, соответствующая переходу в состояние «синтаксическая ошибка».

Результаты и их обсуждение

Программа для разбора строки "sa,b,a,afa,a,a,b,b,b,a$" реализована на JavaScript и выполняется в современных веб-браузерах. Особенностями программы являются:

• входная строка записана в виде массива символов;
• неуспешное завершение синтаксического анализа отрабатывается функцией stateerr(), генерирующей исключительную ситуацию (для прекращения рекурсивного вызова функций и выхода из всех рекурсий), обрабатываемую конструкцией «try-catch»;
• информация об результатах анализа («+» или «-») отображается на веб-странице.

Полная версия программы будет выглядеть следующим образом.

<body>
<script>
var input = "sa,b,a,afa,a,a,b,b,b,a$";
var pos = 0;
var x = '';

yylex = () =>
{
         x = input[pos];
         pos++;
}

stateok = () => {
         document.write('+');
}

stateerr = () => {
         throw "-";
}

main = () => {
         yylex();
         S();
         switch( x ) {
                   case '$': stateok(); break;
                   default: stateerr(); break;
         }
}

S = () => {
switch( x ) {
                   case 's': yylex(); X(); f(); X(); break;
                   default: stateerr(); break;
         }
}

X = () => {
         switch( x ) {
                   case 'a': A(); Y(); break;
                   case 'b': A(); Y(); break;
                   default: stateerr(); break;
         }
}

A = () => {
         switch( x ) {
                   case 'a': yylex(); break;
                   case 'b': yylex(); break;
                   default: stateerr(); break;
         }
}

Y = () => {
         switch( x ) {
                   case 'f': break;
                   case '$': break;
                   case ',': yylex(); A(); Y(); break;
                   default: stateerr(); break;
         }
}

f = () => {
         switch( x ) {
                   case 'f': yylex(); break;
                   default: stateerr(); break;
         }
}

try {
         main();
}
catch (e)
{
         document.write('-');
}
</script>

Заключение

Приведенный метод позволяет за считанные минуты составить доказуемо правильную программу. Естественно при этом должна быть предварительно составлена формальная грамматика LL(1).

В рассмотренном примере вместо лексем (токенов) используются непосредственно входные символы. Но метод без какой бы то ни было модификации позволяет полученному синтаксическому анализатору работать в паре с лексическим анализатором. Потребуется только заменить символы, заданные константами в конструкции «case», на токены/лексемы (например, использовав макроопределения с помощью #define) и переопределить функцию получения очередного символа «yylex()», название которой выбрано неслучайно (именно так называет функцию генератор лексического анализатора «lex»).

Благодарности

Выражаю благодарность учителю и руководителю Соловьеву А.Е., который говорит, что переход от неформального к формальному неформален; студентам ПНИПУ, в свое время согласившимся участвовать в безуспешном (с точки зрения студентов) и успешном (с точки зрения автора) эксперименте по построению синтаксического анализатора специально без использования рассмотренного (да и вообще, какого бы то ни было) метода; жене, если в статье нет описок.