Ишакова Е.Н. Разработка компиляторов - Методические указания к курсовой работе (1082246), страница 3

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

2) по ДС с действиями написать программу сканирования текста исходной программы.

Пример 2.7. Составим ЛА для модельного языка М. Предварительно введем следующие обозначения для переменных, процедур и функций.

Переменные:

1) СН – очередной входной символ;

2) S - буфер для накапливания символов лексемы;

3) B – переменная для формирования числового значения константы;

4) CS - текущее состояние буфера накопления лексем с возможными значениями: Н - начало, I - идентификатор, N - число, С - комментарий, DV – двоеточие, О - ограничитель, V - выход, ER –ошибка;

1. t - таблица лексем анализируемой программы с возможными значениями: TW - таблица служебных слов М-языка, TL – таблица ограничителей М-языка, TI - таблица идентификаторов программы, TN – чисел, используемых в программе;

6) z - номер лексемы в таблице t (если лексемы в таблице нет, то z=0).

Процедуры и функции:

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

2) let – логическая функция, проверяющая, является ли переменная СН буквой;

3) digit - логическая функция, проверяющая, является ли переменная СН цифрой;

4) nill – процедура очистки буфера S;

5) add – процедура добавления очередного символа в конец буфера S;

6) look(t) – процедура поиска лексемы из буфера S в таблице t с возвращением номера лексемы в таблице;

7) put(t) – процедура записи лексемы из буфера S в таблицу t, если там не было этой лексемы, возвращает номер данной лексемы в таблице;

8) out(n, k) – процедура записи пары чисел (n, k) в файл лексем.

Шаг 1. Построим ДС с действиями для распознавания и формирования внутреннего представления лексем модельного языка М (рисунок 2.5).

gc, out(2, z)

Рисунок 2.5 – Диаграмма состояний с действиями для модельного языка М

Шаг 2. Составляем функцию scanner для анализа текста исходной программы:

function scanner: boolean;

var CS: (H, I, N, C, DV, O, V, ER);

begin gc; CS:=H;

repeat

case CS of

H: if CH=’ ‘ then gc

else

if let then

begin

nill; add;

gc; CS:= I

end

else

if digit then

begin

B:=ord(CH)-ord(‘0’);

gc; CS:= N

end

else

if CH= ‘:’ then

begin

gc;

CS:= DV

end

else

if CH=’.’ then

begin

out(2,1);

CS:=V

end

else

if CH=’{‘ then

begin

gc; CS:=C

end

else CS:=O;

I: if let or digit then

begin

add; gc

end

else begin

look(TW);

if z<>0 then

begin

out(1,z); CS:=H

end

else begin

put(TI);

out(4,z);

CS:=H

end

end;

N: if digit then

begin

B:=10*B+ord(CH)-ord(‘0’);

gc

end

else begin

put(TN);

out(3,z); CS:=H

end;

C: if CH=’}’ then begin

gc; CS:=H

end

else if CH=’.’ then CS:=ER else gc;

DV: if CH=’=’ then begin

gc; out(2,5);

CS:=H

end

else begin

out(2,4); CS:=H

end;

O: begin

null; add; look(TL);

if z<>0 then begin

gc; out(2,z);

CS:=H

end

else CS:=ER

end

end {case}

until (CS=V) or (CS=ER);

scanner:= CS=V

end;

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

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

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

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

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

.

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

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

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

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

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

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

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

3. 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;

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

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

1) A, где (TN)^*, и это единственное правило вывода для этого нетерминала;

2) Aa₁₁ | a₂₂ |…| a_n_n, где a_i T для каждого i=1, 2,…, n; a_ia_j для ij, _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

end

end;

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

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

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

Введем обозначения:

1) LEX – переменная, содержащая текущую лексему, считанную из файла лексем;

2) gl – процедура считывания очередной лексемы из файла лексем в переменную LEX;

2) EQ(S) – логическая функция, проверяющая, является ли текущая лексема LEX лексемой для S;

3) ID – логическая функция, проверяющая, является ли LEX идентификатором;

1. 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

Характеристики

Список файлов книги