Формы Бэкуса - Наура ( БНФ )

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

Е.Н. Ишакова

РАЗРАБОТКА КОМПИЛЯТОРОВ

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

к курсовой работе

Рекомендовано к изданию Редакционно-издательским советом

государственного образовательного учреждения

высшего профессионального образования

“Оренбургский государственный университет”

Оренбург 2005

УДК 004.4¢422(075.8)

ББК 32.973.26-018.1я73

И 97

Рецензент

кандидат технических наук, доцент Бахарева Н.Ф.

Ишакова Е.Н.

И 97 Разработка компиляторов: Методические указания к курсовой работе. - Оренбург: ГОУ ОГУ, 2005. – 50 с.

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

Методические указания предназначены для выполнения курсовой работы по дисциплине «Теория языков программирования и методов трансляции» для студентов специальности 220400 – «Программное обеспечение вычислительной техники и автоматизированных систем».

Содержание

Введение.............................................................................................................. 4

1 Тема и цель курсовой работы......................................................................... 5

2 Основы теории разработки компиляторов..................................................... 5

2.1 Методы описания синтаксиса языка программирования............................ 5

2.2 Общая структура компилятора.................................................................. 13

2.3 Лексический анализатор программы......................................................... 14

2.4 Синтаксический анализатор программы.................................................. 19

2.5 Семантический анализатор программы..................................................... 24

2.6 Генерация внутреннего представления программы.................................. 29

2.7 Интерпретатор программы........................................................................ 32

3 Постановка задачи к курсовой работе.......................................................... 35

4 Требования к содержанию курсовой работы............................................... 36

5 Варианты индивидуальных заданий............................................................. 37

6 Контрольные вопросы для самопроверки.................................................... 42

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

Приложение А Пример оформления титульного листа курсовой работы.... 44

Приложение Б Правила присвоения классификационного кода.................... 45

Приложение В Пример оформления содержания курсовой работы............. 46

Приложение Г Пример оформления приложений курсовой работы............. 48

Введение

Предлагаемый материал посвящен основам классической теории компиляторов – одной из важнейших составных частей системного программного обеспечения.

Несмотря на более чем полувековую историю вычислительной техники, формально годом рождения теории компиляторов можно считать 1957, когда появился первый компилятор языка Фортран, созданный Бэкусом и дающий достаточно эффективный объектный код. До этого времени создание компиляторов было весьма «творческим» процессом. Лишь появление теории формальных языков и строгих математических моделей позволило перейти от «творчества» к «науке». Именно благодаря этому, стало возможным появление сотен новых языков программирования.

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

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

1 Тема и цель курсовой работы

Тема курсовой работы: «Разработка компилятора модельного языка программирования».

Цель курсовой работы:

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

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

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

2 Основы теории разработки компиляторов

2.1 Описание синтаксиса языка программирования

Существуют три основных метода описания синтаксиса языков программирования: формальные грамматики, формы Бэкуса-Наура и диаграммы Вирта.

Формальные грамматики

Определение 2.1. Формальной грамматикой называется четверка вида:

, (1.1)

где V _N - конечное множество нетерминальных символов грамматики (обычно прописные латинские буквы);

V _T - множество терминальных символов грамматики (обычно строчные латинские буквы, цифры, и т.п.), V _T ÇV _N = Æ;

Р – множество правил вывода грамматики, являющееся конечным подмножеством множества (V _T È V _N)⁺ ´ (V _T È V _N)^*; элемент (a , b) множества Р называется правилом вывода и записывается в виде a®b (читается: «из цепочки a выводится цепочка b»);

S – начальный символ грамматики, S ÎV_N.

Для записи правил вывода с одинаковыми левыми частями вида используется сокращенная форма записи .

Пример 2.1. Опишем с помощью формальных грамматик синтаксис паскалеподобного модельного языка М. Грамматика будет иметь правила вывода вида:

P ® program D2 B.

D2 ® var D1

D1 ® D | D1; D

D ® I1: int | I1: bool

I1 ® I | I1, I

B ® begin S1 end

S1 ® S | S1; S

S ® begin S1 end | if E then S else S | while E do S | read(I) | write(E)

E ® E1 | E1=E1 | E1>E1 | E1<E1

El ® T | T+E1 | T-E1 | TÚEl

T ® F | F*T | F/T | FÙT

F ® I | N | L | ØF | (E)

L ® true | false

I ® C | IC | IR

N ® R | NR

C ® a | b | c | d | e | f | g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v | w | x | y | z

R ® 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Диаграммы Вирта

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

При построении диаграмм учитывают следующие правила:

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

каждому правилу соответствует своя графическая диаграмма, на которой терминалы и нетерминалы соединяются посредством дуг;

альтернативы в правилах задаются ветвлением дуг, а итерации - их слиянием;

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

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

Пример 1.4. Описание синтаксиса модельного языка М с помощью диаграмм

Описание синтаксиса модельного языка М с помощью диаграмм Вирта представлено на рисунке 2.2.

цифра

Рисунок 2.2 – Синтаксические правила модельного языка М

Буква

Идентификатор

число

ключевое_слово

Рисунок 2.2 – Синтаксические правила модельного языка М, лист 2

Разделитель

программа

описание

тело

Рисунок 2.2 – Синтаксические правила модельного языка М, лист 3

Оператор

выражение

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

присваивания

условный

цикла

составной

ввода

вывода

Рисунок 2.2 – Синтаксические правила модельного языка М, лист 4

выражение

сумма

произведение

Операнд

логическая_константа

Рисунок 2.2 – Синтаксические правила модельного языка М, лист 5

Пример 2.4. Программа на модельном языке М, вычисляющая среднее арифметическое чисел, введенных с клавиатуры.

program

var k, n, sum: int;

begin

read(n);

sum:= 0;

i:=1;

while i<=n do

begin

read(k);

sum:=sum+k;

k:=k+1

end;

write(sum/n)

end.

2.2 Общая структура компилятора

Определение 2.2. Компилятор – это программа, которая осуществляет перевод исходной программы в эквивалентную ей объектную программу на языке машинных команд или языке ассемблере.

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

1) проверка исходной цепочки символов на принадлежность к входному языку;

2) генерация выходной цепочки символов на языке машинных команд или ассемблере.

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

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

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

лексический анализ;

синтаксический анализ;

семантический анализ;

подготовка к генерации кода;

генерация кода.

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

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

Общая схема работы компилятора представлена на рисунке 2.3.

Рисунок 2.3 – Общая схема работы компилятора

Обработка описаний

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

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

type

tabid = record

id :string;

descrid :byte;

typid :string[4];

addrid :word

end;

var

TI: array[1.. n] of tabid;

Таблица 2.1 – Таблица идентификаторов на этапе СеА

Номер	Идентификатор	Описан	Тип	Адрес
1	K	1	Int	…
2	Sum	0	…	…

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

При выполнении процедуры D вводится стековая переменная-массив, в которую заносится контрольное число 0. По мере успешного выполнения процедуры I в стек заносятся номера считываемых из файла лексем, под которыми они записаны в таблице идентификаторов. Как только при считывании лексем встречается лексема «:», из стека извлекаются записанные номера и по ним в таблице идентификаторов проставляется 1 в поле «описан» (к этому моменту там должен быть 0). Если очередная лексема будет «int» или «bool», то попутно в таблице идентификаторов поле «тип» заполняется соответствующим типом.

Пример 2.11. Пусть фрагмент описания на модельном языке имеет вид: var k, sum: int … Тогда соответствующий фрагмент файла лексем: (1, 2) (4, 1) (2, 3) (4, 2)…Содержимое стека при выполнении процедуры D представлено на рисунке 2.7.

Рисунок 2.7 – Содержимое стека при выполнении процедуры D

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

1) LEX – переменная, хранящая значение очередной лексемы, представляющая собой одномерный массив размером 2, т.е. для лексемы (n, k) LEX[1]=n , LEX[2]=k;

2) gl – процедура считывания очередной лексемы в переменную LEX;

3) inst(l) - процедура записи в стек числа l;

4) outst(l) – процедура вывод из стека числа l;

5) instl – процедура записи в стек номера, под которым лексема хранится в таблице идентификаторов, т.е. inst(LEX[2]);

6) dec(t) - процедура вывода всех чисел из стека и вызова процедуры decid(1, t);

7) decid(l, t) – процедура проверки и заполнения поля «описан» и «тип» таблицы идентификаторов для лексемы с номером l и типа t.

Процедуры dec и decid имеют вид:

procedure decid (l:..; t:...);

begin

if TI[l].descrid =1 then ERR

else begin

TI[l].descrid: = 1;

TI[l].typid:= t

end

end;

procedure dec(t: ...);

begin

outst(l);

while l<>0 do

begin

decid(l, t);

outst(l)

end

end;

Правило и процедура D с учетом семантических проверок принимает вид:

D ® <inst(0)> I <instl> {, I <instl> } : ( int <deс(‘int’)> | bool <dec(‘bool’)> )

procedure D;

begin

inst(0);

instl;

while EQ(‘,’) do

begin

gl; I; instl

end;

if EQ(‘:’) then gl else ERR;

if EQ(‘int’) then

begin

gl; dec(‘int’)

end

else

if EQ(‘bool’)

then

begin

gl; dec(‘bool’)

end

else ERR

end;

Анализ выражений

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

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

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

1) checkid - процедура, которая для лексемы LEX, являющейся идентификатором, проверяет по таблице идентификаторов TI, описан ли он, и, если описан, то помещает его тип в стек;

2) checkop – процедура, выводящая из стека типы операндов и знак операции, вызывающая процедуру gettype(op, t1, t2, t), проверяющая соответствие типов и записывающая в стек тип результата операции;

3) gettype(ор, t1, t2, t) – процедура, которая по таблице операций TOP для операции ор выдает тип t результата и типы t1, t2 операндов;

4) checknot – процедура проверки типа для одноместной операции «Ø».

Таблица 2.2 – Фрагмент таблицы двуместных операций TOP

Операция	Тип 1	Тип 2	Тип результата
+ > …	int int …	int int …	int bool …

Перечисленные процедуры имеют следующий вид:

procedure checkid;

begin

k:=LEX[2];

if TI[k].descrid = 0 then ERR;

inst(TI[k].typid)

end;

procedure checkop;

begin

outst(top2); outst(op); outst(top1);

gettype(op, t1, t2, t);

if (top1<>t1) or (top2<>t2) then ERR;

inst(t)

end;

procedure checknot;

begin

outst(t);

if t<> bool then ERR;

inst(t)

end;

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

Е ® Е1 {( > | < | = ) <instl> E1 <checkop>}

E1® Т {(+ | - | Ú) <instl> T <checkop>}

T® F {( * | / | Ù) <instl> F<checkop>}

F® I <checkid>| N<inst(‘int’)> | L <inst(‘bool’)>| ØF <checknot>|(E)

Пример 2.12. Дано выражение a+5*b. Дерево разбора выражения и динамика содержимого стека представлены на рисунке 2.8.

int

Рисунок 2.8 – Анализ выражения a +5* b

Перевод в ПОЛИЗ выражений

В ПОЛИЗе операнды записаны слева направо в порядке использования. Знаки операций следуют таким образом, что знаку операции непосредственно предшествуют его операнды.

Пример 2.13. Для выражения в обычной (инфиксной записи) a*(b+c)-(d-e)/f ПОЛИЗ будет иметь вид: abc +*de-f/-.

Справедливы следующие формальные определения.

Определение 2.5. Если Е является единственным операндом, то ПОЛИЗ выражения Е – это этот операнд.

Определение 2.6. ПОЛИЗ выражения Е₁q Е₂, где q - знак бинарной операции, Е₁ и Е₂ – операнды для q, является запись , где - ПОЛИЗ выражений Е₁ и Е₂соответственно.

Определение 2.7. ПОЛИЗ выражения qЕ, где q - знак унарной операции, а Е – операнд q, есть запись , где - ПОЛИЗ выражения Е.

Определение 2.8. ПОЛИЗ выражения (Е) есть ПОЛИЗ выражения Е.

Перевод в ПОЛИЗ операторов

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

Оператор присваивания I := E в ПОЛИЗе записывается:

I E :=,

где «:=» - двуместная операция,

I, E – операнды операции присваивания;

I – означает, что операндом операции «:=» является адрес переменной I, а не ее значение.

Пример 2.14. Оператор x:=x+9 в ПОЛИЗе имеет вид: x x 9 + :=.

Оператор перехода в терминах ПОЛИЗа означает, что процесс интерпретации необходимо продолжить с того элемента ПОЛИЗа, который указан как операнд операции перехода. Чтобы можно было ссылаться на элементы ПОЛИЗа, будем считать, что все они пронумерованы, начиная с единицы (например, последовательные элементы одномерного массива). Пусть ПОЛИЗ оператора, помеченного меткой L, начинается с номера p, тогда оператору безусловного перехода goto L в ПОЛИЗе будет соответствовать:

p!, где ! – операция выбора элемента ПОЛИЗа, номер которого равен p.

Условный оператор. Введем вспомогательную операцию – условный переход «по лжи» с семантикой if (not B) then goto L . Это двуместная операция с операндами B и L. Обозначим ее !F, тогда в ПОЛИЗе она будет записываться:

B p !F, где p – номер элемента, с которого начинается ПОЛИЗ оператора, помеченного меткой L.

С использованием введенной операции условный оператор if B then S₁ else S₂ в ПОЛИЗе будет записываться:

B p₁!F S₁p₂! S₂, где p₁ – номер элемента, с которого начинается ПОЛИЗ оператора S₂, а p₁– оператора, следующего за условным оператором.

Пример 2.15. ПОЛИЗ оператора if x>0 then x:=x+8 else x:=x-3 представлен в таблице 2.3.

Таблица 2.3 – ПОЛИЗ оператора if

лексема	x	0	>	13	!F	x	x	8	+	:=	18	!	x	x	3	-	:=	…
номер	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18

Оператор цикла. С учетом введенных операций оператор цикла while B do S в ПОЛИЗе будет записываться:

B p₁!F S p_o !, где p_o – номер элемента, с которого начинается ПОЛИЗ выражения B, а p₁– оператора, следующего за данным оператором цикла.

Операторы ввода и вывода языка М одноместные. Пусть R – обозначение операции ввода, а W – обозначение операции вывода, тогда оператор read(I) в ПОЛИЗе запишется как I R, а оператор write(E) – E W.

Составной оператор begin S₁; S₂;...; S_n end в ПОЛИЗе записывается как S₁ S₂... S_n.

Пример 2.16. ПОЛИЗ оператора while n>3 do begin write(n* n-1); n:=n-1 end представлен в таблице 2.4.

Таблица 2.4 – ПОЛИЗ оператора while

лексема	n	3	>	19	!F	n	n	*	1	-	W	n	n	1	-	:=	1	!	…
номер	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19

Интерпретатор программы

Запись программы в форме ПОЛИЗа удобна для последующей интерпретации (выполнения программы) с помощью стека. Массив ПОЛИЗа просматривается один раз слева направо, при этом:

1) если очередной элемент ПОЛИЗа является операндом, то его значение заносят в стек;

2) если очередной элемент – операция, то на «верхушке» стека находятся ее операнды, которые извлекаются из стека, над ними выполняется соответствующая операция, результат которой заносится в стек;

3) интерпретация продолжается до тех пор, пока не будет считана из ПОЛИЗа точка, стек при этом должен быть пуст.

Пример 2.18. Интерпретировать ПОЛИЗ программы, заданный таблицей 2.5 при введенном значении а равном 7.

Таблица 2.5 – ПОЛИЗ исходной программы

Лексема	a	r	a	5	>	17	!F	b	a	3	+
(n, k)	(5,1)	(2,20)	(4,1)	(3,1)	(2,16)	(0,17)	(2,19)	(5,1)	(4,1)	(3,2)	(2,8)
Номер	1	2	3	4	5	6	7	8	9	10	11

Продолжение таблицы 2.5 – ПОЛИЗ исходной программы

Лексема	:=	b	W	19	!	a	W	.
(n, k)	(2,5)	(4,1)	(2,21)	(0,19)	(2,18)	(4,1)	(2,21)	(2,1)
Номер	12	13	14	15	16	17	18	19

Процесс интерпретации программы на модельном языке М, записанной в форме ПОЛИЗа, показан в таблице 2.6.

Таблица 2.6 – Ход интерпретации ПОЛИЗа программы

Стек

Текущий элемент ПОЛИЗа

Операция

Таблицы

переменных

адреса

значения

пуст

адрес - в стек

1) a 2) b

1) - 2) -

извлечь из стека номер элемента таблицы значений и записать по нему число 7

1) a 2) b

1) 7 2) -

пуст

значение - в стек

1) a 2) b

1) 7 2) -

значение - в стек

1) a 2) b

1) 7 2) -

7; 5

в стек – true, т.к. 7>5

1) a 2) b

1) 7 2) -

true

метка - в стек

1) a 2) b

1) 7 2) -

true; 6

переход, к следующему элементу ПОЛИЗа, т.к. условие истинно

1) a 2) b

1) 7 2) -

пуст

адрес - в стек

1) a 2) b

1) 7 2) -

значение переменной - в стек

1) a 2) b

1) 7 2) -

2; 7

число - в стек

1) a 2) b

1) 7 2) -

2; 7; 3

извлечь из стека 3 и 7 и поместить в стек их сумму

1) a 2) b

1) 7 2) -

2; 10

присвоить второму элементу таблицы значений число 10

1) a 2) b

1) 7 2) 10

пуст

значение – в стек

1) a 2) b

1) 7 2) 10

вывести на экран число из «верхушки стека»

1) a 2) b

1) 7 2) 10

Продолжение таблицы 2.6 – Ход интерпретации ПОЛИЗа программы

Стек	Текущий элемент ПОЛИЗа	Операция	Таблицы переменных
Стек	Текущий элемент ПОЛИЗа	Операция	адреса	значения
пуст	15	метка – в стек	1) a 2) b	1) 7 2) 10
19	16	переход к элементу ПОЛИЗ с номером, извлекаемым из верхушки стека	1) a 2) b	1) 7 2) 10
пуст	19	интерпретация завершена	1) a 2) b	1) 7 2) 10

Пример 2.19. Построим интерпретатор ПОЛИЗа для языка М.

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

1) ad d r(1) – функция, выдающая адрес ячейки, отведенной для хранения лексемы l;

2) cont(А) – функция, выдающая содержимое ячейки с адресом А;

3) let(А, х) – процедура записи в ячейку с адресом А значения х;

4) inst(x) – процедура записи в стек значения х;

5) o u tst(x) – процедура считывания из стека значения х.

Тело интерпретатора ПОЛИЗа будет иметь следующий вид:

free:=1; {на начало P}

repeat

LEX:=P[free]; {очередная лексема}

n:=LEX[1]; k:=LEX[2];

case n of

0: inst(k); {метка - в стек}

5: inst(addr(LEX)); {адрес - в стек}

1,3,4: inst(cont(addr(LEX))); {значение - в стек}

2: {знак операции}

case k of

8{+}: begin outst(у); outst(x); inst(x+y) end;

9{-}: begin outst(у); outst(x); inst(x-y) end;

…{аналогично для *, / и других операций}

14{Ø}: begin outst(x); inst(not x) end;

5{:=} begin outst(x); outst(А); let(А, х) end;

18{!}: begin outst(free); free:=free-1 end;

19{!F}: begin

outst(free1); outst(B);

if B=false then free:=free1-1;

end;

20{R}: begin outst(A); read(x); let(А, х) end;

21{W}: begin outst(x); write(x) end

end

free:=free+1;

until (k=2) and (n=2).

Требования к содержанию курсовой работы

Курсовая работа должна иметь следующую структуру и состоять из разделов.

Введение

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

2 Формальная модель задачи

3 Спецификация основных процедур и функций

3.1 Лексический анализатор

3.2 Синтаксический анализатор

3.3 Семантический анализатор

3.4 Генерация внутреннего представления программы

3.5 Интерпретатор программы

4 Структурная организация данных

4.1 Спецификация входных данных

4.2 Спецификация выходных данных

5 Разработка алгоритма решения задачи

5.1 Укрупненная схема алгоритма программного средства

5.2 Детальная разработка алгоритмов отдельных подзадач

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

7 Работа с программным средством

Заключение

Список использованных источников

Приложение А – Текст программы

Приложение Б – Контрольный пример

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

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

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

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

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

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

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

Установка программного средства. Описываются все действия, необходимые для установки программного средства (ПС) на ПЭВМ. Также объем, занимаемый ПС на жестком магнитном диске, минимальный объем оперативной памяти, необходимый для его эксплуатации и другие технические характеристики оборудования.

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

Заключение. В заключении приводятся основные выводы и перспективы дальнейшего развития представленного ПС.

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

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

5 Индивидуальные варианты задания

Операции языка (первая цифра варианта) представлены в таблицах 5.1 – 5.4.

Таблица 5.1 - Операции группы «отношение»

Номер	Синтаксис группы операций (в порядке следования: неравно, равно, меньше, меньше или равно, больше, больше или равно)
1	<операции_группы_отношения>:: = < > \| = \| < \| <= \| > \| >=
2	<операции_группы_отношения>:: = != \| = = \| < \| <= \| > \| >=
3	<операции_группы_отношения>::= NE \| EQ \| LT \| LE \| GT \| GE

Таблица 5.2 - Операции группы «сложение»

Номер	Синтаксис группы операций (в порядке следования: сложение, вычитание, дизъюнкция)
1	<операции_группы_сложения>:: = + \| - \| or
2	<операции_группы_сложения>:: = + \| - \| \|\|
3	<операции_группы_сложения>:: = plus \| min \| or

Таблица 5.3 - Операции группы «умножение»

Номер	Синтаксис группы операций (в порядке следования: умножение, деление, конъюнкция)
1	<операции_группы_умножения>::= * \| / \| and
2	<операции_группы_умножения>:: = * \| / \| &&
3	<операции_группы_умножения>::= mult \| div \| and

Таблица 5.4 - Унарная операция

Номер	Синтаксис операции
1	<унарная_операция>::= not
2	<унарная_операция>::= !
3	<унарная_операция>::= ~

Выражения языка задаются правилами:

<выражение>::= <операнд>{<операции_группы_отношения> <операнд>}

<операнд>::= <слагаемое> {<операции_группы_сложения> <слагаемое>}

<слагаемое>::= <множитель> {<операции_группы_умножения> <множитель>}

<множитель>::= <идентификатор> | <число> | <логическая_константа> |

<унарная_операция> <множитель> | (<выражение>)

<число>::= <целое> | <действительное>

<логическая_константа>::= true | false

Приложение А

(обязательное)

Пример оформления титульного листа курсовой работы

Министерство образования и науки Российской Федерации

Федеральное агентство образования

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

“ОРЕНБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ”

Факультет информационных технологий

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

и автоматизированных систем

КУРСОВАЯ РАБОТА

(16 пт)

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

Разработка компилятора модельного языка

(16 пт)

Пояснительная записка

ГОУ ОГУ 220400.5404.13 ПЗ

Руководитель работы

_______________Ишакова Е.Н.

"____"______________2004г.

Исполнитель

студент гр. 01ПО1 _______________Ковальчук С.В.

"____"______________2004г.

Оренбург 2004

Примечание – Остальные надписи размером 14 пт.

Приложение Б

(обязательное)

Приложение В

(обязательное)

Пример оформления содержания курсовой работы

Содержание

Введение........................................................................................... 3

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

2 Формальная модель задачи.......................................................... 5

3 Спецификация основных процедур и функций........................... 8

3.1 Лексический анализатор............................................................ 8

3.2 Синтаксический анализатор...................................................... 9

3.3 Семантический анализатор...................................................... 10

3.4 Генерации внутреннего представления программы............... 11

3.5 Интерпретатор программы..................................................... 12

4 Структурная организация данных............................................. 13

4.1 Спецификация входной информации...................................... 13

4.2 Спецификация выходной информации................................... 14

5 Разработка алгоритма решения задачи..................................... 15

5.1 Укрупненная схема алгоритма программного средства........ 16

5.2 Детальная разработка алгоритмов отдельных подзадач....... 18

6 Установка и эксплуатация программного средства.................. 20

7 Работа с программным средством............................................. 21

Заключение..................................................................................... 24

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

Приложение А – Текст программы............................................... 26

Приложение Б – Контрольный пример........................................ 31

Алгоритм решения задачи

Укрупненная схема алгоритма программного средства представлена на рисунке 6.1.

Приложение Г

(обязательное)

Пример оформления приложений курсовой работы

Приложение А

(обязательное)

Контрольный пример

Результаты работы лексического анализатора представлены на рисунке А.1.

Рисунок А.1 – Выходные данные лексического анализатора

Приложение Б

(обязательное)

Текст программы

La.h

#include <grids.hpp>

#include <fstream.h>

#include <string.h>

#include <vector>

#include <string>

using std::string;

using std::vector;

// структура, описывающая лексему

struct par{

long n; // номер таблицы

long k; // номер в таблице

};

typedef vector<string> wordtable;

typedef vector<par> parvec;

// состояния диаграммы

enum states {SH, // начало

SI, // идентификатор

SN, // число (до точки)

SND, // дробная часть

SNS, // знак порядка

SNP, // порядок

SO, // ограничитель

SC, // комментарий

SL, // <

SG, // >

SS, // :

SDT, // .

SER, // ошибка

SV}; // выход

class LA;

// класс сканер

class Scanner{

public:

LA * A; // связанный лексический анализатор

string instr; // входная строка с исходным текстом

unsigned long pos; // позиция в строке

long z; // найденная позиция в таблице

long errcode; // код ошибки

char cur; // текущий символ

string S; // строка, формирующая лексему

states State; // состояние дмаграммы

int Scan(); // метод-сканер

char gc(){ // считывание следующего символа

if (pos >= instr.size()){

State = SV;

return cur;

}

return (cur = instr[pos++]);

}

bool letter(){ // проверка символа на букву

return isalpha(cur);

}

bool digit(){ // проверка символа на цифру

return isdigit(cur);

}

long look(wordtable * t); // поиск лексемы S в таблице t

long put(wordtable * t){ // помещение лексемы в таблицу

z = look(t);

if (z >= 0)

return z;

t->push_back(S);

return (z = (t->size() - 1));

}

void out(long n, long z);

};

// класс лексический анализатор

class LA{

public:

wordtable R; // таблица служебных слов

wordtable D; // таблица разделителей

wordtable I; // таблица идентификаторов

wordtable N; // таблица чисел

parvec res; // вектор пар чисел - результат лексического анализа

Scanner S; // сканер

void InTables(char *fname); // ввод таблиц R и D из файла

void OutTable(TStringGrid * G, wordtable * X); // вывод таблицы в StringGrid

int Scan(string s); // сканирование

string ErrorMsg(int code); // сообщение об ошибке по коду

string GetResult(); // сформировать результат в виде строки

void OutTables(char *fname); // вывод таблиц I и N в файл

void OutResult(char *fname); // вывод результата в файл

};

La.cpp

#include "la.h"

// перевод строки в нижний регистр

void tolower(string &s){

for (unsigned long i = 0; i < s.length(); i++)

s[i] = tolower(s[i]);

}

int Scanner::Scan(){

par t;

pos = 0;

State = SH;

errcode = 0;

gc();

while(State != SV && State != SER){

while(State != SV && cur != '\n' && isspace(cur))

gc();

if (State == SV)

break;

if (letter()){ // буква

State = SI;

S = cur;

for(gc(); State != SV && (letter() || digit()); gc())

S += cur;

//tolower(S);

look(&A->R);

if (z >= 0)

out(0, z);

else {

put(&A->I);

out(3, z);

}

} else if (digit()){ //число

State = SN;

S = cur;

for(gc(); State != SV && (digit() || strchr("ABCDEFabcdef", cur)); gc())

S += cur;

if (strchr("HhDdOoBb", cur)){

S += cur;

gc();

} else if (cur == '.'){ // дробная часть

State = SND;

S += cur;

for(gc(); State != SV && digit(); gc())

S += cur;

if (cur == 'e' || cur == 'E'){ // порядок

S += cur;

gc();

State = SNS;

if (cur == '+' || cur == '-'){

S += cur;

gc();

}

State = SNP;

for(; State != SV && digit(); gc())

S += cur;

}

} else if ((digit() || cur == '+' || cur == '-') && (S[S.length() - 1] == 'e' || S[S.length() - 1] == 'E')){ // порядок

State = SNP;

for(gc(); State != SV && digit(); gc())

S += cur;

}

put(&A->N);

out(2, z);

} else if (cur == '{'){ // комментарий

State = SC;

for(gc(); State != SV && cur != '}'; gc());

if (State == SV){

errcode = 1;

break;

}

gc();

} else if (cur == '<'){ // < <= <>

State = SL;

gc();

if (cur == '=' || cur == '>'){

S = "<";

S += cur;

gc();

}

else

S = "<";

look(&A->D);

out(1, z);

} else if (cur == '>'){ // > >=

State = SG;

gc();

if (cur == '='){

S = ">=";

gc();

}

else

S = ">";

look(&A->D);

out(1, z);

} else if (cur == ':'){ // : :=

State = SS;

gc();

if (cur == '='){

S = ":=";

gc();

}

else

S = ":";

look(&A->D);

out(1, z);

Е.Н. Ишакова

РАЗРАБОТКА КОМПИЛЯТОРОВ

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

к курсовой работе

Рекомендовано к изданию Редакционно-издательским советом

государственного образовательного учреждения

высшего профессионального образования

“Оренбургский государственный университет”

Оренбург 2005

УДК 004.4¢422(075.8)

ББК 32.973.26-018.1я73

И 97

Рецензент

кандидат технических наук, доцент Бахарева Н.Ф.

Ишакова Е.Н.

И 97 Разработка компиляторов: Методические указания к курсовой работе. - Оренбург: ГОУ ОГУ, 2005. – 50 с.