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




НазваниеМетодические указания предназначены для выполнения курсовой работы по дисциплине «Теория языков программирования и методов трансляции»
страница1/9
Дата22.01.2013
Размер0.63 Mb.
ТипМетодические указания
  1   2   3   4   5   6   7   8   9


МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ


ФЕДЕРАЛЬНОЕ АГЕНТСТВО ОБРАЗОВАНИЯ


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

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

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


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

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


Е.Н. Ишакова


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


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

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


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

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

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

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


Оренбург 2005








УДК 004.4422(075.8)

ББК 32.973.26-018.1я73

И 97


Рецензент

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


Ишакова Е.Н.

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


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

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

И


1404000000

6Л9-04


ББК 32.937.26-018.1я73






© Ишакова Е.Н., 2005

© ГОУ ОГУ, 2005









Содержание


Введение 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)


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

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

Р – множество правил вывода грамматики, являющееся конечным подмножеством множества (VT VN)+ (VT VN)*; элемент (, ) множества Р называется правилом вывода и записывается в виде (читается: «из цепочки выводится цепочка »);

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


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


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


Pprogram D2 B.

D2  var D1

D1  D | D1; D

DI1: int | I1: bool

I1  I | I1, I

Bbegin S1 end

S1  S | S1; S

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

EE1 | E1=E1 | E1>E1 | E1<E1

El  T | T+E1 | T-E1 | TEl

TF | F*T | F/T | FT

FI | N | L | F | (E)

Ltrue | false

IC | IC | IR

NR | NR

Ca | 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.2. Определение понятия «идентификатор» с использованием БНФ имеет вид:


<идентификатор> ::= <буква> | <идентификатор> <буква>

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

<буква> :: = 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

<цифра> :: = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9


Расширенные формы Бэкуса-Наура (РБНФ)


Для повышения удобства и компактности описаний, в РБНФ вводятся следующие дополнительные конструкции (метасимволы):

  • квадратные скобки «[» и «]» означают, что заключенная в них синтаксическая конструкция может отсутствовать;

  • фигурные скобки «{» и «}» означают повторение заключенной в них синтаксической конструкции ноль или более раз;

  • сочетание фигурных скобок и косой черты «{/» и «/}» используется для обозначения повторения один и более раз;

  • круглые скобки «(» и «)» используются для ограничения альтернативных конструкций.

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


<буква> ::= 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

<цифра> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

<идентификатор> ::= <буква> { <буква> | <цифра> }

<число> ::= {/< цифра> /}

<ключевое_слово> ::= program | var | begin | end | int | bool | read | write | if |

then | else | while | do | true | false

<разделитель> ::= ( | ) | , | ; | : | := | . | { | } |+ | - | * | / |  |  |  | = | < | >

<программа> ::= program <описание> ; <тело>.

<описание> ::= var <идентификатор> {, <идентификатор>}: (int | bool)

<тело> ::= begin {<оператор>; } end

<оператор> ::= <присваивания> | <условный> | <цикла> | <составной> |

<ввода> | <вывода>

<присваивания> ::= <идентификатор> := <выражение>

<условный> ::= if <выражение> then <оператор> else <оператор>

<цикла> ::= while <выражение> do <оператор>

<составной>:: = begin {<оператор> ;} end

<ввода>:: = read(<идентификатор>)

<вывода>:: = write(<выражение>)

<выражение>:: = <сумма> | <сумма> ( = | < | >) <сумма>

<сумма> ::= <произведение> { (+ | - | ) <произведение>}

<произведение>:: = <множитель> { (* | / | ) <множитель>}

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

 <множитель> | (<выражение>)

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


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


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

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

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

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

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

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

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




1) 2) 3)





1) – терминальный символ, принадлежащий алфавиту языка;

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

3) – нетерминальный символ, определяющий название правила;

4) – входная дуга с именем правила, определяющая его название;

5) – соединительные линии, обеспечивающие связь между терминальными и нетерминальными символами в правилах.

Рисунок 2.1 – Графические примитивы диаграмм Вирта


блок


4)

5)

блок

Пример 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.
  1   2   3   4   5   6   7   8   9

Похожие:

Методические указания предназначены для выполнения курсовой работы по дисциплине «Теория языков программирования и методов трансляции» iconПояснительная записка к курсовой работе по дисциплине «Теория языков программирования и методов трансляции»
Представление основных операторов(описанных в разделе семантики) с помощью тетрад 35
Методические указания предназначены для выполнения курсовой работы по дисциплине «Теория языков программирования и методов трансляции» iconМетодические указания к курсовой работе по дисциплине «Гидравлика»
Методические указания предназначены в помощь студентам при выполнении курсовой работы. В них изложены все необходимые сведения для...
Методические указания предназначены для выполнения курсовой работы по дисциплине «Теория языков программирования и методов трансляции» iconМетодические указания к курсовой работе по дисциплине «Насосы и насосные станции»
Методические указания предназначены в помощь студентам при выполнении курсовой работы. В них изложены все необходимые сведения для...
Методические указания предназначены для выполнения курсовой работы по дисциплине «Теория языков программирования и методов трансляции» iconМетодические указания по выполнению лабораторных работ по дисциплине "Теория языков программирования и методы трансляции"
Целью работы является получение практических навыков по составлению правил грамматики и проверка их правильности путём моделирования...
Методические указания предназначены для выполнения курсовой работы по дисциплине «Теория языков программирования и методов трансляции» iconМетодические указания к выполнению курсовой работы по дисциплине «Теория автоматов»
Методические указания предназначены для оказания практической помощи студентам, синтезирующим в курсовой работе на языках дискретной...
Методические указания предназначены для выполнения курсовой работы по дисциплине «Теория языков программирования и методов трансляции» iconМетодические указания по написанию курсовой работы по дисциплине «Теория менеджмента»
Методические указания предназначены для студентов, изучающих курс теория менеджмента и выполняющих, согласно учебному плану, курсовую...
Методические указания предназначены для выполнения курсовой работы по дисциплине «Теория языков программирования и методов трансляции» iconМетодические указания к выполнению курсовой работы по дисциплине «Экологический мониторинг»
Методические указания предназначены для выполнения курсовых работ по дисциплине «Экологический мониторинг» студентами, обучающимися...
Методические указания предназначены для выполнения курсовой работы по дисциплине «Теория языков программирования и методов трансляции» iconМетодические указания для выполнения курсовой работы по дисциплине «Макроэкономика»
Методические указания для выполнения курсовой работы по дисциплине «Макроэкономика» / Академия труда и социальных отношений. Курган,...
Методические указания предназначены для выполнения курсовой работы по дисциплине «Теория языков программирования и методов трансляции» iconУчебно-методическое пособие по выполнению курсовой работы по дисциплине «Основы инженерного менеджмента»
Методические указания предназначены для изучения элементов проектирования новой продукции, в рамках выполнения курсовой работы по...
Методические указания предназначены для выполнения курсовой работы по дисциплине «Теория языков программирования и методов трансляции» iconМетодические указания по курсу «Языки программирования и методы трансляции» для студентов 1 и 2 курсов дневного и вечернего отделений
Методические указания предназначены для студентов, изучающих курс «Языки программирования и методы трансляции», и преподавателей,...
Разместите кнопку на своём сайте:
Библиотека


База данных защищена авторским правом ©lib.znate.ru 2014
обратиться к администрации
Библиотека
Главная страница