Ишакова Е.Н. Разработка компиляторов - Методические указания к курсовой работе

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

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

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

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

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

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

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

Е.Н. Ишакова

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

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

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

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

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

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

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

Оренбург 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)

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

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

Р – множество правил вывода грамматики, являющееся конечным подмножеством множества (V_T V_N)⁺  (V_T V_N)^*; элемент (, ) множества Р называется правилом вывода и записывается в виде  (читается: «из цепочки  выводится цепочка  »);

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.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