Лабораторные работы по Теории вычислительных процессов и структур

| Категория реферата: Рефераты по информатике, программированию
| Теги реферата: рефераты по психологии, банк рефератов 5 баллов
| Добавил(а) на сайт: Антипов.

2.2. В соответствии с выданным вариантом выполнить следующее:

2.2.1. Составит техническое задание (ТЗ) на разработку программы сканера, производящей лексический анализ произвольных текстов в пределах установленного алфавита.

2.2.2. Согласовать ТЗ с преподавателем.

2.2.3. Разработать программу-сканер на языках
Паскаль, С++ или в интегрированных средах по собственному усмотрению.

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

2.2.5. Составить отчёт по работе и приложить к нему ТЗ.

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

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

Таблица 1. Алфавит входного языка.
|№ | Алфавит |
| 1 |Латинский, строчные буквы |
| 2 |Латинский, заглавные буквы |
| 3 |Кириллица, строчные буквы |
| 4 |Кириллица, заглавные буквы |
| 5 |Латинский, строчные + заглавные |
| 6 |Кириллица, строчные + заглавные |

Таблица 2. Ключевые слова.
|№ | Дополнительные ключевые слова |
| 1 |Описание циклов, массивов |
| 2 |Описание операторов перехода, |
| |структуры типа switch |
| 3 |Описание безусловных переходов, |
| |описание функций |

Таблица 3. Библиотечные функции.
|№ | Стандартные функции |
|1 |sin, cos, tan, exp |
| |sqrt, log, ln, nearby |
|2 | |
| 3 |abs, fact, code, sign |

Например, 1-2-3 означает, что из первой таблицы необходимо выбрать первую строку, из второй таблицы - вторую строку, из третьей таблицы - третью строку.

Для всех вариантов задаётся общая часть в которую входит следующее.
Ключевые слова обозначающие начало и конец программы, описание типа, ввод и вывод, присваивание.

Разделители : +, -, *, :, _, /, (, ), {, }, =, , [,
], ;, “, ‘ , ‘,’ и про- бел.

Идентификаторы должны начинаться с буквы, не включать в себя разделители, количество позиций не должно превышать 14.

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

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

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

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

Затем, проводится идентификация лексемы. Она заключается в сборке лексемы из символов, начиная с выделенного на предыдущем этапе, и проверки правильности записи лексемы данного класса.

Идентификация лексемы из конечного класса выполняется путём сравнения её с эталонным значением. Основная проблема здесь - минимизация времени поиска эталона. В общем случае может понадобиться полный перебор слов данного класса, особенно, если выделенное слово содержит ошибку. Уменьшить время поиска можно, используя различные методы ускоренного поиска: упорядоченный список, линейный список, метод расстановки и др.

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

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

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

В ходе лексического анализа могут выполняться и другие виды лексического контроля, в частности, проверяться парность скобок и других парных символов, наличие метки у оператора, следующего за GOTO и т.д.