В Навлинском муниципальном районе Брянской области

Варианты контекстных условий

Begin

hta:= THashingTablesArray.Create(3); // Создаем менеджера трех хеш-таблиц.

hta.SetPointTable(2); // Инициализация указателей.

// Каждому слову второй таблицы будет

// сопоставлен указатель на что-нибудь.

hta.AddLexicalUnit(‘Victor’, 2, k); // Заносим слово 'Victor’ во вторую таблицу.

// Слово будет добавлено в таблицу,

// если его там еще нет.

// В k возвращается лексический

// код (ключ) слова.

p:= TPerson.Create;

p.Age:= 20;

p.Weight:= 60;

hta.Pointers[k]:= Pointer(p); // Связываем слово 'Victor’ и объект p.

...

end;

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

2.2.1.Оформить в виде процедуры или функции или метода класса «Лексический анализатор».

2.2.2. Содержание отчета:

а) титульный лист;

б) текст задания, включающий вариант задания;

в) описание алгоритма вычисления места слова в таблице с помощью хеш–функции (если пользуетесь uHashingTablesArray.pas или другой библиотекой, то разобрать используемый там алгоритм);

г) исходный текст процедуры поиска слова в таблице;

в) результаты тестирования.

Лабораторная работа № 3. Разработка контекстно-свободного (КС) синтаксического анализатора (2 часа)

3.1.Задание

Для предложенного преподавателем варианта КС-грамматики разработать методом рекурсивного спуска синтаксический анализатор.

Примечание. Здесь и далее через <1> и <2> обозначены слова из лабораторной работы №1.

Внимание. Символы <, > частью слов не являются.

3.2. Варианты грамматик

Определение варианта:

5-ая группа: Номер в группе.

6-ая группа: (Номер в группе + 16) mod 27 + 1.

7-ая группа: 28 - Номер в группе.

№

Грамматика

№

Грамматика

№

Грамматика

S ® S S + S ® A A ® S S * A ® B B ® <2> | <1>

S ® A | B A ® A B + | B B ® B C * | C C ® C - | <1> | <2>

O ® A = A | (L) A ® <1> | <2> L ® true| false | U | not L | O U ® <2>

П ® П, O | O O ® <2> = <1> <1> O ® <2> = (O)

C ® B | P B ® [ P P ] | <1> P ® (B B) | <2>

М ® М + П | П П ® П * А | А А ® [ ] А ® [ S ] S ® <1>, S | <2>, S | <1> | <2> | [ A ]

П ® П; К | K К ® О R, A O ® <2> R ® <1> A ® <1> | <2>

D ® D Ú K | K K ® K Ù A | A A ® Ø A | (D) | O O ® <1> = <2> | <2> = <1> | <2> = <2>

S ® A | B A ® <1> | ((A) [ B ]) B ® <2> | [ [ B ] (A) ]

S ® <2> S A S ® A A ® (S) A ® () A ® <1>

S ® S; P | P P ® A = A A ® A + M | M M ® M * T | T T ® <1> | <2> | (A)

S ® (D!: S! S) S ® <1> D ® D Ú K | K K ® K Ù A | A A ® <2> | Ø A | (D)

S ® <1> A S S ® <2> A ® <1> A ® <2> S A

S ® B A A ® + B A | B B ® D C C ® * D C | D D ® (S) | <1> | <2>

S ® <2> A <2> B S ® <1> A <1> B A ® <2> | <2> <1> B ® <2> B B ® <2>

S ® A: B. A ® <2> B ® B; C B ® C C ® C, D C ® D D ® <1> D ® <2>

S ® A; S S ® A A ® A, B A ® B B ® <1> B ® <2>: <1>

S ® (A!: B! B) S ® (A!: B) A ® <2> B ® <1> B ® S

S ® + S S S ® A A ® * S S A ® B B ® <2> [ <1> ]

S ® S + A S ® A A ® A * B A ® B B ® <2> (<1>)

S ® S; A S ® A A ® <2>:= [ B ] B ® <1>, B B ® <1>

S ® (A) A ® (<2> B) A ® <1> B ® (C) C ® C, <1> C ® <1>

S ® A:- B. A ® <2> (<1>) B ® B, A B ® A

S ® <2> A <1> B A ® [ A ] A ® <1> B ® B <2> B ® <2>

S ® S A S ® B B A ® <2> A A A ® <1> B ® <2>

S­­ ® <2> (А):- B. A ® <1>, A A ® <1> B ® B, <2> B ® <2>

S ® [ S ] | A A ® [ <2> B ] B ® [ C ] C ® C, <1> | <1>

Внимание. Для лучшего рассмотрения содержащихся в грамматике символов рекомендуется изучить свой вариант задания в увеличенном масштабе.

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

3.3.1. Рекомендации

1. Лексический анализатор из лабораторной работы №1 должен быть расширен обработкой появившихся в КС-грамматике новых слов и включен в виде подпрограммы или поля класса или метода класса в синтаксический анализатор.

2. Оформить синтаксический анализатор в виде процедуры или функции или класса, которые при обращении обрабатывают весь исходный текст.

3. Если грамматика леворекурсивная, то устранить левую рекурсию.

3.3.2. Содержание отчета:

а) титульный лист;

б) текст задания, включающий вариант задания;

в) преобразование КС – грамматики по исключению левой рекурсии;

г) исходный текст синтаксического анализатора;

д) результаты тестирования.

Лабораторная работа № 4. Построение синтаксического дерева (2 часа)

4.1. Задание

Включить в синтаксический анализатор из лабораторной работы №.3 построение синтаксического дерева. Использовать атрибутный метод Кнута, т.е. преобразовать КС – грамматику из лабораторной работы № 3 в атрибутную грамматику добавлением атрибутов и правил построения синтаксического дерева. Расширить программу синтаксического анализатора из лабораторной работы № 3 введением действий по построению синтаксического дерева.

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

4.2.1. Содержание отчета:

а) титульный лист;

б) текст задания, включающий вариант задания;

в) атрибутная грамматика с действиями по построению синтаксического дерева;

г) исходный текст синтаксического анализатора;

д) результаты тестирования (должны содержать отладочный вывод синтаксического дерева на экран).

Лабораторная работа № 5. Разработка контекстного анализатора (2 часа)

5.1. Задание

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

Определение варианта: такой же, как в л.р. № 3.

	Все идентификаторы должны быть разными		Все числа должны быть разными		Все идентификаторы должны быть разными
	Все числа должны быть разными		Все идентификаторы должны быть разными		Все числа должны быть разными
	Все числа должны быть разными		Все идентификаторы должны быть разными		Все числа должны быть разными
	Все числа должны быть разными		Все числа должны быть разными		Все идентификаторы должны быть разными
	Все идентификаторы должны быть разными		Внутри скобок все идентификаторы должны быть разными		Все идентификаторы должны быть разными
	Все числа должны быть разными		Все идентификаторы должны быть разными		Все идентификаторы должны быть разными
	Все идентификаторы должны быть разными		Все идентификаторы должны быть разными		Все числа должны быть разными
	Все числа должны быть разными		Все числа должны быть разными		Все идентификаторы должны быть разными
	Все числа должны быть разными		Все идентификаторы должны быть разными		Все числа должны быть разными

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

5.3.1. Содержание отчета:

а) титульный лист;

б) текст задания, включающий вариант задания;

в) атрибутная грамматика с атрибутами и действиями по вычислению контекстных условий;

б) исходный текст синтаксического анализатора;

в) результаты тестирования.

Лабораторная работа № 6. Разработка генератора (2 часа)

6.1. Задание

По результатам анализа исходного текста получить выходной текст в виде:

1. Все числа исходного текста должны быть переведены в десятичное представление.

2. Выполнить вывод полученного текста в структурированном виде с помощью отступов («ступеньками»).

Примечание. Генератор должен осуществлять отдельный просмотр текста (синтаксического дерева). Правила структурирования текста разработать самостоятельно.

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

6.2.1. Содержание отчета:

а) титульный лист;

б) текст задания, включающий вариант задания;

в) атрибутная грамматика с атрибутами и действиями по преобразованию исходного текста в выходной;

г) исходный текст генератора;

д) результаты тестирования.

--------------------------------------------------------------------------------------------------------------------------------------------

Лабораторная работа № 7. Разработка интерпретатора формул

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

Определение варианта: выбрать из приведенных ниже или предложить свой, согласовать с преподавателем.

1. Интерпретатор арифметических функций.

<Арифметическая функция>::= АрФункция <Имя> [(<Список параметров>)] = <АрВыражение>.

Арифметическое выражение состоит из:

- имен параметров, указанных в <Список параметров>;

- целых и вещественных констант;

- ранее определенных арифметических функций;

- символов арифметических операций (+, -, /, mod, div) и круглых скобок.

Можно ввести составные типы данных.

Пример:

АрФункция ПромежутокВремениВЧасах(В1: время, В2: время) = (В2.Часов - В1.Часов) + (В2.Минут - В1.Минут) / 60.

Интерпретатор выдает значение функции (целое или вещественное число) для конкретных параметров.

2. Интерпретатор логических функций.

<Логическая функция>::= ЛогФункция <Имя> [(<Список параметров>)] = <ЛогВыражение>.

В логических выражениях участвуют:

- имена параметров, указанных в <Список параметров>;

- целые и вещественные константы;

- ранее определенные логические функции;

- символы логических операций (Ø, &, Ú, Þ, Û, <, £, ¹, ³, >) и круглые скобки.

Можно ввести составные типы данных.

Пример:

ВремяБольше(В1: время, В2: время) = (В1.Часов > B2.Часов) Ú ((В1.Часов = B2.Часов) & (B1.Минут > B2.Минут)).

Интерпретатор выдает значение функции (True или False) для конкретных параметров.

3. Простой табличный процессор.

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

Арифметические выражения состоит из:

- ссылок на ячейки;

- целых и вещественных констант;

- символов арифметических операций (+, -, /, mod, div) и круглых скобок.

Интерпретатор по цепочке означивает ячейки таблицы.

4. Проверятель ограничений.

Имеется таблица, в ячейках которой содержатся целые и вещественные константы.

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

<Ограничение>::= Ограничение <Ячейка> <Операция сравнения> <АрВыражение>.

<Ячейка>::= <Строка>. <Столбец>.

<Операция сравнения>::= < | £ | ¹ | ³ | >.

Арифметические выражения состоят из:

- ссылок на ячейки;

- целых и вещественных констант;

- символов арифметических операций (+, -, /, mod, div) и круглых скобок.

Интерпретатор выполняет проверку ограничений.

7.2. План работы

1. Конкретизировать вариант задания, сформулировать точную постановку задачи.

2. Аналогично лаб. работе № 1:

2.1. Составить регулярную грамматику для каждого вида используемых слов и комментария. Шаблон комментария разработать самостоятельно.

2.2. По каждой грамматике построить конечный автомат.

2.3. Преобразовать полученные конечные автоматы в детерминированные конечные автоматы.

2.4. Составить объединенный алгоритм лексического анализатора.

2.5. Написать и отладить программу по алгоритму. Предусмотреть транслитератор и обработчик ошибок в качестве отдельных подпрограмм. Оформить лексический анализатор в виде процедуры или функции или класса. За одно обращение обрабатывает одно очередное слово. Управление потоком слов осуществляется отдельно. При отладке программы обратить внимание на обработку правильного текста, обработку ошибочного текста, обработку конца исходного текста.

3. Аналогично лаб. работе № 2:

3.1. Ввести табличный способ хранения слов. Оформить в виде процедуры или функции или метода класса «Лексический анализатор».

4. Аналогично лаб. работе № 3:

4.1. Разработать КС-грамматику, соответствующую задаче.

4.2. Если грамматика леворекурсивная, то устранить левую рекурсию.

4.3. Разработать методом рекурсивного спуска синтаксический анализатор. Лексический анализатор должен быть включен в виде подпрограммы или поля класса или метода класса в синтаксический анализатор. Оформить синтаксический анализатор в виде процедуры или функции или класса, которые при обращении обрабатывают весь исходный текст.

5. Аналогично лаб. работе № 4:

5.1. Включить в синтаксический анализатор построение синтаксического дерева. Использовать атрибутный метод Кнута, т.е. преобразовать КС–грамматику в атрибутную грамматику добавлением атрибутов и правил построения синтаксического дерева. Расширить программу синтаксического анализатора введением действий по построению синтаксического дерева.

6. Аналогично лаб. работе № 5:

6.1. Расширить атрибутную грамматику добавлением атрибутов, правил их вычисления, правил вычисления контекстных условий (исходя из своей задачи). Включить в программу синтаксического анализатора действия по вычислению атрибутов и проверки контекстных условий.

7. Аналогично лаб. работе № 6:

7.1. По результатам анализа исходного текста сгенерировать вычислительную модель (обратная польская запись). Генератор должен осуществлять отдельный просмотр синтаксического дерева.

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

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

Обратить внимание на обработку ошибок.

Содержание отчета:

1. Титульный лист.

2. Постановка задачи.

3. Для одного из видов слов:

3.1. Описание регулярной грамматики.

3.2. Описание недетерминированного конечного автомата (в виде диаграммы и матрицы).

3.3. Описание детерминированного конечного автомата (в виде матрицы и диаграммы).

4. Описание объединенного алгоритма лексического анализатора.

5. Описание алгоритма вычисления места слова в таблице с помощью хеш–функции (если пользуетесь uHashingTablesArray.pas или другой библиотекой, то разобрать используемый там алгоритм).

6. Преобразование КС–грамматики по исключению левой рекурсии.

7. Атрибутная грамматика с атрибутами и действиями по построению синтаксического дерева.

8. Атрибутная грамматика с атрибутами и действиями по вычислению контекстных условий.

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

10. Исходный текст программы.

11. Результаты тестирования.

Дата добавления: 2015-06-04