Теория языков программирования и методы трансляции

↑

▷ Содержание

Стр 1 из 8Следующая ⇒

Теория языков программирования и методы трансляции

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

к выполнению лабораторных работ и курсового проектирования

по дисциплине «Теория языков программирования и методы трансляции»

Пенза 2003

УДК 681.3

Даны указания к выполнению лабораторных работ по курсу «Теория языков программирования и методы трансляции». Изложены основные требования к выполнению курсового проектирования, описаны основные этапы выполнения курсового проектирования, приведены основные требования ГОСТ по оформлению пояснительной записки и графической части.

Методические указания подготовлены на кафедре "Математическое обеспечение и применение ЭВМ" и предназначены для студентов специальности 230105.

Ил., табл., библиогр. назв.

Составители: Дорофеева О.С., Князев В.Н., Ракова А.Н.

Лабораторный практикум

ЛАБОРАТОРНАЯ РАБОТА № 1

Разработка конечного автомата

Цель работы - приобретение практических навыков разработки и проектирования конечных автоматов.

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

Краткое теоретическое введение

С помощью конечного автомата, представленного в виде графа, можно реализовать любую регулярную грамматику

G = (N,T,P,S),

где

N - множество нетерминальных символов;

T - множество терминальных символов;

P - множество правил (продукций) грамматики;

S - начальное состояние грамматики (начальный нетерминальный символ).

Конечный автомат - это пятерка объектов (K,VT,M,S,Z), где

К - алфавит элементов, называемых состояниями;

VT - алфавит, называемый входным алфавитом (символы, которые могут встретиться в цепочке);

М - отображение (или функция) множества КхVT во множество К (если М(Q,T) = R, то это означает, что из состояния Q при входном символе Т происходит переключение в состояние R);

S - начальное состояние из множества K;

Z - непустое множество заключительных состояний из множества К.

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

Если в процессе вывода цепочки языка для текущего символа нет дуг, помеченных данным символом, то это означает, что цепочка не входит в язык, и процедура закончена.

Если по исчерпании символов цепочки оказывается, что достигнута конечная вершина, то процедура закончена и цепочка входит в язык.

Пример

Рассмотрим регулярную грамматику G = (N,T,P,S)

S::= A0|B1

A::= S1|1

B::= S0|0

Порождаемый данной грамматикой язык состоит из последовательностей, образуемых парами 01 или 10, т.е.

, где B = {01, 10}.

Данной грамматике G соответствует конечный автомат с состояниями S,A,B,Z, где

S - начальное состояние;

Z - конечное состояние.

Граф для конечного автомата представлен на рис. 1.1.

Рис. 1.1

Матрица переходов состояний для данного конечного автомата представлена в табл. 1.1.

Таблица 1.1

Например, цепочка "10010110" входит в язык, а цепочка "110110" - нет.

ЗАДАНИЕ

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

Примечание.

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

СОДЕРЖАНИЕ ОТЧЕТА

Отчет о выполнении лабораторной работы должен содержать:

· титульный лист;

· задание;

· граф для конечного автомата;

· укрупненную схему программы;

· листинг программы;

· результаты тестирования;

· выводы по выполненной работе.

ВАРИАНТЫ ЗАДАНИЙ

Варианты заданий представлены в табл. 1.2.

Таблица 1.2

ЛАБОРАТОРНАЯ РАБОТА № 2

Разработка детерминированного конечного автомата
по регулярному выражению и недетерминированному
конечному автомату

Цель работы - приобретение практических навыков детерминирования конечных автоматов.

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

Пример

Задано регулярное выражение (101 | 110)*

Составляем недетерминированный конечный автомат, принимающий данное регулярное выражение и имеющий состояния S, T, U, W, F, где S - начальное состояние, S, F - конечные состояния. Граф для данного конечного автомата представлен на рис. 1.2.

Детерминируем конечный автомат. В итоге имеем детерминированный конечный автомат с состояниями S, TV, U, W, F, где S - начальное состояние, S, F - конечные состояния. Граф для данного конечного автомата представлен на рис. 1.3.

Рис 1.2 Рис 1.3

ЗАДАНИЕ

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

СОДЕРЖАНИЕ ОТЧЕТА

Отчет о выполнении лабораторной работы должен содержать:

· титульный лист;

· задание;

· граф для недетерминированного конечного автомата;

· граф для детерминированного конечного автомата;

· результаты тестирования;

· выводы по выполненной работе.

ВАРИАНТЫ ЗАДАНИЙ

Варианты заданий приведены в табл. 2.1.

Таблица 2.1

ЛАБОРАТОРНАЯ РАБОТА № 3

Разработка транслятора

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

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

Задание

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

Примечание.

Форма транслятора (компилятор или интерпретатор), его структура и язык кодирования для программной реализации задаются преподавателем.

СОДЕРЖАНИЕ ОТЧЕТА

Отчет о выполнении лабораторной работы должен содержать:

· титульный лист;

· задание;

· укрупненную схему программы;

· листинг программы;

· результаты тестирования;

· выводы по выполненной работе.

ВАРИАНТЫ ЗАДАНИЙ

На основании базового описания языка и в соответствии с вариантом задания разработать транслятор с заданного языка. Базовое описание языка имеет следующий вид:

<Программа>::= <Объявление переменных> <Описание вычислений>

<Описание вычислений>::= BEGIN <cписок присваиваний> END

<Объявление переменных>::= VAR <список переменных>: тип;

<Список переменных>::= <Идент>|<Идент>,<Список переменных>

<Список присваиваний>::= <Присваивание>|<Присваивание> <Список присваиваний>

<Присваивание>::= <Идент> = <Выражение>;

<Выражение>::= <Ун.оп.> <Подвыражение> | <Подвыражение>

<Подвыражение>::= (<Выражение>) | <Операнд> | <Подвыражение>

<Бин.оп.><Подвыражение>

<Ун.оп>::= вид

<Бин.оп.>::= вид

<Операнд>::= <Идент>|<Конст>

<Идент>::= <Буква><Идент>|<Буква>

<Конст>::= вид

Варианты заданий приведены в таблице 3.1.

Таблица 3.1

Примечания

1. <Буква> - буква латинского алфавита от A до Z;

<Цифра> - цифра от 0 до 9;

.NOT. - отрицание;

.AND. - коньюнкция;

.OR. - дизьюнкция;

.IMP. - импликация;

.EQU. - эквивалентность.

2. Таблицы истинности для логических операций эквивалентности и

импликации имеют следующий вид:

И - "истина", Л - "ложь".

3. Старшинство логических операций (по убыванию) имеет

следующий вид:

1) отрицание,

2) коньюнкция,

3) дизъюнкция,

4) импликация,

5) эквивалентность.

Старшинство арифметических операций (по убыванию) имеет

следующий вид:

1) унарный минус,

2) умножение, деление,

3) сложение, вычитание.

4. Цифрами обозначены следующие виды распознавателей:

1. Детерминированный нисходящий распознаватель (магазинный

автомат) для грамматики типа LL(1)

2. Детерминированный восходящий распознаватель (магазинный

автомат)

Курсовое проектирование

2.1 Задание на курсовое проектирование

С учетом дополнений для лабораторной работы № 3 разработать расширенный вариант транслятора, осуществить его программную реализацию и тестирование.

2.2 Варианты заданий

Дополнения к лабораторной работе № 3

для курсового проектирования по дисциплине

"Теория языков программирования и методы трансляции"

Примечания

1. Цифрами обозначены следующие операторы и их описание:

1. READ(<Список переменных>);

2. FOR <Идент>=<Выражение> TO <Выражение> DO

<Список присваиваний>

END_FOR;

3. REPEAT

<Список присваиваний>

UNTIL <Выражение>;

4. WHILE <Выражение> DO

<Список присваиваний>

END_WHILE;

5. IF <Выражение> THEN

<Список присваиваний>

ELSE

<Список присваиваний>

END_IF;

6. CASE <Выражение> OF

<Список выбора>

END_CASE;

<Список выбора>::=<Выбор>|<Выбор><Список выбора>

<Выбор>::=<Конст>:<Присваивание>

7. WRITE(<Список переменных>);

2.3 Методические указания к курсовому проектированию

Базой для выполнения курсового проектирования является лабораторная работа № 3 данного лабораторного практикума. Поэтому приводимые методические указания относятся по методологии и к лабораторной, и к курсовой работе.

Приведем основные указания для выполнения курсового проектирования.

1) Грамматику транслируемого языка, используемую в работе № 3, следует модифицировать и расширить соответствующими операторами дополнений для курсовой работы. Для удобства целесообразно терминальные и нетерминальные символы грамматики обозначить соответствующими буквами и составить таблицу соответствия символов и обозначений.

2) Расширенную грамматику необходимо преобразовать к нужному виду путем соответствующих действий.

Для нисходящего грамматического разбора для грамматики типа LL(1) требуется, по крайней мере, устранить прямую левую рекурсию и провести факторизацию.

Устранение прямой левой рекурсии (исключение самолеворекурсивности) заключается в преобразовании правил вида А®Аa|b₁|b₂|…|b_n в правила вида

А® b₁А’|b₂А’|…|b_nА’

А’®aА’|e

Факторизация (вынесение общей части) заключается в преобразовании правил вида А®ab₁|ab₂|…|ab_n в правила вида

А®a А’

А’® b₁ |b₂ |…|b_n

3) Следует разработать лексический анализатор, на вход которого подается исходный текст транслируемой программы, а на выходе которого формируется последовательность лексем. Кроме того лексический анализатор должен формировать таблицу символов (идентификаторов, констант) и выдавать сообщения об ошибках при их обнаружении.

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

5) В зависимости от формы транслятора: компилятор или интерпретатор- разрабатывается или генератор кода, или модуль интерпретации соответственно.

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

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

8) В случае, если разработка транслятора выполняется бригадой студентов (два-три человека), пояснительная записка оформляется отдельно на каждого студента. При этом в пояснительной записке приводится описание разработки всего транслятора, а в реферате и заключении указывается, в чем состоял личный вклад студента в общую разработку. Например, личный вклад может заключаться в выполнении следующих работ:

· разработка лексического анализатора;

· проектирование магазинного автомата;

· программная реализация синтаксического анализатора;

· разработка модуля интерпретации (генератора кода).

2.3.1 Разработка лексического анализатора

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

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

Может использоваться общая таблица сисмволов, в которой хранятся и переменные, и константы.

Лексема может описываться двумя основными признаками. Одним из них является принадлежность лексемы определенному классу (переменные, константы, операции и т. д.) Второй признак определяет конкретный элемент данного класса.

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

Просмотр таблицы идентификаторов выполняет две основные функции:

1) запись нового имени в таблицу при обработке описания переменных;

2) поиск имени, ранее записанного в таблицу.

Это позволяет выявлять такие ошибочные ситуации, как множественное описание переменной и наличие неописанной переменной.

Разработка лексического анализатора заключается частично в моделировании различных автоматов для распознавания идентификаторов, констант, зарезервированных слов и т. д. Если лексемы разного типа начинаются с одного и того же сисмвола или одной и той же последовательности символов, может оказаться необходимым объединение их распознавания.

2.3.2 Разработка синтаксического анализатора

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

Для нисходящего грамматического разбора для грамматики типа LL(1) после приведения ее к нужному виду требуется с использованием функций ПЕРВ и СЛЕД спроектировать магазинный автомат с подробным описанием всех переходов в рамках функции переходов.

Для восходящего грамматического разбора требуется с использованием функций ПЕРВ, СЛЕД и отношений ПОСЛЕ, СВЕРТ спроектировать магазинный автомат с подробным описанием всех переходов в рамках функции переходов, после чего при наличии конфликтов типа перенос-свертка устранить их соответствующим способом, а также при наличии одинаковых пар для отношения СВЕРТ использовать в магазинном автомате операцию опознания (по какому правилу свертка).

2.3.3 Разработка генератора кода или модуля интерпретации

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

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

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

Рассмотрим основные принципы формирования и выполнения постфиксной формы записи выражений.

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

1) унарный минус записывается как бинарная операция, т.е. вместо, например -В записывается 0-В;

2) для обозначения унарного минуса используется новый знак, например @;

3) унарный минус может определяться по контексту: он может стоять либо в начале выражения, либо сразу после открывающей скобки, например -х+а(-в+с)/(-d+f).

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

Считанные операнды добавляются к постфиксной записи, операции записываются в стек.

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

Считанная открывающая скобка заносится в стек.

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

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

Рассмотрим пример преобразования для следующей инфиксной записи:

A+B*C

Рассмотрим пример преобразования для следующей инфиксной записи:

(A+B)*C

Рассмотрим пример преобразования для следующей инфиксной записи:

-A*((-B+C)/D-F)

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

Если лексема является операндом, то она записывается в стек. Если лексема является операцией, то указанная операция выполняется над последними элементами (последним элементом), записанными в стек, и эти элементы (элемент) заменяются в стеке результатом операции.

3 Общие требования к курсовому проектированию

Курсовое проектирование может проводиться в форме выполнения либо курсового проекта, либо курсовой работы. Отличие курсового проекта от курсовой работы, помимо, в общем случае, большей сложности и объема, состоит в обязательном наличии графической части (чертежей, минимум – одного). В обоих случаях предусматривается обязательное оформление расчетно-пояснительной записки.

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

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

Ниже приведены правила присвоения квалификационного кода документа, размещаемого на титульном листе в строке обозначение курсового проекта (работы) (приложение А).

ПГУ 230105-10ДП961.01 ПЗ

Код организации-

разработчика

Код специальности

Номер семестра, в котором

выполняется проект или работа

Код вида проекта (работы)

ДП – дипломный проект

ДР – дипломная работа

КП – курсовой проект

КР – курсовая работа

Код группы (только цифры)

Номер варианта задания

Шифр документа

Для студента группы 00ВП1 с номером задания – 07 квалификационный код будет выглядеть следующим образом

ПГУ 230105-6КР001.07 ПЗ

3.1.2 Техническое задание

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

Оно подписывается руководителем, студентом и утверждается заведующим выпускающей кафедры.

Задание оформляется на специальном бланке (приложение Б).

Реферат

Реферат к курсовому проекту (работе), согласно ГОСТ 7.9-95 - сокращенное изложение содержания пояснительной записки с основными сведениями и выводами. Реферат должен содержать сведения:

- об объеме;

- количестве иллюстраций;

- количестве таблиц;

- количестве чертежей формата А4;

- количестве использованных источников.

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

Далее располагают текст реферата, который составляется по следующему плану:

- предмет (объект) исследования;

- цель работы;

- метод исследования и аппаратура;

- полученные результаты и их новизна;

- степень внедрения;

- эффективность;

- область применения;

- основные конструктивные и технико-эксплуатационные характеристики.

Если в пояснительной записке отсутствуют какие-либо части из перечисленных выше, то их опускают, сохраняя последовательность изложения.

Оптимальный объем реферата - 1200 знаков, но не более 2000 (примерно не более двух страниц формата А4).

Пример оформления реферата приведен в приложении В.

Содержание

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

Слово "Содержание" записывают в виде заголовка (симметрично тексту) с прописной буквы (приложение Г).

Введение

Введение должно состоять из двух частей.

В первой части рекомендуется обосновать актуальность темы курсового проекта (работы). В качестве обоснования могут быть приведены мотивы социально-общественного, политического, экономического и другого характера.

Во второй части приводится формулировка цели проекта (работы) и пути решения поставленной задачи.

Заключение

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

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

Приложения

В приложении могут быть приведены различные текстовые материалы, оформленные как самостоятельные документы, материалы вспомогательного характера, материалы графического характера В частности, в приложении приводятся распечатки с ЭВМ, которые должны соответствовать формату А4.

Имеются два варианта указания заголовка приложения.

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

Если материал приложения располагается со следующего после заголовка листа, то заголовок строится посредине листа в следующей последовательности: наименование, обозначение, тип (обязательное).

Графическая часть

Графическая часть отражает основные проектные решения курсового проекта. Она включает чертежи, выполненные в соответствии с ГОСТ 19.701-90 (приложение Л).

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

ЛИТЕРАТУРА

1. Князев В.Н., Шибанов С.В. Теория вычислительных процессов и структур. – Пенза, ПГТУ, 1996. – 20 с.

2. Белоусова В.В., Гурьянов Л.В., Князев В.Н., Линьков В.М., Ракова А.Н., Самуйлов С.В., Сивохин А.В. Дипломное проектирование для специальности 220400. – Пенза, ПГУ, 2001. – 89 с.

3. Белоусова В.В., Князев В.Н., Самуйлов С.В. Общие требования и правила оформления пояснительной записки курсовой работы. – Пенза, ПГТУ, 1992. – 36 с.

4. Компаниец Р.И., Маньков Е.В., Филатов Н.Е. Системное программирование. Основы построения трансляторов. – СПб.: КОРОНА принт, 2004. – 256 с.

5. Соколов А.П. Системы программирования. Теория, методы, алгоритмы. – М.: Финансы и статистика, 2004. – 320 с.

Познавательные статьи:



Как правильно слушать собеседника

Типичные ошибки при выполнении бросков в баскетболе

Принятие христианства на Руси и его значение

Средства массовой информации США