Синтаксический анализатор программы

 

Задача синтаксического анализатора (СиА) - провести разбор текста программы, сопоставив его с эталоном, данным в описании языка. Для синтаксического разбора используются контекстно-свободные грамматики (КС-грамматики).

Один из эффективных методов синтаксического анализа – метод рекурсивного спуска. В основе метода рекурсивного спуска лежит левосторонний разбор строки языка. Исходной сентенциальной формой является начальный символ грамматики, а целевой – заданная строка языка. На каждом шаге разбора правило грамматики применяется к самому левому нетерминалу сентенции. Данный процесс соответствует построению дерева разбора цепочки сверху вниз (от корня к листьям).

Пример 2.8. Дана грамматика  с правилами . Требуется выполнить анализ строки cabca^.

Левосторонний вывод цепочки имеет вид:

 

.

 

Нисходящее дерево разбора цепочки представлено на рисунке 2.6.

 

 

 

 

Рисунок 2.6 – Дерево нисходящего разбора цепочки cabca^

 

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

Пример 2.9. Построим синтаксический анализатор методом рекурсивного спуска для грамматики  из примера 2.8.

Введем следующие обозначения:

С H – текущий символ исходной строки;

gc – процедура считывания очередного символа исходной строки в переменную СH;

Err - процедура обработки ошибок, возвращающая по коду соответствующее сообщение об ошибке.

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

 

procedure S;

begin

A; B;

if CH<>¢^¢ then ERR

end;

procedure A;

begin

if CH=¢a¢ then gc

else if CH=¢c¢

then begin

gc; A

end

else Err

end;

procedure B;

begin

if CH= ¢b¢ then

begin

gc; B

end

else Err

end;

⇐ Предыдущая12345678Следующая ⇒

Поделиться: