Синтаксический анализатор на основе грамматики операторного предшествования(С ПРОГРАММОЙ В DELPHI)

Техническое задание:
I. Разработать грамматику для моделирования работы компилятора согласно своему варианту.
Построить лексический анализатор, который решает следующие задачи: выделяет из текста входной программы все лексемы, входящие в языковую конструкцию – «простые типы, процедуры и функции пользователя языка Паскаль», идентификаторы, константы; удаляет лишние пробелы и комментарии из входной строки.
II. Построить синтаксический анализатор на основе грамматики операторного предшествования. Дополнительные множества, необходимые для заполнения таблиц разбора, должны строиться автоматически. Таблицы разбора должны заполняться автоматически с использованием алгоритмов, предложенных в учебниках Гордеева, Молчанова. Результатом работы синтаксического анализатора должно быть дерево вывода ...

Оглавление
ВВЕДЕНИЕ 3
Основные фазы компиляции: 6
1.Лексический анализ 6
2. Синтаксический анализ 7
3. Семантический анализ 7
4. Оптимизация 7
5. Генерация кода 8
Построение компилятора 8
1. Этапы построения компилятора 8
1. 1. Построение лексического анализатора 8
1.2. Построение синтаксического анализатора 11
Описание в виде правил КС-грамматики 12
Описание грамматики в форме Бэкуса-Наура 15
Описание грамматики на языке синтаксических диаграмм 17
Синтаксический анализатор грамматики операторного предшествования 23
Алгоритм функционирования синтаксического анализатора 27
1.3. Построение дерева разбора 28
1.4. Внутреннее представление 28
1.5. Аннотированное дерево 29
2. Сведения о программе 31
2.1 Общие сведения 31
2.2. Функциональное назначение 31
3.3. Логическая структура программы 31
2.4. Используемые технические средства 33
2.5. Вызов и загрузка 33
2.6. Входные данные 33
2.7. Выходные данные 34
3. Протокол выполнения программы 34
ЗАКЛЮЧЕНИЕ 35
СПИСОК ЛИТЕРАТУРЫ 36
ПРИЛОЖЕНИЕ 1 37
ПРИЛОЖЕНИЕ 2 46
ПРИЛОЖЕНИЕ 3 49
ПРИЛОЖЕНИЕ 4 122
ПРИЛОЖЕНИЕ 5 13

Каждая вычислительная машина имеет свой собственный язык программи¬рования — язык команд или машинный язык — и может исполнять программы, записанные только на этом языке. С помощью машинного языка, в принципе, можно описать любой алгоритм, но затраты на программирование будут чрезвы¬чайно велики. Это обусловлено тем, что машинный язык позволяет описывать и обрабатывать лишь примитивные структуры данных — бит, байт, слово. Про¬граммирование в машинных кодах требует чрезмерной детализации программы и доступно лишь программистам, хорошо знающим устройство и функционирование ЭВМ. Преодолеть эту трудность и позволили языки высокого уровня (Фор¬тран, ПЛ/1, Паскаль, Си, Ада, и др.) с развитыми структурами данных и сред¬ствами их обработки, не зависящими от языка конкретной ЭВМ.
Алгоритмические яз ыки высокого уровня обладают достаточно высокой изобразительной силой, они дают возможность программисту достаточно про¬сто и удобно описывать алгоритмы решения многих прикладных задач. Такое описание называют исходной программой, а язык высокого уровня — входным языком.
Языковым процессором называют программу на машинном языке, по-зволяющую вычислительной машине понимать и выполнять программы на входном языке. Различают два основных типа языковых процессоров: интер¬претаторы и трансляторы [2].
Интерпретатор — это программа, которая в качестве входа допускает программу на входном языке и по мере распознавания конструкций входного языка реализует их, выдавая на выходе результаты вычислений, предписанные исходной программой.
Транслятор — это программа, которая допускает на входе исходную программу и порождает на своем выходе программу, функционально-эквива¬лентную исходной, называемую объектной. Объектная программа записыва¬ется на объектном языке. В частном случае, объектным языком может служить машинный язык, и в этом случае полученную на выходе транслятора про¬грамму можно сразу же выполнить на ЭВМ (проинтерпретировать). При этом ЭВМ является интерпретатором объектной программы в машинных кодах. В общем случае объектный язык необязательно должен быть машинным или близким к нему (автокодом). В качестве объектного языка может служить некоторый промежуточный язык — язык, лежащий между входным и ма¬шинным языками.
Если в качестве объектного языка используется промежуточный язык, то возможны два варианта построения транслятора.
Первый вариант — для промежуточного языка имеется (или разрабаты¬вается) другой транслятор — с промежуточного языка на машинный, и он ис¬пользуется в качестве последнего блока проектируемого транслятора.
Второй вариант построения транслятора с использованием промежу-точного языка — построить интерпретатор команд промежуточного языка и использовать его в качестве последнего блока транслятора. Преимущество интерпретаторов проявляется в отладочных и диалоговых трансляторах, обес¬печивающих работу пользователя в диалоговом режиме, вплоть до внесений изменений в программу без ее повторной полной перетрансляции.
Интерпретаторы используются также и при эмуляции программ — ис-полнении на технологической машине программ, составленных для другой (объектной) машины) Данный вариант, в частности, используется при отладке на универсальной ЭВМ программ, которые будут выполняться на специализи¬рованной ЭВМ.
Транслятор, использующий в качестве входного языка язык, близкий к машинному (автокод или ассемблер), традиционно называют ассемблером. Транслятор для языка высокого уровня называют компилятором.
В построении компиляторов за последние годы достигнуты значитель-ные успехи. Первые компиляторы использовали так называемые прямые ме¬тоды трансляции — это преимущественно эвристические методы, в которых на основе общей идеи для каждой конструкции языка разрабатывался свой ал¬горитм перевода в машинный эквивалент [2]. Эти методы были медленные и не носили структурного характера. В основе методики проектирования совре¬менных компиляторов лежит композиционный синтаксически-управляемый метод обработки языков. Композиционный в том смысле, что процесс перево¬да исходной программы в объектную реализуется композицией функциональ¬но независимых отображений с явно выделенными входными и выходными структурами данных. Отображения эти строятся из рассмотрения исходной программы, как композиции основных аспектов (уровней) описания входного языка: лексики, синтаксиса, семантики и прагматики, и выявления этих аспек¬тов из исходной программы в ходе ее компиляции.
Перевод программы с одного языка на другой, в общем случае, состоит в изменении алфавита, лексики и синтаксиса языка программы с сохранени¬ем ее семантики. Процесс трансляции исходной программы в объектную обычно разбивается на несколько независимых подпроцессов (фаз трансля¬ции), которые реализуются соответствующими блоками транслятора. Удоб¬но считать основными фазами трансляции лексический анализ, синтаксический анализ, семантический анализ и синтез объектной програм¬мы. Тем не менее, во многих реальных компиляторах эти фазы разбиваются на несколько подфаз, могут также быть и другие фазы (например, оптими¬зация объектного кода) [2]. На рис.1 показана упрощенная функциональ¬ная модель транслятора.

построение синтаксического анализатора;
построение дерева разбора;
3. ТРЕБОВАНИЯ К ПРОГРАММЕ
3.1 Требования к функциональным характеристикам
Программа должна иметь удобный интерфейс, понятный любому пользователю, даже не имеющему навыков программирования. В ходе выполнения программы должно осуществляться:
Ввод символьных и числовых данных с клавиатуры;
Обработку символьных и числовых данных:
Лексический анализ входной строки (на основе конечного автомата);
Синтаксический анализ входной строки (на основе грамматики операторного предшествования);
Построение дерева разбора (как результата работы синтаксического анализатора).
Наглядное представление результатов;
Поиск ошибок, а также вызов подпрограммы восстановления после ошибки.
Основными входными данными являются разработанныеправила грамматики, а также текстовые строки, вводимые пользователем с клавиатуры, либо загружаемые из файла и предлагаемые программе для распознавания.
Выходные данные будут представлены в виде таблицы идентификаторов, таблицы последовательности разбора входной цепочки, дерева вывода и соответствующего ему порождения рассматриваемой последовательности символов, формы внутреннего представления выполняемых инструкций – ассемблерного кода.
Должна выводиться информация о допуске входной строки лексическим и синтаксическим анализаторами.
3.2. Требования к надежности
В ходе выполнения программы должна быть предусмотрена обработка неверных действий пользователя (неверный порядок действий, некорректный ввод данных), а также обработку ошибок, полученных в ходе выполнения программы.
В программе должны быть предусмотрено обеспечение обработки или корректного завершения программы в случае ошибки;
Пользователь должен быть уведомлен о возникающих ошибках через сообщения.
3.3.Требования к составу и параметрам технических средств
В состав технических средств должен входить IВМ-совместимый персональный компьютер (ПЭВМ), включающий в себя:
процессор Pentium 200МГц, не менее;
оперативную память объемом, 128 Мбайт, не менее;
свободного пространства на жестком диске, 20Мбайт, не менее;
операционную систему Windows 98, Windows 2000, Windows XP, Windows Vista, Windows 7.
3.4. Специальные требования.
Специальных требований не предъявляется.
4.ТРЕБОВАНИЯ К ПРОГРАММНОЙ ДОКУМЕНТАЦИИ
К программе должно прилагаться:
руководство пользователя;
блок-схемы алгоритмов;
текст программы;
расчетно-пояснительная записка.
Программная документация должна оформляться на листах формата А4 по действующим стандартам ЕСПД.
5. УСЛОВИЯ ЭКСПЛУАТАЦИИ
Программа предназначена для работы на одном персональном компьютере одним пользователем, не требует наличия обслуживающего персонала. От пользователя не требуется знание языков программирования.
5.СТАДИИ И ЭТАПЫ РАЗРАБОТКИ
Разработка должна быть проведена в три стадии:
1. разработка технического задания;
2. рабочее проектирование;
3. внедрение.
На стадии разработки технического задания должен быть выполнен этап разработки, согласования и утверждения настоящего технического задания.
На стадии рабочего проектирования должны быть выполнены перечисленные ниже этапы работ:
1. постановка задачи;
2. разработка грамматики, анализ структуры входных и выходных данных;
3. разработка алгоритма;
4. разработка интерфейса;
5. реализация разработанного алгоритма;
6. отладка и тестирование;
7. разработка программной документации.
6. ПОРЯДОК КОНТРОЛЯ И ПРИЕМА
Основные этапы приема курсовой работы:
№
Дата
Вид работ
Форма отчета
1
05.04.2010