Математические итерационные методы

Слово (символ) - элемент словаря языка.

Предложение- последовательность слов.

Терминальные символы - основные символы языка (буквы, цифры, служебные символы, ключевые слова).

Нетерминальные символы - грамматические категории языка (идентификатор, константа, выражение, инструкция и т.д.).

Синтаксис - совокупность правил и формул, которые задают множество (формально-правильных) предложений.

Грамматический разбор - процесс распознавания предложений и их структуры.

Язык L = L(T, N, P, S) задается: а) словарем Т терминальных символов, б) множеством N нетерминальных символов, в) множеством Р порождающих правил (синтаксисом), г) символом S (из N), называемым начальным символом, порождащим язык L.

1.5.2. Пример задания некоторого языка L1 в БНФ

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

< простое выражение> :: = < буква> ½ < цифра> ½

< простое выражение> +< буква> ½

< простое выражение> -< цифра>

< буква> :: = A ½ B

< цифра> :: = 1 ½ 2 ½ 3

В примере используются следующие символы:

[, ], +, -, A, B, 1, 2, 3 - терминальные символы (словарь Т);

< индексное выражение>, < простое выражение>, < буква>, < цифра> - нетерминальные символы, (заключаются в угловые скобки);

< индексное выражение> - начальный символ.

[A]

Примеры предложений [2]

языка L1: [A-3]

[A+B-1+A-2]

Программа, которая распознает какой-либо язык, строится на основе анализа БНФ. Так как они содержат рекурсивные правила определения конструкций этого языка, то реализация этого правила требует в программе рекурсивной процедуры.

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

Спецификация задачи.

1. Задача. Провести синтаксический контроль конструкции

< индексное выражение>.

2. Входные данные.

лит ch - входной символ

“[” – конечный символ

3. Выходные данные.

í

4. Метод. è

Синтаксические правила (БНФ):

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

< простое выражение> :: = < буква> ½ < цифра>

< простое выражение> +< буква> ½

< простое выражение> -< цифра>

< буква> :: = A ½ B

< цифра> :: = 1 ½ 2 ½ 3

5. Аномалии.

В программе не рассматриваются аномалии, связанные с достижением конца файла в процессе разбора.

Ограничение: при записи индексного выражения нельзя использовать пробелы.

6. Функциональные тесты.

Исходные данные Ожидаемые результаты

[A], [B-2] Ошибок нет

B+A] Нет символа " ["

[A+1], [B-A], [1-A], [f-1] Ошибка в выражении

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

Методика разработки программы

Каждый этап проектирования содержит разбор одного порождающего прави-

ла. Используем Паскаль как язык проектирования.

1 этап. Проектирование главной программы.

Делаем разбор первого правила, упрятывая разбор каждого нетерминального символа в процедуру.

program IndexExpr (f);

var ch: char; f: text; O С1

begin

read(f, ch); O С2.1 O С2.2

if (ch='[') then

begin

{Анализ < простое выражение> } O С3

SimpExpr;

if (ch=']') then Структурная схема программы

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

else Error (1)

end

else Error (2)

end.

2 этап. Разбор второго правила. Раскрытие процедуры SimpExpr .

В этом правиле определение состоит из нерекурсивной и рекурсивной части. Разбор рекурсивной части представим как рекурсивную процедуру Scan, которая сканирует (просматривает) файл f символ за символом, проверяя правильность построения выражения. Раскроем процедуру Scan: С3

.

procedure SimpExpr;

begin

read(f, ch);

{Проверка первого символа}

if ch in [A, B, 1..3] then

Scan;

end

Раскроем процедуру обработки ошибок.

Упражнение.

Каждый из вариантов заданий содержит описание синтаксиса некоторого языка в Бэкус-Науровой Форме (БНФ). Разработать синтаксический анализатор языка, заданного этими синтаксическими правилами.

При решении задачи использовать методику, описанную выше в примере грамматического разбора языка L1.

Анализируемые тексты вводятся посимвольно из текстового файла.

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

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

Варианты заданий

1. < оператор присваивания>:: =< буква>: =< строка>

< строка>:: = ’ < последовательность символов> ’

< последовательность символов>:: =< символ> ½

< последовательность символов> < символ>

2. < арифметический терм>:: =< буква> ½ < цифра> ½

< арифметический терм> * < буква> ½

< арифметический терм> / < цифра>

3. < логическое выражение>:: =< буква> ½ NOT< буква> ½

< логическое выражение> OR< буква>

4. < описание константы>:: =CONST< имя> =< значение> ½

< имя>:: =< буква> ½ < имя> < цифра>

< значение> <:: = -< цифра> ½ < значение> < цифра>

5. < конструктор множества>:: =[< список выражений> ]

< список выражений>:: =< выражение> ½ < список выражений>, < выражение>

< выражение>:: =< буква> ½ < выражение> - < цифра>

6. < интервальный тип>:: =< константа>.. < константа>

< константа>:: =< имя> ½ < число>

< имя>:: =< буква>

< число>:: =< цифра> ½ < число> < цифра>

7. < логический терм>:: =FALSE½ < буква> ½ < логический терм> AND < буква>

8. < указатель функции>:: =< имя> (< выражение> )

< имя>:: =< буква> ½ < имя> < буква> ½ < имя> < цифра>

< выражение>:: =< цифра> ½ < выражение> +< буква>

9. < отношение>:: =< выражение> Ð = < выражение>

< выражение>:: =< имя> ½ < константа>

< имя>:: =< буква>

< константа>:: =< цифра> ½ < константа> < цифра>

10. < вещественное число>:: =< число>.< число> ½ - < число>. < число>

< число>:: =< цифра> ½ < число> < цифра>

11. < логическое выражение>:: =< буква> ½

< логическое выражение> OR< буква> ½

< логическое выражение> OR NOT< буква>

12. < оператор присваивания>:: =< переменная>: = < выражение> ½

< переменная>:: =< имя>

< выражение>:: = ’ < последовательность символ> ’

< имя>:: =< буква> ½ < имя> < буква>

< последовательность символов>:: =< символ> ½

< последовательность символов> < символ>

13. < арифметический терм>:: =< множитель> * < множитель>

< множитель>:: =< имя> ½ < константа>

< имя>:: =< буква> ½ < имя> < цифра>

< константа>:: =< цифра> ½ < константа> < цифра>

14. < блок>:: =BEGIN< оператор> END

< оператор>:: =< оператор процедуры>

< оператор процедуры>:: =< имя> (< список параметров> )

< список параметров>:: =< имя> ½ < список параметров>, < имя>

< имя>:: =< буква>

15. < запись>:: =RECORD< список полей> END

< список полей>:: =< поле> ½ < список полей>; < поле>

< поле>:: =< имя>: < тип>

< тип>:: =< имя>

< имя>:: =< буква> ½ < имя> < буква>

16. < переменная с индексом>:: =< буква> [< список индексов> ]

< список индексов>:: =< индекс>, < индекс>

< индекс>:: =< имя>

< имя>:: =< буква> ½ < имя> < буква>

17. < вещественное число>:: =< целое число> * < натуральное число>

< целое число>:: =< натуральное число> ½ - < натуральное число>

< натуральное число>:: =< цифра> ½ < натуральное число> < цифра>

18. < логическое выражение>:: =TRUE½ < логическое выражение> OR < буква> ½

< логическое выражение> AND< буква>

19. < заголовок>:: =PROCEDURE< имя> (< список параметров> )

< список параметров>:: =< параметр> ½ < список параметров>; < параметр>

< параметр>:: =< имя> : < тип>

< тип>:: =< имя>

< имя>:: =< буква>

20. < отношение>:: =< выражение> = < выражение>

< выражение>:: =< имя> ½ < число>

< имя>:: =< буква>

< число>:: =< цифра> ½ -< цифра> ½ < число> < цифра>

21. < арифметическое выражение>:: =< буква> ½ < цифра> ½ -< цифра> ½

< арифметическое выражение> + < буква> ½

< арифметическое выражение> / < цифра>

22. < интервальный тип>:: =< константа>..< константа>

< константа>:: =< цифра> ½ - < цифра> ½ < константа> < цифра>

23. < описание типа>:: =TYPE< имя> = < тип>

< тип>:: =< имя>

< имя>:: =< буква> ½ < имя> < буква> ½ < имя> < цифра>

24. < вещественное число>:: =< целое число> E< целое число>

< целое число>:: =< цифра> ½ - < цифра> ½ < целое число> < цифра>

25. < указатель функции>:: =< имя> (< выражение> );

< имя>:: =< буква> ½ < имя> < цифра>

< выражение>:: =< цифра> ½ < выражение> - < буква>

26. < литерное выражение>:: =< переменная> ½ < литерное выражение> + < переменная>

< переменная>:: =< имя>

< имя>:: =< буква> ½ < имя> < буква> ½ имя> < цифра>

27. < логический терм>:: =< буква> ½ TRUE½ < логический терм> AND< буква>

1.5.4. Лабораторная работа " Синтаксический анализатор "

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

Рассмотрим методику поэтапного выполнения лабораторной работы.

Методические указания.

Этап 1. Разработка спецификации задачи.

1. Задача. Провести синтаксический контроль конструкции

< описание процедуры>.

2. Входные данные.

лит ch - входной символ

< ch> < ch>...< ch>

файл

3. Выходные данные.

Выходная форма:

æ Ошибок нет

í

è < Реакция на аномалии>

4. Метод. Выбор подмножества L2 языка Паскаль.

1) В синтаксической таблице БНФ выбрать начальный символ языка L2 ( на-

пример, < описание процедуры> ) и порождающее правило:

< описание процедуры> :: = < заголовок>; < блок>.

2) Если порождающее правило громоздкое, то часть логических ветвей можно

отбросить (по указанию преподавателя).

3) Для каждого нетерминального символа из правой части правила

(< заголовок>, < блок> ) записать порождающее правило.

4) Повторять п.3 для каждого нового правила до выполнения следующих ус -ловий:

- порождающее правило в правой части содержит только терминальные

символы языка Паскаль;

- если сложность программы С = m*n > 30, где m - число порождающих правил, а n - общее число логических ветвей в правилах, то в целях ограничения программы использовать заглушки. Например, в рассматриваемой задаче во втором правиле оставляется ветвь «процедура без параметров» (отбрасывается ветвь описа- ния процедуры с параметрами), в третьем правиле при описании символа < блок> оставляем только «составной оператор» (отбрасывается раздел описаний) и < последовательность операторов> заменяется на < последовательность символов>.