Автор: Пользователь скрыл имя, 19 Мая 2012 в 17:24, курсовая работа
Теория формальных языков, грамматик и автоматов составляет фундамент синтаксических методов. Основы этой теории были заложены Н. Хомским в 40–50-е годы XX столетия в связи с его лингвистическими работами, посвященными изучению естественных языков. Но уже в следующем десятилетии синтаксические методы нашли широкое практическое применение в области разработки и реализации языков программирования.
Введение 3
1 Постановка задачи 4
2 Формальная модель задачи 5
3 Структура программы………………………………………………….....16
3.1 Лексический анализатор 16
3.2 Синтаксический анализатор 18
3.3 Семантический анализатор 20
3.4 Генерация ПОЛИЗа программы 22
3.5 Интерпритация ПОЛИЗа программы 24
4 Структурная организация данных 31
4.1 Спецификация входной информации 31
4.2 Спецификация выходной информации 31
4.3 Спецификация процедур и функций 31
5 Разработка алгоритма решения задачи 32
5.1 Укрупненная схема алгоритма программного средства 32
5.2 Детальная разработка алгоритмов отдельных подзадач 33
6 Установка и эксплуатация программного средства 34
7 Работа с программным средством 35
Заключение 36
Список использованных источников 37
Приложение А – Текст программы 38
3.4 Генерация ПОЛИЗа
программы
В ПОЛИЗе операнды записаны слева направо в порядке использования. Знаки операций следуют таким образом, что знаку операции непосредственно предшествуют его операнды.
Пример 1: Для выражения в обычной (инфиксной записи) a*(b+c)-(d-e)/f ПОЛИЗ будет иметь вид: abc+*de-f/-.
Справедливы следующие формальные определения.
Определение: Если B является единственным операндом, то ПОЛИЗ выражения B – это этот операнд.
Определение: ПОЛИЗ выражения B1 q B2, где q - знак бинарной операции, B1 и B2 – операнды для q, является запись , где - ПОЛИЗ выражений B1 и B2 соответственно.
Определение: ПОЛИЗ выражения qB, где q - знак унарной операции, а B – операнд q, есть запись , где - ПОЛИЗ выражения B.
Определение: ПОЛИЗ выражения (B) есть ПОЛИЗ выражения B.
Оператор присваивания I ass B в ПОЛИЗе записывается:
I B ass,
где «ass» - двуместная операция,
I, B – операнды операции присваивания;
I – означает, что операндом операции «ass» является адрес переменной I, а не ее значение.
Пример 2: Оператор x ass x+9 в ПОЛИЗе имеет вид: x x 9 + ass.
Оператор перехода в терминах ПОЛИЗа означает, что процесс интерпретации необходимо продолжить с того элемента ПОЛИЗа, который указан как операнд операции перехода. Чтобы можно было ссылаться на элементы ПОЛИЗа, будем считать, что все они пронумерованы, начиная с единицы (например, последовательные элементы одномерного массива). Пусть ПОЛИЗ оператора, помеченного меткой L, начинается с номера p, тогда оператору безусловного перехода goto L в ПОЛИЗе будет соответствовать:
p!, где ! – операция выбора элемента ПОЛИЗа, номер которого равен p.
Условный оператор. Введем вспомогательную операцию – условный переход «по лжи» с семантикой if not E goto L. Это двуместная операция с операндами E и L. Обозначим ее !F, тогда в ПОЛИЗе она будет записываться:
E p !F, где p – номер элемента, с которого начинается ПОЛИЗ оператора, помеченного меткой L.
С использованием введенной операции условный оператор if E then S else S4 в ПОЛИЗе будет записываться:
E p1
!F S p2 ! S4, где p1
– номер элемента, с которого начинается
ПОЛИЗ оператора S4, а p1
– оператора, следующего за условным оператором.
Пример
3: ПОЛИЗ оператора if x>0 x ass x-5 else x ass
x*2 представлен в таблице 2.3.
Таблица 3 – ПОЛИЗ оператора if
| лексема | x | 0 | > | 13 | !F | x | x | 5 | - | ass | 18 | ! | x | x | 2 | * | ass | … |
| Номер | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 |
Оператор цикла while. С учетом введенных операций оператор цикла while E do S в ПОЛИЗе будет записываться:
E p1 !F S po !, где po – номер элемента, с которого начинается ПОЛИЗ выражения B, а p1 – оператора, следующего за данным оператором цикла.
Оператор цикла for. С учетом введенных операций оператор цикла for G to E do S в ПОЛИЗе будет записываться:
G E I <= p1 !F S I I 1 +ass po !, где po – номер элемента, с которого начинается операция сравнения , а p1 – оператора, следующего за данным оператором цикла.
Операторы ввода и вывода языка М одноместные. Пусть R – обозначение операции ввода, а W – обозначение операции вывода, тогда оператор read (I) в ПОЛИЗе запишется как I R, а оператор write (E) – E W.
Составной оператор begin S1; S2;...; Sn end в ПОЛИЗе записывается как S1 S2... Sn.
Пример 4: ПОЛИЗ оператора while n<9 do t ass n*n-1: n ass n-1;
Таблица 4 – ПОЛИЗ оператора while
Синтаксически управляемый перевод.
На
практике СиА, СеА и генерация
внутреннего представления
Пример 5: Составим процедуры перевода в ПОЛИЗ программы на языке М.
ПОЛИЗ представляет собой массив, каждый элемент которого является парой вида (n, k), где n – номер таблицы лексем, k – номер лексемы в таблице. Расширяем набор лексем:
1)
в таблицу ограничителей
2)
для ссылок на номера
3)
чтобы различать операнды-
3.5 Интерпретация ПОЛИЗа программы
Ход интерпретации программы с помощью таблицы
Интерпретируем следующую программу:
program
var integer a,b;
begin
b ass 1;
for a ass 1 to 2 do
b ass b+1
write(b)
end.
ПОЛИЗ данной программы будет иметь вид:
Таблица 5 – ПОЛИЗ исходной программы
| Лексема | b | 1 | ass | a | 1 | ass | a | 2 | <= | 26 | !F |
| Номер | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
| Лексема | b | b | 1 | + | ass | b | W | a | a | 1 | + |
| Номер | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 |
| Лексема | ass | 7 | ! | . |
| Номер | 23 | 24 | 25 | 26 |
Процесс интерпретации
программы на модельном языке
М, записанной в форме ПОЛИЗа, показан
в таблице 6.
Таблица 6 – Ход интерпретации ПОЛИЗа программы
| Стек | Текущий элемент ПОЛИЗа | Операция | Таблицы
переменных | |
| адреса | значения | |||
| пуст | 1 | адрес - в стек | 1) a
2) b |
1) -
2) - |
| 2 | 2 | число в стек | 1) a
2) b |
1) -
2) - |
| 2;1 | 3 | присвоить второму элементу таблицы значений число 1 | 1) a
2) b |
1) -
2) 1 |
| пуст | 4 | адрес - в стек | 1) a
2) b |
1) -
2) 1 |
| 1 | 5 | число в стек | 1) a
2) b |
1) -
2) 1 |
| 1;1 | 6 | присвоить первому элементу таблицы значений число 1 | 1) a
2) b |
1) 1
2) 1 |
| пуст | 7 | значение - в стек | 1) a
2) b |
1) 1
2) 1 |
| 1 | 8 | число в стек | 1) a
2) b |
1) 1
2) 1 |
| 1;2 | 9 | в стек – true, т.к. 1<=2 | 1) a
2) b |
1) 1
2) 1 |
| 1 | 10 | метка - в стек | 1) a
2) b |
1) 1
2) 1 |
| 1;22 | 11 | переход, к следующему элементу ПОЛИЗа, т.к. условие истинно | 1) a
2) b |
1) 1
2) 1 |
| пуст | 12 | адрес - в стек | 1) a
2) b |
1) 1
2) 1 |
| 2 | 13 | значение - в стек | 1) a
2) b |
1) 1
2) 1 |
| 2;1 | 14 | число в стек | 1) a
2) b |
1) 1
2) 1 |
| 2;1;1 | 15 | извлечь из стека 1 и 1 и поместить в стек их сумму | 1) a
2) b |
1) 1
2) 1 |
| 2;2 | 16 | присвоить второму элементу таблицы значений число 2 | 1) a
2) b |
1) 1
2) 2 |
| пуст | 17 | значение - в стек | 1) a
2) b |
1) 1
2) 2 |
| 2 | 18 | значение из стека на экран | 1) a
2) b |
1) 1
2) 2 |
| пуст | 19 | адрес - в стек | 1) a
2) b |
1) 1
2) 2 |
| 1 | 20 | значение - в стек | 1) a
2) b |
1) 1
2) 2 |
| 1,1 | 21 | число в стек | 1) a
2) b |
1) 1
2) 2 |
| 1,1,1 | 22 | 2 из стека + и результат в стек | 1) a
2) b |
1) 1
2) 2 |
| 1,2 | 23 | присваиваем 2 по адресу 1 | 1) a
2) b |
1) 2
2) 2 |
| пуст | 24 | адрес в стек | 1) a
2) b |
1) 2
2) 2 |
| 7 | 25 | переход к элементу
ПОЛИЗа, с номером, извлекаемым из вершины стека |
1) a
2) b |
1) 2
2) 2 |
| пуст | 7 | значение - в стек | 1) a
2) b |
1) 2
2) 1 |
| 2 | 8 | число в стек | 1) a
2) b |
1) 2
2) 1 |
| 2;1 |
9 | в стек – true, т.к. 2<=2 | 1) a
2) b |
1) 2
2) 1 |
| 1 | 10 | метка - в стек | 1) a
2) b |
1) 2
2) 1 |
| 1;22 | 11 | переход, к следующему элементу ПОЛИЗа, т.к. условие истинно | 1) a
2) b |
1) 2
2) 1 |
| пуст | 12 | адрес - в стек | 1) a
2) b |
1) 2
2) 1 |
| 2 | 13 | значение - в стек | 1) a
2) b |
1) 2
2) 1 |
| 2;2 | 14 | число в стек | 1) a
2) b |
1) 2
2) 1 |
| 2;2;1 | 15 | извлечь из стека 2 и 1 и поместить в стек их сумму | 1) a
2) b |
1) 2
2) 1 |
| 2;3 | 16 | присвоить второму элементу таблицы значений число 3 | 1) a
2) b |
1) 2
2) 2 |
| пуст | 17 | значение - в стек | 1) a
2) b |
1) 2
2) 3 |
| 3 | 18 | значение из стека на экран | 1) a
2) b |
1) 2
2) 3 |
| пуст | 19 | адрес - в стек | 1) a
2) b |
1) 2
2) 3 |
| 1 | 20 | значение - в стек | 1) a
2) b |
1) 2
2) 3 |
| 1,2 | 21 | число в стек | 1) a
2) b |
1) 2
2) 3 |
| 1,2,1 | 22 | 2 из стека + и результат в стек | 1) a
2) b |
1) 2
2) 3 |
| 1,3 | 23 | присваиваем 3 по адресу 1 | 1) a
2) b |
1) 2
2) 3 |
| пуст | 24 | адрес в стек | 1) a
2) b |
1) 3
2) 3 |
| 7 | 25 | переход к элементу
ПОЛИЗа, с номером, извлекаемым из вершины стека |
1) a
2) b |
1) 3
2) 3 |
| пуст | 7 | значение - в стек | 1) a
2) b |
1) 3
2) 3 |
| 3 | 8 | число в стек | 1) a
2) b |
1) 3
2) 3 |
| 3,2 | 9 | 2 из стека
и сравниваем,
т.к. 3<=2 то в стек false |
1) a
2) b |
1) 3
2) 3 |
| 0 | 10 | адрес в стек | 1) a
2) b |
1) 3
2) 3 |
| 0,26 | 11 | Т.к false то переход на 26 | 1) a
2) b |
1) 3
2) 3 |
| пуст | 26 | интерпретация завершена | 1) a
2) b |
1) 3
2) 3 |
4
Структурная организация
данных
4.1 Спецификация входной информации
| объявления | Пояснения |
| array <char> text(0); | Для хранения текста программы |
| array <AnsiString> slova(0); | Массив для хранения служебных слов |
| array <AnsiString> ogran(0); | Массив для хранения разделителей |
| AnsiString FILE_NAME; | Имя открытого файла |
4.2 Спецификация выходной информации
| объявления | пояснения |
| array <AnsiString> chisla(0); | Массив чисел в текстовом варианте |
| array <strB> NUM(0); | Массив чисел (внутреннее представление) |
| array <AnsiString> ident(0); | Массив для хранения идентификаторов |
| array <TL> lec(0); | Массив лексем |
| Form1->Memo3->Lines; | Поле возвращает коды синтаксических и семантических ошибок, а также ПОЛИЗ |
| Form1->Memo4->Lines; | Поле возвращает обратный диалог при интерпретации ПОЛИЗ |
4.3 Спецификация процедур и функций
| объявления | пояснения |
| AnalizeChislo | Распознает числа |
| LAnalize | Производит лексический анализ |
| ident_to | Строит и обрабатывает таблицу идентификаторов |
| typelec | Возвращает тип лексемы |
| Poliz | Находит полиз программы |
| errt | Обрабатывает ошибки в коде программы |
| SinAnalize | Производит синтаксический анализ |
| INP | Производит запись значения идентификаторов |
| OUTP | Производи вывод результатов работы программы |