Logo GenDocs.ru

Поиск по сайту:  

Загрузка...

Алёшин А.В. Теория языков программирования и методы трансляции. Практикум - файл 1.doc


Алёшин А.В. Теория языков программирования и методы трансляции. Практикум
скачать (179 kb.)

Доступные файлы (1):

1.doc179kb.29.11.2011 20:54скачать

содержание
Загрузка...

1.doc

Реклама MarketGid:
Загрузка...
Министерство образования и науки Российской Федерации
АКАДЕМИЯ МАРКЕТИНГА

И СОЦИАЛЬНО-ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ

(ИМСИТ)

Кафедра компьютерных систем, управления

и обработки информации
ТЕОРИЯ ЯЗЫКОВ ПРОГРАММИРОВАНИЯ

И МЕТОДЫ ТРАНСЛЯЦИИ

Методические указания и варианты заданий

для выполнения практических занятий

для студентов очной формы обучения

специальности 220400 – Программное обеспечение ВТ и АС
КРАСНОДАР

2005
Составитель: ^ Алёшин А.В., кандидат технических наук, доцент
Теория языков программирования и методы трансляции. Методические указания и варианты заданий для выполнения практических занятий для студентов очной формы обучения специальности 220400 – Программное обеспечение ВТ и АС / Сост. Алёшин А.В. – Краснодар: ИМСИТ, 2005. – ... с.
Библиогр.: 18.
^

ПРАКТИЧЕСКАЯ РАБОТА 1 ЛЕКСИЧЕСКИЙ АНАЛИЗ



1.1 Цель и порядок выполнения работы



Цель занятия: изучение алгоритма работы лексического анализатора.

Порядок выполнения практической работы:

– прочитать описание работы;

– получить задание у преподавателя;

– в соответствии с заданным вариантом исходных данных разработать алгоритм сканера;

– составить, ввести и отладить программу, реализующую алгоритм сканера;

– составить тестовые наборы данных;

– получить листинги исходного модуля программы, входных данных и результатов работы;

– оформить отчет по практической работе.


^

1.2 Теоретические сведения



Лексический анализ включает в себя сканирование исходного текста программы и распознавание лексем, т.е. элементов, из которых строятся предложения языка, и замену их кодами лексем. Лексемой может быть ключевое слово, имя переменной, число и т.п. Программу, которая выполняет лексический анализ, называют лексическим анализатором или сканером. Точный перечень лексем, которые необходимо распознавать, зависит от языка программирования и от грамматики, используемой для его описания. Например, для языка PASCAL лексемами являются: PROGRAM, INTEGER, REAL, VAR, DO, READ и т.д. Каждый код лексемы обычно представляется кодом таблицы и спецификатором. Спецификатор задает номер строки в таблице, куда занесена лексема. Это позволяет избежать дополнительного поиска по таблицам на последующих этапах трансляции. Сканер работает с тремя таблицами: терминальных символов, символических имен и литералов.
Таблица терминальных символов в простейшем случае может иметь следующий вид:


№ строки

Терминальный символ

Признак разделителя

01

PROGRAM



02

VAR



03

BEGIN



04

END



05

INTEGER



06

FOR



07

TO



08

DO



09

WHILE



10

DIV



11

MOD



12

AND



13

OR



14

:=

+


Таблица символических имен может иметь следующий вид:

№ строки

Символическое имя

Адрес

Тип

Другая информация

01

I




int




02

Y




real




03

X1




real




04

...

...

...

...


Таблица литералов по структуре аналогична таблице символических имен:

№ строки

Литерал

Адрес

Тип

Другая информация

01

1




int




02

100




int




03

...

...

...

...


Результатом работы сканера является последовательность кодов лексем. Например, в результате обработки сканером следующего предложения языка Pascal
FOR I := 1 TO 100 DO Y := X1 ;
Будет получена строка:
<1,06><2,1><1,14><3,1><1,07><3,2><1,08><2,2><1,14><2,3>,
где в угловых скобках пара чисел задает код таблицы и спецификатор. В дополнение к своей основной функции – распознавание лексем – сканер также выполняет чтение строк и печать листинга исходной программы.

Функционально в сканере могут быть выделены следующие модули:

1. Выделение из входной строки очередного слова.

2. Поиск в таблицах лексем и определение кода лексемы.

3. Формирование и вывод выходной строки.

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

Для поиска в таблицах может быть использован как наиболее простой метод – линейный алгоритм.

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

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


^

1.3 Задание на практическую работу



В соответствие с заданным вариантом исходных данных разработать алгоритм сканера. Варианты исходных данных приведены в Таблице 1.1.
Таблица 1.1 Варианты исходных данных

№ варианта

Исходные данные

Ключевые слова

Служебные знаки

Другие лексемы

1

^ PROGRAM, INPUT, OUTPUT, VAR, INTEGER, BEGIN, IF, THEN, ELSE

«:», «,», «;», «:=», «<», «>», «(», «)»

идентификаторы с количеством символов не более 5


2

^ PROGRAM, INPUT, OUTPUT, VAR, INTEGER, BEGIN, FOR, TO, DO

«:», «,», «;», «:=», «.», «[», «]», «(», «)»

целые числа с количеством цифр не более 8

3

^ PROGRAM, INPUT, OUTPUT, VAR, END, BEGIN, WHILE, DO, CHAR

«:», «,», «;», «:=», «.», «=», «<>», «(», апостроф

символьные константы с количеством символов не более 10

4

^ PROGRAM, INPUT, OUTPUT, VAR, BOOLEAN, END,

BEGIN, AND, OR

«:», «,», «;», «:=», «.», «<=», «>=», «(», «)»

константы типа множество символов

5

^ MAIN, INT, REAL, STDIO, GET, PUT, PRINTF, FOR, DO, AND, OR

«:», «,», «;», «=», «.», «&», «!=», «{», «}», «+», «-»

символические имена с количеством символов не более 10

6

^ PROCEDURE, OPTIONS, MAIN, BINARY, FIXED, BEGIN, END, IF, THEN, ELSE

«:», «,», «;», «=», «.», «&», «<», «(», «)», «+», «-»

целые числа с количеством цифр не более 4

7

^ DIMENSION, ARRAY, REAL, INTEGER, CONTINUE, DO, IF, GOTO, COMMON

«:», «,», «;», «=», «.», «*», «/», «(», «)», «+», «-»

символические имена с количеством символов не более 4

8

^ COPY, TO, FIELDS, FOR, WHILE, ALL, REST, REPLACE, USE, IF, ENDIF

«:», «,», «;», «=», «.», «*», «/», «(», «)», «+», «-»"

символьные константы с количеством символов не более 25


^

1.4 Контрольные вопросы



1. Будет или нет уменьшение объема исходного текста программы в результате обработки его сканером?

2. Какой цели служит спецификатор лексемы?
^

ПРАКТИЧЕСКАЯ РАБОТА 2 СИНТАКСИЧЕСКИЙ АНАЛИЗ



2.1 Цель и порядок выполнения работы



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

Порядок выполнения практической работы:

  • на основе БНФ-определения составить синтаксическую диаграмму, а затем блок-схему алгоритма разбора;

  • дополнить программу лексического анализатора модулями, реализующими алгоритм разбора;

  • составить тестовые наборы данных;

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


^

2.2 Теоретические сведения



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

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

Например, определение идентификатора в БНФ имеет вид:
1.<идентификатор>::=<буква><продолжение идентификатора>

2. <продолжение идентификатора> ::= <буква><продолжение идентификатора> |

<цифра><продолжение идентификатора> |

<пусто>
Синтаксическая диаграмма для этого определения будет выглядеть, как показано на Рисунке 2.1.


Рисунок 2.1 Синтаксическая диаграмма идентификатора
Достоинством синтаксических диаграмм является наглядность и простота для понимания. Кроме того, от синтаксической диаграммы просто перейти к блок-схеме алгоритма грамматического разбора.

Для данного примера диаграммы блок-схема приведена на Рисунке 2.2. (указанные в блок-схеме подпрограммы вырабатывают признак U=True, если символ входной строки соответствует проверяемому понятию, и U=False – в противном случае). Подпрограммы «буква» и «цифра» выполняют соответственно проверку очередного символа входной строки на принадлежность множеству букв и цифр.

Общим недостатком формальных методов является отсутствие средств для задания смысловых правил синтаксиса языка. Примером такого вида правил является требование, чтобы все объекты в PASCAL-программе были описаны. Однако при переходе к алгоритмическому заданию синтаксиса (например, в виде блок-схемы) эта трудность преодолима. Пусть в рассмотренном примере требуется, чтобы количество символов в идентификаторе не превышало 5. Если обозначить счетчик символов как COUNT, то можно изменить приведенную на Рисунке 2.2 блок-схему так, как показано на Рисунке 2.3.



Рисунок 2.2 Блок-схема алгоритма контроля понятия «идентификатор»



Рисунок 2.3 Учет количественных ограничений


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


^

2.3 Задание на практическую работу



Составить определение заданного понятия в БНФ. Варианты исходных данных приведены в Таблице 2.1.

Таблица 2.1 Варианты исходных данных


варианта

Исходные данные

1

Подмножество языка Pascal. Допускается:

– в описаниях – переменные целого типа;

– в операторной части – оператор присваивания

и оператор IF ... THEN.

2

Подмножество языка Pascal. Допускается:

– в описаниях – переменные целого типа;

– в операторной части – оператор присваивания и

оператор FOR.

3

Подмножество языка Pascal. Допускается:

– в описаниях – переменные целого типа;

– в операторной части – оператор присваивания и

оператор WHILE.

4

Подмножество языка Pascal. Допускается:

– в описаниях – переменные целого типа;

– в операторной части – оператор присваивания,

в правой части которого несколько соотношений

соединяются знаками логических операций.

5

Подмножество языка Pascal. Допускается:

– в описаниях – переменные целого типа;

– в операторной части – оператор присваивания и

оператор REPEAT.

6

Подмножество языка Pascal. Допускается:

– в описаниях – переменные целого типа;

– в операторной части – оператор присваивания и

оператор CASE.

7

Подмножество языка Pascal. Допускается:

– в описаниях – переменные целого типа;

– в операторной части – оператор присваивания с

арифметическим выражением над целыми переменными.

8

Подмножество языка Pascal. Допускается:

- в описаниях - переменные и массивы вещественного

типа;

- в операторной части - оператор присваивания с

выражением над вещественными переменными;


^

2.4 Контрольные вопросы



1. Перечислите достоинства и недостатки синтаксических диаграмм.

2. В чем преимущества алгоритмического задания синтаксиса языков по сравнению с БНФ?

^

ПРАКТИЧЕСКАЯ РАБОТА 3 ПРОЕКТИРОВАНИЕ СИНТАКСИЧЕСКОГО АНАЛИЗАТОРА



3.1 Цель и порядок выполнения работы



Цель занятия: Получение практических навыков по проектированию синтаксических блоков компиляторов.
^ Порядок выполнения практической работы:

– прочитать описание работы;

– получить задание у преподавателя;

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

– составить, ввести и отладить программу, реализующую алгоритм синтаксического анализатора;

– составить тестовые наборы данных (позитивные и негативные);

– получить листинги исходного модуля программы, входных данных и результатов работы;

– оформить отчет по практической работе.


^

3.2 Теоретические сведения



Теоретические основы разработки формальных грамматик, построения и программной реализации автоматов с магазинной памятью рассмотрены в главах 3, 4, 5, 8 и 9 конспекта лекций по данной дисциплине.


^

3.3 Задание на практическую работу



Вариант индивидуального задания складывается из заданий по практической работе №№ 1 и 2, а также приведенных ниже требований.
Общие требования к синтаксическому блоку:

1. Операции: "+", "-", "/", "*" ("<",">","=","<=",">=","and", "or" – дополнительно по желанию).

2. Операторы: присваивания (обязательно для всех вариантов), условия и цикла (по варианту).

3. Для ввода данных и вывода результатов обязательно реализовать соответствующие функции (операторы), например, "read" и "write".

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

На входе – программа на выбранном языке, разработанная в соответствии с правилами грамматики.

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

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


^

3.4 Порядок защиты практической работы



Практическая работа сдается в два этапа:

Первый этап – преподавателю предоставляется формальная грамматика, записанная в РБНФ. Дополнительно можно представить графическое представление в форме диаграмм Вирта.

Грамматика имеет два вида: пользовательский и преобразованная для реализации грамматика. В последней грамматике для каждого правила должно быть определено множество «ВЫБОР» (Множество входных символов, для которых может быть применимо правило).

^ Второй этап – программная реализация автомата с магазинной памятью, функционирующего по разработанной формальной грамматике.

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


^

3.5 Содержание отчета по практической работе



1. Постановка задачи:

– формулировка задачи (ограничения реализуемого подмножества языка Паскаль);

– формальная грамматика пользователя;

– формальная грамматика разбора (атрибуты и множество выбора).

2. Описание реализации:

– описание выбора метода решения;

– описание структуры блока синтаксического анализа;

– алгоритмы функционирования компонент (блоков) анализатора.

3. Обработка ошибок.

4. Выводы.


^

3.6 Дополнительные возможности, оцениваемые при защите практической работы



1. Наличие семантического разбора (атрибутная грамматика).

2. Наличие построенных диаграмм Вирта.

3. Наличие дополнительных логических функций ("or", "and" и так далее) и смешанных выражение арифметических и логических выражений.

4. Наличие процедур и функций.

5. Удобный интерфейс для представления результатов синтаксического разбора (можно использовать log-файл).

6. Эффективные сообщения об ошибках.

^

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ



1. Пратт Т., Зелковиц М. Языки программирования: разработка и реализация / Под общей ред. А. Матросова. – СПб.: Питер, 2002. – 688 с.: ил.

2. Серебряников В.А. Теория и реализация языков программирования. – М.: МЗ-Пресс, 2003.

3. Альфред В. Ахо, Рави Сети, Джеффри Д. Ульман. Компиляторы: принципы, технологии и инструментарий. – М.: Вильямс, 2001.

4. Системное программирование. Основы построения трансляторов. Учебное пособие. – М.: КОРОНА-принт, 2001.

5. Кауфман В. Ш. Языки программирования. Концепции и принципы. - М.: Радио и связь, 1993. - 432 с.

6. Льюис Ф., Розенкранц Д., Стринз Р. Теоретические основы проектирования компиляторов. - М.: Мир, 1979.

7. Маккиман У. Генератор Компиляторов. - М.: Статистика, 1980.

8. Рейоурд-Смит В.Дж. Теория формальных языков. Вводный курс. - М.: Радио и связь, 1988.

9. Фостер Дж. Автоматический синтаксический анализ. - М.: Мир, 1975.

10. Дейкстра Э. Дисциплина программирования. М.: Мир, 1978.

11. Шишмарев А.И., Заморин А.П. Англо-русско-немецко-французский толковый словарь по вычислительной технике. М.: Издательство «Русский язык», 1978.

12. Браун П. Макропроцессоры и мобильность программного обеспечения. - М.: Мир, 1977.

13. Легалов А.И. Процедурно-параметрическая парадигма программирования. Возможна ли альтернатива объектно-ориентированному стилю? - Красноярск: 2000. Деп. рук. № 622-В00 Деп. в ВИНИТИ 13.03.2000. - 43 с.

14. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. - М.: Мир, 1978.

15. Грис Д. Наука программирования. М.: Мир, 1984.

16. Льюис Ф., Розенкранц Д., Стринз Р. Теоретические основы проектирования компиляторов. - М.: Мир, 1979.

17. Легалов А.И. Основы разработки трансляторов. Конспект лекций.

18. Вайнгартен Ф. Трансляция языков программирования. - М.: Мир, 1977.

СОДЕРЖАНИЕ



^ ПРАКТИЧЕСКАЯ РАБОТА 1 ЛЕКСИЧЕСКИЙ АНАЛИЗ 3

1.1 Цель и порядок выполнения работы 3

1.2 Теоретические сведения 3

1.3 Задание на практическую работу 5

1.4 Контрольные вопросы 7

^ ПРАКТИЧЕСКАЯ РАБОТА 2 СИНТАКСИЧЕСКИЙ АНАЛИЗ 8

2.1 Цель и порядок выполнения работы 8

2.2 Теоретические сведения 8

2.3 Задание на практическую работу 12

2.4 Контрольные вопросы 14

^ ПРАКТИЧЕСКАЯ РАБОТА 3 ПРОЕКТИРОВАНИЕ СИНТАКСИЧЕСКОГО АНАЛИЗАТОРА 15

3.1 Цель и порядок выполнения работы 15

3.2 Теоретические сведения 15

3.3 Задание на практическую работу 15

3.4 Порядок защиты практической работы 16

3.5 Содержание отчета по практической работе 16

3.6 Дополнительные возможности, оцениваемые при защите практической работы 17

^ СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ 18


ТЕОРИЯ ЯЗЫКОВ ПРОГРАММИРОВАНИЯ

И МЕТОДЫ ТРАНСЛЯЦИИ
Методические указания и варианты заданий для выполнения практических занятий для студентов очной формы обучения специальности 220400 – Программное обеспечение ВТ и АС
Алёшин Александр Владимирович


Скачать файл (179 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации