Методические указания к курсовой работе по дисциплине " системы программирования " Киев -2002




Скачать 116.76 Kb.
НазваниеМетодические указания к курсовой работе по дисциплине " системы программирования " Киев -2002
Дата публикации11.07.2013
Размер116.76 Kb.
ТипМетодические указания
lit-yaz.ru > Информатика > Методические указания
Министерство образования Украины
КИЕВСКИЙ ПОЛИТЕХНИЧЕСКИЙ ИНСТИТУТ
Кафедра прикладной математики
МЕТОДИЧЕСКИЕ УКАЗАНИЯ
к курсовой работе по дисциплине
" СИСТЕМЫ ПРОГРАММИРОВАНИЯ "


Киев -2002




1. ЦЕЛИ И ЗАДАЧИ КУРСОВОЙ РАБОТЫ

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

        Необходимо решить следующие задачи:

  • выбрать тему курсовой работы;

  • выбрать схему реализации компилятора;

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

  • выбрать представление для правил грамматики;

  • выбрать представление для синтаксического дерева вывода; атрибутного дерева (абстрактной программы) и промежуточного кода (ПОЛИЗ, тетрады, триады или косвенные триады);

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

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

  • определить набор программных компонент;

  • кодировать программную реализацию, разработать тестовые примеры и провести отладку;

Тема курсовой работы, которая должна включать:

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

  • применяемый метод синтаксического анализа;

  • код на выходе генератора промежуточного кода (ПОЛИЗ, тетрады, триады или косвенные триады).


Может быть выбрана однопроходная, двухпроходная и т.п схема реализации компилятора. Для класса методов синтаксического анализа с возвратами лучше выделить по меньшей мере две фазы – в конце 1-ой фазы получить синтаксическое дерево вывода (возможно представление дерева в линейной форме с применением скобочной записи или какое-либо другое представление, удобное для преобразования дерева в атрибутное), в процессе 2-ой фазы снабдить узлы дерева атрибутами, выполняя формирование таблицы символов (используя результаты лабораторной работы № 2) и в процессе прохождения дерева выполнять вызов генератора промежуточного кода; возможна и 3-я фаза, если отложить генерацию кода до момента окончательного формирования всех атрибутов для дерева вывода. Для класса методов синтаксического анализа без возвратов – лексический и синтаксический анализ, формирование атрибутов и генерацию кода желательно совместить , и это вполне возможно, поскольку анализатор работает детерминированно, заглядывая вперед на один-два символа по входной цепочке.

           Преобразования исходных правил грамматики должно выполнено быть таким образом, чтобы они были приспособлены для реализации синтаксического анализатора в соответствии с выбранным методом. Здесь возможно, что не все правила можно «подогнать» под общую схему; тогда в процессе кодирования правил их надо пометить, выделить в особую категорию, чтобы анализатор в необходимой ситуации включил эвристические процедуры. Например, для реализации выбран LL(1) анализатор, но полученная грамматика не LL(1). Тогда в некоторых ситуациях анализатор “заглядывает” вперед по входной цепочке, чтобы определить применяемое правило.

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

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

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

         Набор программных компонент может влючать в себя:

  • программы для работы с потоками ввода/вывода;

  • транслитератор;

  • собственно лексический анализатор, синтаксический анализатор;

  • генератор кода;

  • программа работы с таблицами символов;

  • программы диалогового взаимодействия.

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

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

^ 2. ТЕМАТИКА КУРСОВЫХ РАБОТ
Методы синтаксического анализа:

1.Нисходящий разбор с возвратами ( декларативное,        табличное представление правил грамматики).

2. Нисходящий разбор с возвратами (рекурсивный спуск).

    3. Восходящий разбор с возвратами.

4. Алгоритм Кока-Янгера-Касами.

5. Алгоритм Эрли.

6. LL(1)- анализатор.

7. LR(1)- анализатор.

8. Метод расширенного предшествования.

9. Метод ограниченного правого контекста.

10. Метод предшествования Колмерауэра.

11. Модификации основных алгоритмов.

При выборе пунктов 1,2 и 3 необходимо сразу указать процедурный или декларативный подход (в виде структур данных) правил грамматики.

Исходное подмножество языков программирования:
1. **Бейсик.                 8. Ада.

2. Паскаль.                  9. Common Lisp или Хlisp.

3. Модула.                 10.Java

4. Cи или С++.           11. JavaScript или JScript.

5. Фортран-|V.          12. VBScript.

6. Фортран-77.          13. Алгол-60.

7. Смолток-80.  

Другие ЯП по согласованию с преподавателем.

       **Для Бейсика необходимо дополнительно решить задачу «языкотворчества» и ввести в него конструкции для поддержки блочной структуры программы.
Результирующий код (выход генератора):


  1. Польская инверсная запись (ПОЛИЗ).

  2. Тетрады.

  3. Триады .

  4. Косвенные триады.

^ 3.ОФОРМЛЕНИЕ ПОЯСНИТЕЛЬНОЙ ЗАПИСКИ КУРСОВОЙ РАБОТЫ

3.1. Общие положения

Курсовая работа состоит из теоретической и практической частей. Объем и содержание каждой части определяется заданием по курсовой работе.

Курсовая работа снабжается титульным листом, форма которого приведена в Приложении 1.

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

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

Пояснительная записка должна содержать следующие разделы:

введение;

постановка задачи;

теоретические обоснования;

описание логической структуры программы ;

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

тестирование программы ;

выводы;

литература.

В качестве приложений должны быть представлены текст программы и тексты тестовых примеров.
3.2. Содержание разделов

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

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

В разделе "Теоретические обоснования " должны быть введены подразделы:

формализованное решение;

семантические процедуры;

структуры данных и спецификация функций.

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

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

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

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

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

В разделе "Генерация кода", связанном с разработкой генератора промежуточного кода‚ в раздел включается таблица команд промежуточного кода или тетрад, описание схем перевода для операторов или выражений с обоснованием почему так сделано, чтобы было понятно, что дальнейший перевод в машинные команды обеспечит реализацию семантики операторов. Формируемый код должен включать команды преобразования типов данных, если это требуется для вычисления выражений. Раздел должен содержать ссылки к Приложению с тестовыми примерами вида:" исходный текст программы - промежуточный код". С целью сокращения количества работы, связанной с программированием (чтобы не выполнять перевод промежуточного кода в символьное внутренне представление для демонстрации примеров) допустимо разработать и применить символьный формат для тетрад и триад. В этом случае, однако, необходимо сразу предусмотреть такой формат операндов, который бы позволил однозначно сопоставить операнды исходному коду.

Например, тетрада
^ "PLUSF; FN, 1, A; FN,_, T3;FN,_,T10"
представляет команду сложения данных типа float (PLUSF) и сформирована в результате трансляции тела функции FN. Описание переменной А размещалось в 1-ом блоке в теле этой функции, а переменные Т3, Т10 являются временными рабочими переменными и были сгенерированы компилятором. Такой код легко получить, поскольку абстрактная программа содержит все необходимые ссылки в таблицу символов за исключением может быть внутренних генерируемых меток .

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

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

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

ЛИТЕРАТУРА
1. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. Том 1. Синтаксический анализ. М, Мир, 1978.

2. Льюис Ф., Розенкранц Д., Стирна Р. Теоретические основы проектирования компиляторов. М, Мир, 1979.

3. Грис Д. Конструирование компиляторов для цифровых вычислительных машин. М, Мир, 1975.

4. Лебедев В.Н. Введение в системы проектирования. М, Статистика, 1975.

5. Касьянов В.Н., Потосин И.В. Методы построения трансляторов. Новосибирск, Наука, 1986.

Приложение 1. Титульный лист курсовой работы.

Министерство образования Украины

КИЕВСКИЙ ПОЛИТЕХНИЧЕСКИЙ ИНСТИТУТ
Кафедра прикладной математики


КУРСОВАЯ РАБОТА
по дисциплине " СИСТЕМЫ ПРОГРАММИРОВАНИЯ "

"Синтаксический анализатор для подмножества

языка______________________

  Метод синтаксического анализа:___________________

          Метод генерации промежуточного кода_____________

Выполнил(а)___________________

группа____факультет___________

N зачетной книжки____________

Руководитель__________________

Киев________ год

Добавить документ в свой блог или на сайт

Похожие:

Методические указания к курсовой работе по дисциплине \" системы программирования \" Киев -2002 iconМетодические указания к курсовому проекту по дисциплине «Технологии программирования»
Методические указания предназначены для студентов, обучающихся по специальности 220200 «Автоматизированные системы обработки информации...

Методические указания к курсовой работе по дисциплине \" системы программирования \" Киев -2002 iconМетодические указания по контрольно-курсовой работе по дисциплине эксплуатацияэвми систем
Методические указания по ккр составлены доц каф ЭВМ лебеденко Ю. И. и обсуждены на заседании кафедры ЭВМ факультета кибернетики

Методические указания к курсовой работе по дисциплине \" системы программирования \" Киев -2002 iconМетодические указания по анализу финансового 12 состояния организации 12
Методические указания предназначены для выполнения курсовых работ по дисциплине «Анализ хозяйственной деятельности» для студентов...

Методические указания к курсовой работе по дисциплине \" системы программирования \" Киев -2002 iconМетодические указания по выполнению курсовой работы по дисциплине «Финансы и кредит»
Методические указания по выполнению курсовой работы для студентов специальности

Методические указания к курсовой работе по дисциплине \" системы программирования \" Киев -2002 iconМетодические указания к выполнению курсовой работы (на примере создания...
В соответствии с учебным планом по дисциплине «Автоматизация технологических процессов и производств» студенты специальности 220301....

Методические указания к курсовой работе по дисциплине \" системы программирования \" Киев -2002 iconМетодические указания по курсовой работы для студентов заочной формы обучения
Методические указания предназначены для студентов очной и заочной формы обучения. Содержат рекомендации по написанию курсовой работы...

Методические указания к курсовой работе по дисциплине \" системы программирования \" Киев -2002 iconМетодические указания к лабораторным работам по дисциплине «Теория электрической связи»
Методические указания предназначены для студентов дневной формы обучения по специальности «Телекоммуникационные системы и сети»

Методические указания к курсовой работе по дисциплине \" системы программирования \" Киев -2002 iconПояснительная записка к курсовой работе по дисциплине «Технологии сетевого программирования»
Всю работу пользователь системы производит через Web-интерфейс. Web-интерфейс осуществляет взаимодействие с Session Beans, выполняющим...

Методические указания к курсовой работе по дисциплине \" системы программирования \" Киев -2002 iconМетодические указания к контрольной работе по дисциплине «Экономический...
Методические указания предназначены для обучающихся по специальности 051800 «Учет и аудит (по отраслям)»

Методические указания к курсовой работе по дисциплине \" системы программирования \" Киев -2002 iconКурсовой проект по дисциплине «Цифровые системы управления»
В контрольно-курсовой работе исследуется цсу, предназначенная для реализации заданного режима слежения, структура которой представлена...



Образовательный материал



При копировании материала укажите ссылку © 2013
контакты
lit-yaz.ru
главная страница