Теорема Достаточные условия применимости метода рекурсивного спуска

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

1) A®a, где aÎ(TÈN)^*, и это единственное правило вывода для этого нетерминала;

2) A®a₁a₁ | a₂a₂|…| a_na_n, где a_i ÎT для каждого i=1, 2,…, n; a_i¹a_j для i¹j, a_iÎ(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 идентификатором;

4) 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;

Аналогично составляются оставшиеся процедуры.

14.Синтаксический анализатор. Основные принципы построения.

15.О семантическом анализе

В ходе семантического анализа проверяются отдельные правила записи исходных программ, которые не описываются КС-грамматикой. Эти правила носят контекстно-зависимый характер, их называют семантическими соглашениями или контекстными условиями.

16.Семантический анализатор. Основные принципы построения.

Рассмотрим пример построения семантического анализатора (СеА) для программы на модельном языке М. Соблюдение контекстных условий для языка М предполагает три типа проверок:

1) обработка описаний;

2) анализ выражений;

3) проверка правильности операторов.

В оптимизированном варианте СиА и СеА совмещены и осуществляются параллельно. Поэтому процедуры СеА будем внедрять в ранее разработанные процедуры СиА.

Вход: файл лексем в числовом представлении.

Выход: заключение о семантической правильности программы или о типе обнаруженной семантической ошибки.