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


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


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

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

(Технический университет)

Кафедра “Информационные технологии

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

ЛИНГВИСТИЧЕСКОЕ ОБЕСПЕЧЕНИЕ САПР
Методические указания к курсовой работе

Москва 2003

Составитель: проф., канд. техн. наук Л.В. Зайцева


доц., канд. техн. наук Э.С. Клышинский
Предназначены для изучения теории и основ проектирования компиляторов с использованием средств автоматизации. Приводятся спецификации на генераторы лексических анализаторов (LEX) и компиляторов (YACC). Предлагаются варианты заданий на курсовое проектирование.

Могут использоваться студентами специальностей 22.03.00 – 22.03.04 Из направления 654600 – «Информатика и вычислительная техника».


УДК 517.95


Лингвистическое обеспечение САПР: Метод. указания к курсовой работе/ Моск. гос. ин-т электроники и математики; Сост.: Л.В. Зайцева, Э.С. Клышинский. М., 2003. 29 с.

Ил. 6. Библиогр.: 5 назв.

ISBN 5-904506-025-9

Оглавление



1. Введение

4

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

4

3. Сканер

10

4. LR(k)-грамматики

15

5. Метод разбора рекурсивным спуском

21

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

23

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

25


1. Введение

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

Предлагаемая курсовая работа выполняется в рамках курса «Лингвистическое обеспечение САПР» в течение одного семестра бригадами студентов по 2 человека. В течение первого месяца выполнения курсовой работы студенты должны согласовать с преподавателем выбранный ими вариант.

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

Различают следующие виды трансляторов:

  • ассемблеры – переводят напрямую инструкции ассемблера в машинные коды;

  • макроассемблеры – вид ассемблеров, позволяющий делать макровставки в код программы на ассемблере;

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

  • препроцессоры – переводят надмножество команд в команды языка высокого уровня или опции компилятора;

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

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

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

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

Наиболее общим видом транслятора является компилятор. Задачей компилятора является перевод программы на исходном языке в объектный код. Структура компилятора представлена на рис. 1.

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

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

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

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

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

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

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

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

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

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

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

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

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

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


lexpr

token

attributes

“sort”

id

type = int

“a”

const

value = 5

“readarray”

id

type = double

“i”

id

type = int







^ Массив строк фиксированной длины

attributes
















name



















sort

EOS

a

EOS

readarray

EOS

i

EOS

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

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

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

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

Суть хеш-метода состоит в следующем. Для хранения наборов входных строк используется массив из m блоков. К входной строке применяется некоторая функция h(s), возвращающая значение, принадлежащее интервалу [0,m-1]. Далее входная строка направляется в блок с номером, равным h(s). При поиске строки s необходимо просмотреть блок с номером h(s), а при добавлении – поместить в этот блок. За счет этого скорость линейного поиска увеличивается в m раз, причем значение m можно выбирать самостоятельно.

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

Вместо списочной структуры хранения информации может использоваться массив фиксированной длины. В этом случае в хеш-таблице заводится еще один блок, называемый блоком переполнения. Блок переполнения хранит записи, не умещающиеся в основном блоке. В этом случае строка s ищется сначала в блоке, соответствующем функции h(s), а затем, если блок заполнен полностью, в блоке переполнения.



^ Рис. 3. Вариант хранения данных в хеш-таблице
Примером хеш-функции для строк может служить остаток от деления суммы символов или кода первого (последнего) символа в строке на количество блоков. Однако такие функции будут давать одинаковые результаты для имен, состоящих из одних и тех же символов в первом случае (tar, rat), и одинаково начинающихся имен (base1,base2) во втором.

Критерием оптимальности выбора m и алгоритма хеширования, заложенного в функцию h(s), является равномерное распределение строк по блокам. Если оценка равномерности близка к 1, то хеш-функция и m выбраны удачно. Если оценка близка к 0, то остается много пустого места, а если оценка много больше 1, то распределение строк по блокам далеко от равномерного.

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

#define PRIME m

#define EOS ‘\0’
int hashpjw(char *s)

{char *p;

unsigned int h=0,g;
for(p=s;*p!=EOS;p++)

{h=(h<<4)+(*p);

if(g=h&0xf0000000)

{h=h^(g>>24);

h=h^g;

}

}

return h%PRIME;

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

Похожие:

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


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