Теорема Достаточные условия применимости метода рекурсивного спуска
Метод рекурсивного спуска применим к грамматике, если правила вывода грамматики имеют один из следующих видов:
1) A®a, где aÎ(TÈN)*, и это единственное правило вывода для этого нетерминала;
2) A®a1a1 | a2a2|…| anan, где ai ÎT для каждого i=1, 2,…, n; ai¹aj для i¹j, aiÎ(TÈN)*, т.е. если для нетерминала А несколько правил вывода, то они должны начинаться с терминалов, причем эти терминалы должны быть различными.
Данные требования являются достаточными, но не являются необходимыми. Можно применить эквивалентные преобразования КС-грамматик, которые способствуют приведению грамматики к требуемому виду, но не гарантируют его достижения (см. лабораторную работу № 4) /11/.
При описании синтаксиса языков программирования часто встречаются правила, которые задают последовательность однотипных конструкций, отделенных друг от друга каким-либо разделителем. Общий вид таких правил:
L®a | a,L или в сокращенной форме L®a{,a}.
Формально здесь не выполняются условия метода рекурсивного спуска, т.к. две альтернативы начинаются одинаковыми терминальными символами. Но если принять соглашения, что в подобных ситуациях выбирается самая длинная подцепочка, выводимая из нетерминала L, то разбор становится детерминированным, и метод рекурсивного спуска будет применим к данному правилу грамматики. Соответствующая правилу процедура будет иметь вид:
procedure L;
begin
if CH<>’a’ then Err else gc;
while CH=’,’ do
begin
gc;
if CH<>’a’ then Err else gc
end
end;
ПримерПостроим синтаксический анализатор методом рекурсивного спуска для модельного языка М.
Вход – файл лексем в числовом представлении.
Выход – заключение о синтаксической правильности программы или сообщение об имеющихся ошибках.
Введем обозначения:
1) LEX – переменная, содержащая текущую лексему, считанную из файла лексем;
2) gl – процедура считывания очередной лексемы из файла лексем в переменную LEX;
2) EQ(S) – логическая функция, проверяющая, является ли текущая лексема LEX лексемой для S;
3) ID – логическая функция, проверяющая, является ли LEX идентификатором;
7) NUM - логическая функция, проверяющая, является ли LEX числом.
Процедуры, проверяющие выполнение правил, описывающих язык М и составляющие синтаксический анализатор, будут иметь следующий вид:
1)для правила Р® program D1 В.
procedure Р;
begin
if EQ(`program`) then gl else ERR;
D1;
B;
if not EQ(‘.’) then ERR
end;
2) для правила D1® var D{;D}
procedure D1;
begin
if EQ(‘var’) then gl else ERR;
D;
while EQ(‘;’) do
begin
gl; D
end
end;
3) для правила D® I{,I}:(int | bool)
procedure D;
begin
I;
while EQ(‘,’) do
begin
gl; I
end;
if EQ(‘:’) then gl else ERR;
if EQ(‘int’) or EQ(‘bool’) then gl else ERR
end;
4) для правила F® I|N|L|Ø F|(E)
procedure F;
begin
if ID or NUM or EQ(‘true’) or EQ(‘false’) then gl
else
if EQ(‘Ø’)
then begin
gl; F
end
else
if EQ(‘(‘)
then begin
gl; E;
if EQ(‘)’) then gl else ERR
end
else ERR
end;
Аналогично составляются оставшиеся процедуры.
Дата добавления: 2016-03-27; просмотров: 770;