На этом этапе можно продолжить проектирование в одном из двух направле-

ний:

* раскрывая абстракцию < Анализ блока> в виде сегмента С3.2 (процедура без параметров Block) соответствии с правилом 3;

* продолжая ветвь Zagolovok, раскрывая абстракцию < Анализ имени процедуры> в виде сегмента С4.1 (процедура без параметров Name ).

Второе направление более естественно с точки зрения построения тестов: после контроля символа procedure провести вначале контроль структуры < имя>, а потом - контроль структуры < блок>.

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

Такой нисходящий подход к проектированию и тестированию программы позволяет остановить процесс разработки проекта «Синтаксический анализатор» на любом этапе, если объем программы превысил допустимую границу.

Полученная программа будет иметь следующую структуру:

O С1

O С2

O С3.1 O С3.2

O С4.1 O С4.2

O С5.1

На рисунке видно, что структура программы грамматического разбора синтаксических правил языка Паскаль отражает структуру этих правил. Как говорят, программа " Синтаксический анализатор " синтаксически зависима от языка: для каждого конкретного языка требуется писать заново программу " Синтаксический анализатор ". Такая зависимость объясняется тем, что входные данные не отражают структуры языка: язык представлен простой последовательностью символов. В таких случаях алгоритм имеет максимальную сложность. Если синтаксисические правила языка отразить в структуре данных, то можно разработать программу " Синтаксический анализатор" управляемую синтаксисом и не зависящую от конкретного языка. В следующей главе рассмотрена возможность отражения структуры правил в структуре данных.

Ниже описаны программа и процедуры в виде отдельных фрагментов как результат последовательных этапов проектирования.

{Синтаксический анализ конструкции < описание процедуры> } С1

program Analiz_Proced (f);

uses crt;

var ch, c, num: char;

filename: string[40];

f: text;

begin {Главная программа}

repeat {Оболочка для тестирования}

{Подготовка файла}

chdir('c: \mam\recurs'); {Установка директории}

writeln(' Введите номер файла');

readln(num);

filename: ='example'+num+'.txt';

assign (f, filename);

reset (f);

clrscr; {Очистка экрана}

{Анализ описания процедуры}

Declare_Proced;

if ch = '; ' then

writeln(' Ошибок нет');

writeln ('Продолжить тестирование? (y/n)');

readln (c);

until Block (c='n') or (c='N')

end.

С2

{< описание процедуры> :: =

< заголовок процедуры> < блок> }

procedure Declare_Proced;

begin

{Анализ заголовка }

Zagolovok;

if ch = '; ' then

{Анализ блока}

Block

end;

С3.1 {< заголовок процедуры> :: = procedure < имя> } procedure Zagolovok; var str10: string[10]; begin read (f, str10); if str10 = 'procedure ' then {Анализ имени процедуры } Name else begin writeln(' Ошибка в слове " procedure" '); ch: =str10[10] end end;

{< блок> :: = begin< последовательность операторов> end} C3.2 procedure Block; var str6: string[6]; str3: string[3]; begin read (f, str6); if str6 = 'begin ' then Posledovat; if ch = ' ' then begin {анализ конца последовательности} read (f, str3); if str3 < > 'end' then writeln(' Нет слова " end" ') else read (f, ch) end else begin writeln(' Ошибка в последовательности операторов '); ch: =str6[6] end end;

{< имя> :: = < буква> ï < имя> < буква> ï < имя> < цифра> } C4.1 procedure Name; {------------------------------------------------------------------------ -------} {контроль рекурсивной части} {< имя> :: = < имя> < буква> ï < имя> < цифра> } procedure Scan; {Рекурсивная процедура} С5.1 begin read(f, ch); {чтение очередного символа} if ch in ['A'.. 'Z', '0'.. '9'] then Scan {продолжить чтение} end {Scan}; {------------------- -----------------------------------------------------------} begin { алгоритм Name } read(f, ch); { чтение первого символа} if ch in ['A'.. 'Z'] then begin {первый символ - буква} Scan; { просмотр текста, пока буква или цифра } if ch < > '; ' then writeln ('Ошибка в имени') end else writeln ('Имя начинается не с буквы') end {Name};

{< последовательность операторов>:: =< любые-символы- C4.2 {Заглушка} кроме-пробела> } procedure Posledovat; {Рекурсивная} begin read (f, ch); if (ch < > ') and not eof(f) then {просмотр последовательности операторов} Posledovat; end;

Варианты лабораторной работы " Синтаксический анализатор "

15. Оператор ДО 16. Оператор ДЛЯ 17. Описание констант 18. Описание типа 19. Описание переменных 20. Описание процедуры 21. Описание функции 22. Оператор выбора 23. Отношение 24. Программа 25. Список формальных параметров 26. Указатель функции 27. Оператор присваивания 28. Интервальный тип

1. Число со знаком 2. Переменная 3. Выражение целое 4. Выражение вещественное 5. Выражение логическое 6. Тип «массив» 7. Тип «файл» 8. Тип «запись» 9. Тип «множество» 10. Блок 11. Оператор процедуры 12. Составной оператор 13. Оператор ЕСЛИ 14. Оператор ПОКА

РЕКУРСИВНЫЙ ТИП ДАННЫХ

2.1. Основные определения

Тип данных является рекурсивным, если его определение содержит одну или несколько компонент того же определяемого типа.

Пример 1 . Простой пример объекта, тип которого можно определить рекурсивно, - это арифметическое выражение. Рекурсия отражает возможность вложенности, т.е. использования заключенных в скобки подвыражений в качестве операндов выражения.

Определим понятие < выражение> в виде следующих синтаксических правил, записанных в форме БНФ:

< выражение> :: = < операнд> < оператор> < операнд>

< операнд> :: = < терм>

< терм> :: = < идентификатор> ½ (< выражение> )

Синтаксические правила содержат косвенную рекурсию: < выражение> определяется через < терм>, а < терм> через < выражение>.

Запишем примеры выражений, порождаемых этими правилами, уточняя понятия < оператор> и < идентификатор> следующим образом:

< оператор> :: = +½ -½ *½ /

< идентификатор> :: = w½ x½ y½ z

Примеры выражений.

1) x+y

2) x*(y-z)

3) (x/(y+z))*w

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

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

Для упрощения процесса кодирования на язык Паскаль перепишем синтаксические правила, пользуясь латинским алфавитом.

< expression>:: =< opd> < op> < opd>

< opd>:: =< term>

< term>:: = < id> ½ (< expression> )

< op> :: = +½ -½ *½ /

< id> :: = w½ x½ y½ z

Теперь эти правила легко преобразуются в описание данных типа «запись» на языке Паскаль:

Тип term представлен записью с вариантами, в которой рекурсивная ветвь соответствует значению переключателя t=false.

TYPE

expression = record

op: operator;

opd1, opd2: term

end;

term = record

case t: Boolean of

true: (id: alfa);

false: (subex: expression)

end;

Характерная особенность рекурсивных структур, которая отличает их от фундаментальных структур (массив, запись, множество) - это способность изменять размер памяти.

⇐ Предыдущая 12