Федеральное государственное автономное образовательное учреждение высшего профессионального образования «Уральский федеральный университет имени первого Президента России Б.Н.Ельцина»

Кафедра информационных технологий и автоматизации проектирования

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

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

Рекомендована Методическим Советом ФГАОУ ВПО УрФУ

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

Екатеринбург

2012

1. Общие положения

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

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

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

2. Задание на курсовую работу

2.1. Задача 1. Минимизация конечного автомата

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

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

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

Например, при вводе строки 2+2*2 в результате мы получает ответ 8. При вводе ошибочного выражения получает сообщение об ошибке с позицией ошибочного символа.

2.2. Задача 2. Разработка модели интерпретатора

на основе модели языка

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

• Объявление переменных списком с возможностью инициализации;

• Присваивание переменной выражения;

• Ввод значения переменной с клавиатуры;

• Вывод значения переменной на экран.

Индивидуальные задания по согласованию с преподавателем могут включать:

• Оператор цикла while или for;

• Оператор условия if;

• Оператор Switch и др.

Допускается объявление переменных трех типов:

• integer – целый;

• float – с плавающей точкой;

• string – текстовая строка.

Решение данной задачи состоит из двух частей: создание лексического и синтаксического блоков. Задача лексического блока состоит в преобразовании входного потока символов программы в поток лексем. Каждая лексема представляет собой пару (класс;значение). Где класс означает тип лексемы:

k – ключевое слово

v – идентификатор

c – константа

, ; + – * / – разделители

Для работы МП-автомата можно использовать следующую структуру данных:

Таблица переменных			Стек имен	Стек значений
Имя	Тип	Значение		Тип	Значение

Синтаксический блок необходимо реализовать с использованием МП-автомата и LL(1)-грамматики. За основу для создания требуемой грамматики можно взять следующее множество правил.

Правило Множество выбора

P –> D k

P –> I₄ v

D –>k I₁ k

I1 –>I I₂ v

I2 –>, I1 ,

I2 –> ε ; =

I4 –> I₃ v

I –> v {объявить}I₃ v

I3 –> = E{присвоить} =

I3 –> ε , ;

E –> T X + – v c ( ^

X –> + T{+} X +

X –> – T {–}X –

X –> ε , ; ) ^

T –> F Y + – v c ( ^

Y –> * F {*}Y *

Y –> / F {/}Y /

Y –> S ^

Y –> ε + – ) , ;

S –> S ^ F ^

S –> ε

F –> + F{– –} +

F –> – F{++} –

F –> v {зн.перем.} v

F –> c c

F –> ( E ) (

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

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

Алгоритм обработки управляющих символов:

{+}: Вытащить из стека значений N2;

Вытащить из стека значений N1;

Сравнить типы;

Поместить в стек N1 + N2;

{–}: Вытащить из стека значений N2;

Вытащить из стека значений N1;

Сравнить типы;

Поместить в стек N1 – N2;

{*}: Вытащить из стека значений N2;

Вытащить из стека значений N1;

Сравнить типы;

Поместить в стек N1 * N2;

{/}: Вытащить из стека значений N2;

Вытащить из стека значений N1;

Сравнить типы;

Поместить в стек N1 / N2;

{зн.перем.}: Pop имя, тип переменной из стека имен;

Найти имя переменной в таблице переменных;

Если не найдено, то ошибка "Имя не определено";

Push Значение переменной, тип в стек значений;

{присвоить}: Pop имя, тип переменной из стека имен;

Найти имя переменной в таблице переменных;

Если не найдено, то ошибка "Переменная не определена";

В таблице переменных поменять значение;

{Объявить}: Найти имя переменной в таблице переменных;

Если не найдено

Push имя переменной в таблицу переменных;

Push имя переменной в стек имен;

Иначе

Ошибка "Переменная уже определена".

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

Те если к integer прибавляется float, то тип возвращаемого значения будет float. Присваивание переменной типа integerзначение типа float запрещено.

Обработка ошибок:

1. Если во время работы текущий символ не совпадает с терминальным символом наверху автомата, выдать "ОШИБКА, ожидается abcd", где abcd – список терминалов.

2. Если наверху нетерминал А и нельзя применить ни одно правило, выдать "ОШИБКА, ожидается или X или Y или Z", где X,Y, Z – множество выбора правил с А в качестве правой части.