otchet


МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИИ
Троицкий филиал федерального государственного бюджетного
образовательного учреждения высшего профессионального образования
“Челябинский государственный университет”
Кафедра математики и информатики
ОТЧЁТ ПО ВЫЧИСЛИТЕЛЬНОЙ ПРАКТИКЕ
Выполнил: Терновский А.С
Группа: ТПМ-101
Дата: 12.07.2011
Проверила: ст.преп. Булатова М.Г.
Троицк
2011г.
Содержание:
Спецификация 3
Проектирование
Кодирование

3.1. Блок транслитерации
3.2. Лексический блок
3.3. Синтаксический блок
5
9

9
9
14
Тестирование
Заключение
Литература 15
15
15
Спецификация
Разработка:
Необходимо разработать распознаватель заданной символьной цепочки. Символьная цепочка задается с помощью формул Бэкуса-Наура.
<условный оператор>::=<оператор if-then>|<оператор if-then-else>;
<оператор if-then>::=IF <условие> THEN <оператор1> ELSE<>;
<оператор if-then>::=IF <условие> THEN <оператор1> ELSE<оператор2>;
<оператор1>::=<оператор присваивания>;
<оператор присваивания>::=<идентификатор>::=<выражение>;
<идентификатор>::=<буква>|<идентификатор><буква>|;
<буква>::=A|..|Z;
<выражение>::=<вызов подпрограммы>;
<вызов подпрограммы>::=<идентификатор>(<список параметров>);
<список параметров>::=<идентификатор>;
<оператор2>::=<вызов подпрограммы>;
<список параметров>::=<целая константа>;
<целая константа>::=<целое со знаком>|<целое без знака>;
<целое со знаком>::=<знак><целое без знака>;
<знак>::=+|-;<целое без знака>::=<цифра>|<цифра><целое без знака>;
<цифра>::=0|..|9;
Помимо этого на цепочку накладывается следующее семантическое ограничение: идентификатор, входящий в цепочку, не должен совпадать с ключевыми словами языка Pascal.
Описание входных данных:
Цепочка записана в текстовом файле INPUT.TXT, который состоит из одной строки. Длина цепочки не превышает 80 символов.
Описание выходных данных:
Результат распознавания необходимо записать в текстовый файл OUTPUT.TXT в одно из следующих сообщений: ACCEPT, если цепочка допустима, и REJECT, если цепочка недопустима.
Примеры входных и выходных данных:
INPUT.TXT OUTPUT.TXT
IF b THEN x(f1, f2, f3) ELSE d(e1, e2, e3); ACCEPT
IF TRUE THEN a(b3) ELSE a(c7); IF b THEN x(f1, f2, f3) ELSE d(e1, e2, e3) REJECT
FOR r THEN x(f1, f2, f3) ELSE d(e1, e2); IF b THEN TRUE ELSE x(d6); IF 5 THEN v(t1,f2) ELSE m(u2,f1); Проектирование
На этапе проектирования необходимо выполнить проектирование модульной структуры программы и разработать набор тестов и соответствующие тестовые программы для проведения тестирования. Важной особенностью этапа проектирования является то, что все работы на данном этапе выполняются без использования системы программирования.
Проектирование модульной структуры
Модульная структура представляет собой иерархию процедур и функций (называемых модулями), с помощью которых программа решает поставленную задачу. При этом программа является головным модулем в данной иерархии. Иерархия модулей отражает межмодульные связи по управлению, а не
по времени. Это означает, что модульная структура отражает только тот факт, что модуль более высокого уровня иерархии вызывает все непосредственно связанные с ним модули более низкого уровня иерархии, не показывая при этом порядок вызова связанных модулей более низкого уровня иерархии.
• Блок транслитерации – подпрограмма, преобразующая исходную символьную цепочку в цепочку лексем вида ("символ цепочки", "класс символа цепочки ").
• Лексический блок – подпрограмма, преобразующая цепочку лексем, полученную от транслитератора, в цепочку лексем вида ("символ входного языка", "класс символа входного языка").
• Блок идентификации ключевых слов – подпрограмма, которая устанавливает, какое из ключевых слов языка Pascal соответствует заданному идентификатору либо сообщает, что заданный идентификатор не является ключевым словом языка Pascal. Идентификация ключевых слов может быть выделена в отдельный проход распознавателя символьной цепочки,
то есть идентифицирующий блок будет запускаться после того, как лексический блок полностью подготовит всю цепочку лексем. Другим подходом является объединение в один проход распознавателя символьной цепочки лексического блока и блока идентификации. В этом случае идентификация ключевого слова осуществляется каждый раз, когда лексический
блок выдал одну лексему класса "идентификатор" (без ожидания полной подготовки всей цепочки лексем).
• Синтаксический блок – подпрограмма, которая получает цепочку лексем вида ("символ входного языка", "класс символа входного языка") и устанавливает, соответствует ли она заданным формулам Бэкуса–Наура. Поскольку задание предполагает только распознавание исходной цепочки, фактически данный блок использует для работы только классы символов входного языка.
Пример набора тестов для модулей распознавания цепочки:
Модуль Тесты
Входные данные Выходные данные
Блок транслитерации IF b THEN x(f1, f2, f3) ELSE d(e1, e2); (I,буква)
(f, буква)
( ,пробел)
(b, буква)
( ,пробел)
(t, буква)
(h, буква)
(e, буква)
(n, буква)
( ,пробел)
(x, буква)
((, скобка)(f, буква)
(1, цифра)
(,, запятая)
(f, буква)
(2, цифра)
(,, запятая)
(f, буква)
(3, цифра)
(),скобка)
(, пробел)
(e, буква)
(l, буква)
(s, буква)
(e, буква)
(, пробел)
(d, буква)
((, скобка)(с, буква)
(1, цифра)
(,, запятая)
(с, буква)
(2, буква)
(), скобка)
(;,тчкзпт)
Лексический блок (I, сим буква)
(f, сим буква)
( , сим пробел)
(b, сим буква)
( , сим пробел)
(t, сим буква)
(h, сим буква)
(e, сим буква)
(n, сим буква)
( , сим пробел)
(x, сим буква)
((,сим скобка)(f, сим буква)
(1, сим цифра)
(,,сим запятая)
(f, сим буква)
(2, сим цифра)
(,,сим запятая)
(f, сим буква)
(3, сим цифра)
(),сим скобка)
(,сим пробел)
(e, сим буква)
(l, сим буква)
(s, сим буква)
(e, сим буква)
(,сим пробел)
(d, сим буква)
((,сим скобка)(с, сим буква)
(1, сим цифра)
(,,сим запятая)
(с, сим буква)
(2, сим буква)
(),сим скобка)
(;,сим тчкзпт) (if,условие)
(b,символ)
(then, условие)
(х, символ)
((,скобка)(f1, идентификатор)
(,,запятая)
(f2, идентификатор)
(,,запятая)
(f3, идентификатор)
(),скобка)
(else, условие)
(d, символ)
((,скобка)(c1, идентификатор)
(,,запятая)
(c2, идентификатор)
(),скобка)
(;,тчкзпт)
Блок идентификации ключевых слов if
b
then
x
else
d Кл слово
Не кл слово
Кл слово
Не кл слово
Кл слово
Не кл слово
Синтаксический блок (if,условие)
(b,символ)
(then, условие)
(х, символ)
((,скобка)(f1, идентификатор)
(,,запятая)
(f2, идентификатор)
(,,запятая)
(f3, идентификатор)
(),скобка)
(else, условие)
(d, символ)
((,скобка)(c1, идентификатор)
(,,запятая)
(c2, идентификатор)
(),скобка)
(;,тчкзпт) Правильно
Головной модуль IF b THEN x(f1, f2, f3) ELSE d(e1, e2, e3); ACCEPT
IF TRUE THEN a(b3) ELSE a(c7); ACCEPT
IF b THEN x(f1, f2, f3) ELSE d(e1, e2, e3) REJECT
FOR r THEN x(f1, f2, f3) ELSE d(e1, e2); REJECT
IF b THEN TRUE ELSE x(d6); REJECT
IF 5 THEN v(t1,f2) ELSE m(u2,f1); REJECT
3. Кодирование
3.1. Блок транслитерации
Блок транслитерации реализован в виде детерминированного конечного автомата ,который выполняет обработку и распознавание входной символьной цепочки. Обработка входной цепочки заключается в собственно выполнении транслитерации – формировании цепочки лексем вида ("символ цепочки", "класс символа цепочки"). Распознавание входной цепочки означает, что данный автомат должен отвергать все символьные цепочки, содержащие символы, которые заведомо не удовлетворяют формулам Бэкуса–Наура из условия задачи (например, буквы кириллицы, символы @, # и др.).
Транслитерация символьной цепочки:
Символ Класс
a..z, A..Z
0..9
,
;
(
) Буква
Цифра
Запятая
ТчкзптПробел
Откр. скобка
Закр. скобка
другие ошибка
3.2 Лексический блок
Лексический блок реализован в виде детерминированного конечного автомата, который выполняет обработку и распознавание входной цепочки лексем (полученной как результат работы блока транслитерации). Обработка входной цепочки заключается в формировании цепочки лексем вида ("символ входного языка", "класс символа входного языка"). Распознавание входной цепочки означает, что данный автомат должен отвергать все цепочки лексем, содержащие лексемы, которые заведомо не удовлетворяют
формулам Бэкуса–Наура из условия задачи (например, два знака числа подряд, знак числа после десятичной точки и др.).
Построение конечного автомата лексического блока необходимо выполнить следующим образом. Сначала, используя метод разметки символов, нужно построить конечный распознаватель входной цепочки лексем: определить список состояний (название/номер и семантика состояния), выделить в данном списке начальное состояние и допускающие состояния и указать функцию переходов.

IF b THEN x(f1, f2, f3) ELSE d(e1, e2);
№ п/п Состояние Семантика
1 НАЧ Момент до начала обработки цепочки либо чтение пробелов в начале строки
2 КЛСЛОВО1Чтение ключевого слова if
3 ПРОБЕЛ 1 Чтение пробелов, находящихся между ключевым словом if и именем
4 ИМЯ1Чтение имени
5 ПРОБЕЛ 2 Чтение пробелов, находящихся между именем и ключевым словом
6 КЛСЛОВО2Чтение ключевого слова then
7 ПРОБЕЛ 3 Чтение пробелов, находящихся между ключевым словом then и именем
8 ИМЯ2Чтение имени
9 ПРОБЕЛ 4 Чтение пробелов, находящихся между именем и скобкой
10 СКОБКА1.1 Чтение скобки открывающей список параметров
11 ИМЯ2.1 Чтение имени 1 параметра
12 ЗАПЯТАЯ Чтение запятой
13 ИМЯ2.2 Чтение имени 2 параметра
14 ЗАПЯТАЯ Чтение запятой
15 ИМЯ2.3 Чтение имени 3 параметра
16 СКОБКА1.2 Чтение скобки закрывающей список параметров
17 ПРОБЕЛ 5 Чтение пробелов между скобкой и ключевым словом
18 КЛСЛОВО 3 Чтение ключевого слова else
19 ПРОБЕЛ 6 Чтение пробелов, находящихся между ключевым словом и именем
20 ИМЯ 3 Чтение имени
21 ПРОБЕЛ 7 Чтение пробелов, находящихся между именем и скобкой
22 СКОБКА 2.1 Чтение скобки открывающей список параметров
23 ИМЯ2.1 Чтение имени 1 параметра
24 ЗАПЯТАЯ Чтение запятой
25 ИМЯ2.2 Чтение имени 2 параметра
26 СКОБКА 2.2 Чтение скобки открывающей список параметров
27 ТЧКЗПТ Чтение точки с запятой
Конечный распознаватель лексического блока:
Буква Цифра Пробел Запятая Скобка ТчкзптНАЧ КЛСЛОВО1Е НАЧ Е Е Е
КЛСЛОВО1КЛСЛОВО1Е ПРОБЕЛ 1 Е Е Е
ПРОБЕЛ 1 ИМЯ1ИМЯ Е Е Е Е
ИМЯ1Е Е ПРОБЕЛ 2 Е Е Е
ПРОБЕЛ 2 КЛСЛОВО2Е Е Е Е Е
КЛСЛОВО2Е Е ПРОБЕЛ3 Е Е Е
ПРОБЕЛ 3 ИМЯ2ИМЯ Е Е Е Е
ИМЯ2Е Е ПРОБЕЛ 4 Е Е Е
ПРОБЕЛ 4 Е Е Е Е СКОБКА Е
СКОБКА1.1 ИМЯ2.1 ИМЯ Е Е Е Е
ИМЯ2.1 Е Е Е ЗАПЯТАЯ Е Е
ЗАПЯТАЯ ИМЯ2.2 ИМЯ Е Е Е Е
ИМЯ2.2 Е Е Е ЗАПЯТАЯ Е Е
ЗАПЯТАЯ ИМЯ2.3 ИМЯ Е Е Е Е
ИМЯ2.3 Е Е Е Е СКОБКА Е
СКОБКА1.2 Е Е ПРОБЕЛ 8 Е Е Е
ПРОБЕЛ 5 КЛСЛОВО3 Е Е Е Е Е
КЛСЛОВО 3 Е Е ПРОБЕЛ 9 Е Е Е
ПРОБЕЛ 6 ИМЯ3 ИМЯ Е Е Е Е
ИМЯ 3 Е Е ПРОБЕЛ 10 Е Е Е
ПРОБЕЛ 7 Е Е Е Е СКОБКА Е
СКОБКА 2.1 ИМЯ3.1 ИМЯ Е Е Е Е
ИМЯ2.1 Е Е Е ЗАПЯТАЯ Е Е
ЗАПЯТАЯ ИМЯ3.2 ИМЯ Е Е Е Е
ИМЯ2.2 Е Е Е Е СКОБКА Е
СКОБКА 2.2 Е Е Е Е Е ТЧКЗПТ
ТЧКЗПТ Е Е Е Е Е Е
Редукция конечного распознавателя лексического блока:
Шаг Результат( блоки состояний) Действия
0 Р0={НАЧ, КЛСЛОВО, ПРОБЕЛ 1, ИМЯ, ПРОБЕЛ 2, КЛСЛОВО, ПРОБЕЛ 3, ИМЯ, ПРОБЕЛ 4, КЛСЛОВО, ПРОБЕЛ 5, ИМЯ ,ТЧКЗПТ} Разбиваем P0 на два блока: допустимые и отвергающие состояния
1 Р11= { НАЧ, КЛСЛОВО, ПРОБЕЛ 1, ИМЯ, ПРОБЕЛ 2, КЛСЛОВО, ПРОБЕЛ 3, ИМЯ, ПРОБЕЛ 4, КЛСЛОВО, ПРОБЕЛ 5, ИМЯ }Р12= {ТЧКЗПТ} Разбиваем P11 по входу буква
2 Р21= {НАЧ, КЛСЛОВО}
Р22= {ПРОБЕЛ 1, ИМЯ}
Р23= { ПРОБЕЛ 2, КЛСЛОВО }Р24= { ПРОБЕЛ 3, ИМЯ }Р25= { ПРОБЕЛ 4, КЛСЛОВО }Р26={ ПРОБЕЛ 5, ИМЯ }Р27= {ТЧКЗПТ} 1. Разбиваем Р21 по входу цифра
2. Разбиваем Р22 по входу цифра
3. Разбиваем Р23 по входу двоеточие
4. Разбиваем Р24по входу тчкзпт3 Р31= {НАЧ }Р32= { КЛСЛОВО }Р33= { ПРОБЕЛ 1 }Р34= { ИМЯ }Р35= { ПРОБЕЛ 2 }Р36= { КЛСЛОВО }Р37= { ПРОБЕЛ 3}
Р38= { ИМЯ }Р39= { ПРОБЕЛ 4 }Р310={ КЛСЛОВО }Р311={ ПРОБЕЛ 5 }Р312={ ИМЯ }Р313= {ТЧКЗПТ}
Разбиваем Р39 по входу тчкзпт
Примитивные процедуры обрабатывающего автомата
№ пПроцедура Семантика
0 Да Остановить обработку и допустить цепочку
1 Нет Остановить обработку и отвергнуть цепочку
2 Обработать Добавить входной символ к значению текущей лексемы
3 Лексема (класс) Увеличить счетчик лексем на 1, установить заданный класс текущей лексемы
Процедуры переходов обрабатывающего автомата лексического блока
Действие Семантика
1 Лексема(if); Обработать;
2 Обработать;
3 Лексема(имя); Обработать;
4 Обработать;
5 Лексема(then); Обработать;
6 Обработать;
7 Лексема(имя); Обработать;
8 Лексема(идентифик); Обработать;
9 Обработать;
10 Лексема(else); Обработать;
11 Обработать;
12 Лексема(имя); Обработать;
13 Лексема(идентифик); Обработать;
14 Лексема(ТЧКЗПТ); Обработать;
3.3 Синтаксический блок
Конечный распознаватель синтаксического блока:
Клслово if Клслово then Клслово else Идентификатор Скобка ЗптТчкзптНАЧ IF if ИДЕНТИФИК ИМЯ1THEN then ИДЕНТИФИК ИМЯ2СКОБКА СКОБКА1.1 ИДЕНТИФИК ИМЯ2.1 ЗПТ ЗАПЯТАЯ ИДЕНТИФИК ИМЯ2.2 ЗПТ ЗАПЯТАЯ ИДЕНТИФИК ИМЯ2.3 СКОБКА СКОБКА1.2 ELSE else ИДЕНТИФИК ИМЯ 3 СКОБКА СКОБКА 2.1 ИДЕНТИФИК ИМЯ2.1 ЗПТ ЗАПЯТАЯ ИДЕНТИФИК ИМЯ2.2 СКОБКА СКОБКА 2.2 ТчкзптТЧКЗПТ Тестирование
На этапе тестирования мы выполнили тестовые программы модулей, используя в качестве входных данных входные данные подготовленных ранее тестов, и сравнили полученные выходные данные с выходными данными тестов.
В случае, если установлен факт наличия ошибки, необходимо провести отладку данного модуля. Отладка модуля подразумевает поиск и устранение ошибки. При выполнении отладки полезно сочетать использование отладчика системы программирования с "сухой" отладкой (работа без компьютера, с карандашом и листингом модуля). После устранения ошибки необходимо вновь выполнить тестирование данного модуля на всех тестах. Тестирование и последующая отладка модуля продолжаются до тех пор, пока тестирование не приведет к совпадению всех ожидаемых и действительных результатов.
Пример протокола тестирования головного модуля
№п/п Входные данные Выходные данные Действительный результат Тест пройден?
1 IF b THEN x(f1, f2, f3) ELSE d(e1, e2, e3) ACCEPT ACCEPT Да
2 FOR r THEN x(f1, f2, f3) ELSE d(e1, e2); ACCEPT ACCEPT Да
3 IF b THEN TRUE ELSE x(d6); REJECT REJECT Да
4 IF 5 THEN v(t1,f2) ELSE m(u2,f1); REJECT REJECT Да
5 IF b THEN x(f1, f2, f3) ELSE d(e1, e2, e3) REJECT REJECT Да
6 FOR r THEN x(f1, f2, f3) ELSE d(e1, e2); REJECT REJECT Да
Заключение
В ходе разработки программы были пройдены несколько основных этапов, таких как: проектирование, кодирование и тестирование, каждый из которых имел свое собственное место и значение в нашей программе. Были разработаны блок транслитерации, лексический и синтаксический блоки, а так же было проведено тестированием программы, которое показало, правильно ли работает она и чем больше сделано входных цепочек, тем больше вероятность найти ошибки, чтобы затем исправить их. В итоге получена полностью готовая и рабочая программа.
Литература
Методические указания по вычислительной практике студентов, М.Л.Цымбер и А.Н.Янченкоhtpp:\\www.hochyvseznat.ru
htpp:\\www.wikipedia.ru

Приложенные файлы

  • docx 26541577
    Размер файла: 54 kB Загрузок: 0

Добавить комментарий