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


Скачать 330.98 Kb.
НазваниеМетодические указания к курсовой работе
страница3/3
Дата публикации19.05.2013
Размер330.98 Kb.
ТипМетодические указания
userdocs.ru > Информатика > Методические указания
1   2   3

^ Рис. 7. Работа программы LR-разбора

Для начальной конфигурации (T0, aabb, e) будет выполнен следующий разбор.

(T0, aabb, e) (T0S T1, aabb, 2) (T0S T1a T2, abb, 2) (T0S T1a T2S T3, abb, 22) 

(T0S T1a T2S T3aT4, bb, 22) (T0S T1a T2S T3aT4ST6, bb, 222) 

(T0S T1a T2S T3aT4ST6bT7, b, 222) (T0S T1a T2S T3, b, 2221) 

(T0S T1a T2S T3bT5, e, 2221) (T0S T1, e, 22211)
Bison

Bison – это генератор программ грамматического разбора для LR(1)-грамматик. Bison является программой, совместимой сверху вниз с программой YACC, то есть все грамматики, написанные для YACC, могут быть перенесены в среду Bison.

Bison может работать с контекстно-свободными грамматиками вида LALR(1). LALR(1) – это особый вид LR(1)-грамматик, позволяющий описывать более широкий класс задач. Это достигается за счет «заглядывания» вперед на один символ. То есть на каждом шаге просматривается не только текущий символ, но и следующий за ним.

На вход программы Bison поступает грамматика, заданная в определенном формате. На выходе генерируется код на языке C, для которого определена функция yyparse(), выполняющая собственно грамматический разбор и производящая некоторые другие действия. На вход сгенерированной программы подается поток лексем, сгенерированный, например, в ходе работы функции yylex (лексического анализатора, полученного в результате работы flex’а).

В целом грамматика bison описывается следующим образом.

%{

Определения C

%}
Определения Bison
%%

Правила грамматики

%%

Дополнительный код на C

В любом месте файла описания грамматики может быть вставлен комментарий, заключенный в /* … */.

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

Определения Bison позволяют задавать имена токенов при помощи ключевого слова %token. К токенам можно привязывать некоторые строковые константы. Токену также можно присвоить некоторое целочисленное значение, которое будет использоваться анализатором для простоты обращения к токену. Тип токена можно определить, используя поля из структур, определенных ключевым словом %union.

%union { /* define stack type */

double val;

symrec *tptr;

}

%token NUM /* define token NUM and its type */

%token OR "||"

%token LE 134 "<="

Кроме того, токены могут быть заданы с использованием ключевых слов %left, %right и %noassoc. При этом будет задан порядок разбора структур вида x op y op z. Если y определен как %left, то для разбора будет взята последовательность x op y, а потом добавлено z. Если y определен как %right, то для разбора будет взята последовательность y op z, а потом добавлено x. Если токен определен как %noassoc, то подобная конструкция вызовет ошибку.

Для нетерминальных символов также может задаваться тип определением вида

%type <type> nonterminal

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

Терминальный символ error является зарезервированным для восстановления информации после ошибок.

Правило грамматики bison записывается следующим образом.

name : rule_component1

| rule_component2



;

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

expseq: /* empty */

| expseq1

;

expseq1: exp

| expseq1 ',' exp

;

К каждой компоненте правила может быть привязан некоторый код на языке C, который заключается в фигурные скобки. Кроме объявленных переменных могут использоваться так называемые семантические значения, привязанные к токенам. Например, при выполнении арифметических действий токенам приписываются некоторые значения. Именно над ними, а не над токенами необходимо производить эти арифметические действия. Результат вычисления выражения записывается как $$, а семантическое значение токена как $n. Здесь n – номер символа в правиле, причем нумерация начинается с 1.

exp: ...

| exp '+' exp { $$ = $1 + $3; }

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

Если не определено никакое действие, Bison производит операцию $$=$1.

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

%union {

int itype;

double dtype;

}



exp: ...

| exp '+' exp { $$ = $1 + $3; }

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

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

yylval.itype=value;

Для обработки ошибок к дополнительном коде на C должна быть определена функция yyerror(char *).

Функция обработки входного текста, определяемая самим программистом, может прекратить свою работу с использованием одного из следующих макросов:

- YYABORT – прекращается разбор и порождается ошибка;

- YYACCEPT – разбор принимается;

- YYEMPTY – пустое значение;

- YYERROR – запускается восстановление после ошибки.

Также могут использоваться следующие функции:

- yyclearin – удаляет текущий символ (удобна при обработке ошибок);

- yyerrok – прекращает состояние ошибки.

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

Документация на программы Lex, Flex, YACC и Bison и сами программы широко представлена в сети Internet (например, на сервере www.gnu.org). Кроме описанных здесь программ генерации компиляторов, работающих с языком C, существуют программы, генерирующие код на языках C++, Pascal, Java (см., например, www.experimentalstuff.com/Technologies/JavaCC/).
^ 5. Метод разбора рекурсивным спуском

В ряде случаев более удобным представляется написание собственной программы синтаксического разбора, без использования программ генерации компиляторов (LEX, YACC и т.д.). Одним из вариантов в этом случае является написание транслятора методом рекурсивного спуска. Метод применим для контекстно-свободных грамматик. Перед началом работы с контекстно-свободной грамматикой полезно произвести над ней следующие преобразования.
^ 1) Избавление от противоречий

stmtif expr then stmt | if expr then stmt else stmt | other

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

if E1 then if E2 then S1 else S2

Грамматику необходимо переписать в следующем виде

stmtmatched_stmt | unmatched_stmt

matched_stmtif expr then matched_stmt else matched_stmt | other

unmatched_stmtif expr then stmt | if expr then matched_stmt else unmatched_stmt
2) Избавление от левой рекурсии

Производится для нисходящего разбора. Грамматика является леворекурсивной если  AVN : A+A, для некоторой строки . Пример преобразования.



E E+T|T

T T*F|F

F (E)|id



E TE’

E’ +TE’|e

TFT’

T’*FT’|e

F (E)|id


Для преобразования используется следующий метод. Правила грамматики вида

^ AA1| A2|…| Am|1|2|…|n

преобразуется в следующий набор правил:

A1A’|2A’|…|nA’

A’ 1A’|2A’|…|mA’

^ 3) Левая факторизация

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

stmtif expr then stmt | if expr then stmt else stmt | other

преобразуется в

stmt st2 else stmt | st2| other

st2if expr then stmt

Для подобного преобразования A1| 2|…| n заменяют на

AA’|

A’1|2|…|n
Кроме того, при преобразовании грамматики рекомендуется избавиться от e-цепочек.

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

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

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

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


bool E()

{

if(!T())

return false;

E2();// Результат не зависит от наличия E2

return true;

}
bool E2()

{

if(lexem("+"))

{

if(!T())

return false;

E2();

return true

}

else

return false;

}
bool T()

{

if(!F())

return false;

T2();// Результат не зависит от наличия T2

return true;

}
bool T2()

{

if(lexem("*"))

{

if(!F())

return false;

T2();

return true

}

else

return false;

}
bool F()

{

if(lexem("("))

{

if(E() && lexem(")")

return true;

else

return flase;

}

else

if(lexem("("))

return true;

else

return flase;

}

^ 6. Варианты заданий

1. Конвертер с одного языка высокого уровня на другой. Перевод может осуществляться с любого существующего или разработанного студентами языка высокого уровня на другой. При этом язык, с которого осуществляется перевод, должен обладать следующей функциональностью: арифметические действия, условные операторы единственного и множественного выборов, циклы трех видов, объявление производных типов – структур и классов – с описанием зон видимости методов и свойств, поддержкой конструктора (конструкторов) и деструктора, объявление переменных базовых или производных типов, объявление функций, описание функций, в то числе и методов классов, диагностика синтаксических ошибок.

2. ^ Программа диагностики ошибок. Программа обнаруживает в тексте программы на выбранном языке как синтаксические, так и семантические ошибки (не менее 30 ошибок каждого вида). Списки различных ошибок можно найти на сервере www.gimpel.com.

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

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

5. ^ Интерпретатор программ на языке высокого уровня. Интерпретатор обеспечивает возможность производить выполнение программы, написанной на выбранном языке высокого уровня. При этом язык должен отвечать требованиям, указанным в п. 1, за исключением работы с классами.

6. ^ Интерпретатор файлов в заданном формате. В данном задании необходимо написать программу, осуществляющую интерпретацию некоторых файлов, записанных в определенном формате. Это может быть отображение документов, сохраненных в формате PostScript, PCL, отображение рисунков. Грамматика, описывающая входной файл, должна содержать не менее 40 правил. Возможна интерпретация нескольких входных форматов.

7. ^ Компилятор языка высокого уровня в объектный код. Результатом выполнения данного задания является программа, переводящая текст программы высокого уровня в некоторый объектный код. В качестве объектного кода может быть выбран язык ассемблера (не обязательно на уровне машинных кодов) или некоторый промежуточный код, разработанный самостоятельно, ускоряющий последующую интерпретацию кода. Входной язык должен отвечать требованиям, указанным в п. 1.

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

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

10. Иное задание. По согласованию с преподавателем студенты могут выбрать иное задание.

^ 7. Рекомендуемая литература

1. Ахо А., Ульман Д., Сети Р. Компиляторы: принципы, технологии, инструменты / М.: Вильямс, 2001.

2. Гридин: Теоретические основы проектирования адаптируемых компонентов САПР РЭА.

3. Грис Д. Конструирование компиляторов для ЦЭВМ / М.: Мир, 1975.

4. Тэрри: Компиляторы и генераторы компиляторов.

5. Хантер Р. Проектирование и конструирование компиляторов / М.: ФиС, 1984.
Учебное издание
Лингвистическое обеспечение САПР

Составители:

ЗАЙЦЕВА Лариса Викторовна

КЛЫШИНСКИЙ Эдуард Станиславович

Редактор С.П. Клышинская

Технический редактор О.Г. Завьялова
http://www.miem.edu.ru/rio/

rio@miem.edu.ru

Подписано в печать . .03. Формат 60х84/16.

Бумага типографская № 2. Печать - ризография.

Усл.печ. л. 1,81 Уч.-изд. л. 1,63 Тираж 50 экз.

Заказ . Бесплатно Изд № .

Московский государственный институт электроники и математики

109028 Москва, Б. Трехсвятительский пер., 3/12.

Отдел оперативной полиграфии Московского государственного института электроники и математики.

113054 Москва, ул. М. Пионерская, 12.


1   2   3

Похожие:

Методические указания к курсовой работе iconМетодические указания к курсовой работе по дисциплине «Статистика»
Методические указания к курсовой работе по дисциплине «Статистика» / Сост. Т. И. Мазаева, Н. Н. Скитер, Е. Е. Смотрова, О. А. Донскова;...
Методические указания к курсовой работе iconМетодические указания знакомят студентов с организационной стороной...
Методические указания по выполнению курсовой работы предназначены для студентов 1 курса, обучающихся по специальности 270802 «Строительство...
Методические указания к курсовой работе iconМетодические указания знакомят студентов с организационной стороной...
Методические указания по выполнению курсовой работы предназначены для студентов 4 курса, обучающихся по специальности 270802 «Строительство...
Методические указания к курсовой работе iconМетодические указания к курсовой работе Цель курсовой работы
Целью курсовой работы является закрепление и углубление знаний, полученных при изучении дисциплины в ходе лекционных и практических...
Методические указания к курсовой работе iconМетодические указания к курсовой работе опд. Ф. 07 «маркетинг»
Федеральное государственное образовательное учреждение высшего профессионального образования
Методические указания к курсовой работе iconА. В. Огородников 24 декабря 1993 г
Методические указания по курсовой работе для студентов, обучающихся по специальности «Лесное и садово-парковое хозяйство»
Методические указания к курсовой работе iconМетодические указания по написанию, оформлению и защите курсовой работы
Методические указания по выполнению курсовых работ по экономической теории (для студентов экономических факультетов)
Методические указания к курсовой работе iconМетодические указания по выполнению курсовой работы по дисциплине «Экономика организации»
Приведены методические указания по выполнению курсовой работы по дисциплине «Экономика организации» для учащихся дневной формы обучения...
Методические указания к курсовой работе iconМетодические указания к курсовой работе по дисциплине «Бухгалтерский учёт, анализ и аудит»
К. В. Батенин, канд эконом наук, доцент кафедры «Экономика и менеджмент» хти – филиала кгту
Методические указания к курсовой работе iconМетодические указания по выполнению курсовой работы студентами экономического...
Медведева Т. Н. Налоги и налогообложение. Методические указания по выполнению курсовой работы студентами экономического факультета....
Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2015
контакты
userdocs.ru
Главная страница