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




Скачать 303.6 Kb.
НазваниеЛабораторная работа выполняется в дисплейном классе. Результат представляет собой работающую программу, которая может анализировать любые тексты и сообщать об ошибках программирования
страница1/3
Дата24.09.2012
Размер303.6 Kb.
ТипЛабораторная работа
  1   2   3

Лабораторные работы по дисциплине
«Теория вычислительных процессов и структур»


Лабораторная работа №1

Построение детерминированного синтаксического анализатора.

1. Введение.

Данная лабораторная работа рассчитана на 4 аудиторных часа и ещё 4 часа самостоятельной работы для изучения литературы и оформление отчёта.

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

Метод построения синтаксического анализатора основывается на применении грамматик типа LL(1), что позволяет решить задачу, используя детерминированный алгоритм.

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


2. Содержание работы.

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

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

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

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

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

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

Две буквы L означают, что цепочка символов разбирается слева направо, и используются самые левые продукции. Цифра 1 означает, что варианты порождающих продукций выбираются с помощью одного предварительно просмотренного символа. Эта терминология была впервые предложена Кнутом. Если КС-грамматика не является грамматикой типа LL(1), то её нужно привести к этому типу.

LL(1) грамматика допускает детерминированный разбор предложений языка, описываемого этой грамматикой. Если эта грамматика задана, то магазинный автомат строится по известному правилу [1], а построенный автомат позволяет запрограммировать процесс синтаксического анализа, действуя формально, что и предопределяет решение задачи.

3. Задание по работе.

1. Вариант задания к данной лабораторной работе совпадает с вариантом задания к 1 лабораторной работе.

2. Построить КС-грамматику и проверить является ли она грамматикой типа LL(1).

3. Привести грамматику к типу LL(1).

4. По правилу [1] построить магазинный распознаватель, реализующий детерминированный разбор. Составить управляющую таблицу автомата.

5. Составить техническое задание на разработку программы синтаксического анализатора.

6. Запрограммировать работу синтаксического анализатора.

7. Представить два контрольных примера.

8. Составить отчёт по работе.

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

Язык программирования описывается КС-грамматикой. Детерминированный синтаксический анализ требует, чтобы КС-грамматика отвечала определённым требованиям. Во-первых, необходимо привести её, т.е. грамматика не должна содержать циклы, (-продукции, бесполезные и недостижимые символы, левые рекурсии.

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

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

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

А®А , для А ( N.

АЛГОРИТМ УСТРАНЕНИЯ НЕДОСТИЖИМЫХ.

Пусть дана КС-грамматика G={N,T,P,S}. Построим КС-грамматику G'={N', T', P', S} без недостижимых символов. Метод состоит в следующем:

1. Положим множество V={S} и i=1.

2. Положим множество Vi = Vi-1({A®((( ( P и A ( Vi-1 }.

3. Если Vi ( Vi-1, то i=i=1 и перейти к шагу 2. В противном случае

N'= N ( Vi , T'=T(Vi. Искомое множество продукций Р' состоит

из множества продукций Р, содержащих символы из множества Vi

АЛГОРИТМ УСТРАНЕНИЯ БЕСПОЛЕЗНЫХ СИМВОЛОВ.

Пусть дана КС-грамматика G={N,T,P,S}. Построим эквивалентную грамматику G'={N', T', P', S} без бесполезных символов. Метод состоит в следующем:

1. Положим N0=(, i=1.

2. Положим множество Ni=Ni-1({A | A®(((, ((((i-1(()(}.

3. Если Ni(Ni-1, положим i=i+1 и перейти к шагу 2. В противном случае положим N0=Ni.

4. Положим G1={N0( N,T,P',S}, где P'(P состоит из продукций множества Р, содержащих символы из N0((.

5. Применив к G1 алгоритм устранения в грамматике недостижимых символов, получим G'={N', T', P', S}.

АЛГОРИТМ ПРЕОБРАЗОВАНИЯ ГРАММАТИКИ В ГРАММАТИКУ БЕЗ (-ПРОДУКЦИЙ.

Пусть дана КС-грамматика G={N,T,P,S}. Построим (-свободную грамматику G', эквивалентную грамматике G. Метод состоит в следующем.

1. Применяем шаги 1-3 алгоритма устранения бесполезных символов, определяем множество N0={ A | A((, A®(}.

2. Множество P' строим следующим образом. Если продукция A®(0B1(1B2(2...Bk(k ((, где k ( ( и Bi ((0, но ни один символ в цепочках (j (0( j ( k) не принадлежит N0, добавим к Р' продукции вида A®(0(1(1(2(2...(k(k, где Xi есть или Bi или (, не включая в P' продукцию A®(.

Если S((0, то включим в P' продукцию вида S'®( | S, где S' новый нетерминальный символ и положим N'=N(S', в противном случае N'=N, S'=S.

3. Положим G'={N',T', P', S'}.

АЛГОРИТМ УСТРАНЕНИЯ ЦЕПНЫХ ПРОДУКЦИЙ.

Пусть нам дана (-свободная КС-грамматика G={N,T,P,S}. Получим эквивалентную КС-грамматику G'={N', T', P', S'} свободную от цепных и (-продукций.

Метод состоит в следующем.

1. Для каждого A(( построим множество NA={B | A®(((} нетерминальных символов, выводимых из А следующим образом:

1.1. Положим N0={A} и i=1;

1.2. Положим Ni={C | B®C(( и В((i-1} ( (i-1;

1.3. Если Ni ( (i-1, то положим i=i+1 и повторим шаг 1.2. В противном случае положим NA=N.

2. Построим множество P': если (В®()(( и не является цепной продукцией, то включим в P' продукцию A®(, для всех таких А, что В((А.

3. Положим G={N, T, P',S}.

Данный алгоритм позволяет устранить из грамматики и циклы, т.е. выводы А®(*, где А((.

УСТРАНЕНИЕ В КС-ГРАММАТИКЕ ЛЕВОЙ РЕКУРСИИ.

Алгоритмы синтаксического анализа легче строить тогда, когда КС-грамматика G не обладает свойствами леворекурсивности, т.е. в ней нет продукций вида X®((. Это особенно важно при использовании методов разбора сверху вниз и слева направо. Выбор продукции из множества альтернативных в этих методах базируется на сравнении порождённого крайнего левого символа промежуточной цепочки с текущим символом входной терминальной цепочки. При появлении же в выводе левой рекурсии произойдёт зацикливание. Поэтому при использовании алгоритмов нисходящего разбора левую рекурсию необходимо удалить.

В общем случае левая рекурсия в КС-грамматике может быть явной, когда есть продукции вида A®(( или неявной- когда в грамматике есть взаимно рекурсивные продукции вида:

A®((|...

B®((|...

Устранение леворекурсивных правил. Пусть G КС-грамматика, в которой есть леворекурсивные правила. Эквивалентная грамматика G' получается путём замены множества леворекурсивных правил грамматики G на множество правил вида:

A®(1('|(2('| ... |(n('

A'®(1('|(2('| ... |(n(|(

Здесь А'- новый вспомогательный нетерминальный символ.

ДЕТЕРМИНИРОВАННЫЙ СИНТАКСИЧЕСКИЙ АНАЛИЗ СВЕРХУ ВНИЗ

В данном синтаксическом анализе используются LL(1) грамматики, которые являются обобщением S-грамматик.

КС-грамматика называется S-грамматикой, если выполняются условия:

-правая часть каждой продукции начинается терминальным символом;

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

Для заданной S-грамматики магазинный автомат ( МП-распознаватель) с одним состоянием задаётся следующим образом:

1. А=Т({|-}

2. Г=N({t | t(( и (А®t()((}({(}.

3. Q={q}.

4. z0={#S | S- аксиома}.

5. q0=q.

6. Каждой продукции КС-грамматики сопоставляется элемент управляющей таблицы МП-распознавателя. Если продукция имеет вид A®t(, где A(( и t((, а (({(((}(, то этому правилу в строке А и в столбце t будут соответствовать операции

ЗАМЕНИТЬ ((r), СДВИГ

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

Если продукция имеет вид А®t, то строке А и столбцу t соответствуют операции

ЧТЕНИЕ, СДВИГ.

Если магазинным символом является терминал b, то элементом таблицы в строке b будет

ЧТЕНИЕ, СДВИГ.

Элементом таблицы, который находится в строке маркера дна магазина # и концевого маркера |-, является

ДОПУСТИТЬ.

Все остальные элементы таблицы заполняются операцией

ОТВЕРГНУТЬ.

где: А- символы, записанные на входной ленте;

Г- символы, записанные в магазинную память;

Q- множество состояний автомата;

z0- начальная запись в магазин;

q0-начальное состояние автомата.

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

Определим ПЕРВ(() как множество терминальных символов, которые являются первыми символами цепочек, выводимых из (.

Цепочка ( называется аннулирующей, если (®(.

Продукция грамматики вида А®( также называется аннулирующим.

ВЫБОР (А®()= ПЕРВ((),

если ( - не аннулирующая, и

ВЫБОР(А®()=ПЕРВ(()(СЛЕД(А),

если (- аннулирующая цепочка. При этом СЛЕД(А) - множество следующих за А терминалов в промежуточной цепочке, выводимой из S|-, где S-аксиома грамматики.

Для того, чтобы КС-грамматика была типа LL(1), необходимо, чтобы множества выбора для правил с одинаковыми левыми частями не пересекались, т.е. не имели общих терминальных символов.

Если для вашей грамматики это так, то она будет относится к типу LL(1) и для неё автомат строится по следующему правилу.

ПРАВИЛА ОПРЕДЕЛЕНИЯ ДЕТЕРМИНИРОВАННОГО

МП-РАСПОЗНАВАТЕЛЯ ПО LL(1) ГРАММАТИКЕ.

Для заданной LL(1) грамматики МП-распознаватель задаётся следующим образом:

1. А=Т({|-};

2. Г=N({t | t(( и (А®t()((, (((, (({(((}(}({(};

3. Q={q};

4. z0={#S};

5. q0=q;

6. Управление описывается управляющей таблицей с одним состоянием, строки помечены магазинными символами из Г, столбцы - входными символами из А. Элемент таблицы создаётся для каждой продукции. Если продукция имеет вид А®t(, то этому правилу в строке А и столбце t будут соответствовать операции

ЗАМЕНИТЬ((r), СДВИГ,

где (r - цепочка (, записанная в обратном порядке для того, чтобы удовлетворить соглашению "верхний символ справа"

Если продукция имеет вид А®(, где (=Х( и Х((, (({(((}*, то ему в строке А и во всех столбцах, принадлежащих множеству ВЫБОР (А®(), будет соответствовать переход

ЗАМЕНИТЬ ((r), ДЕРЖАТЬ.

Когда (=(, вместо ЗАМЕНИТЬ(() можно использовать ЧТЕНИЕ.

Если продукция имеет вид А®t, то ей в строке А и в столбце t соответствует операция

ЧТЕНИЕ. СДВИГ.

7. Если магазинным символом является терминал b, то элементом таблицы в строке b будет

ЧТЕНИЕ. СДВИГ.

8. Элементом таблицы, который находится в строке маркера дна # и столбце концевого маркера |-, является

ДОПУСТИТЬ.

9. Все остальные элементы таблицы заполняются операцией

ОТВЕРГНУТЬ.

5. Содержание отчёта.

Отчёт составляется каждым студентом и содержит развёрнутые ответы на все пункты задания. К отчёту прилагается таблица переходов МП-распознавателя и работающая программа МП-распознавателя.

6. Контрольные вопросы.

1. Как определяется КС-грамматика?

2. Как определяется нормальная форма Хомского?

3. Как задаётся нормальная форма Грейбах?

4. Как исключить (-продукции?

5. Как устранить недосигаемые символы?

6. Как устранить бесполезные символы?

7. Как устраняются циклические связи в продукциях?

8. Как устранить левые рекурсии в грамматике?

9. Как определяется магазинный автомат?

10. Как определяется LL(1) грамматика?

11. Как определяется S-грамматика?

Литература.

1. Компаниец Р.И., Маньков Е.В., Филатов Н.Е. Основы построения трансляторов. -СПб.: КОРОНА принт, 2000. -256 с.

2. Хантер Р. Проектирование и конструирование компиляторов. М.: Финансы и статистика. 1984 г.

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

Лабораторная работа №2

Формульный компилятор

Введение

Данная лабораторная работа рассчитана на четыре аудиторных часа. Самостоятельная работа по изучению литературы, оформление отчёта ещё шесть часов.

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

1. Содержание работы.

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

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

Оператор присвоения имеет общий вид для всех вариантов

Y=Y(x).

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

КОП, А1, А2, А3,

где: КОП - код операции,

А1- адрес первого операнда,

А2 - адрес второго операнда,

А3 - адрес результата.

Хотя возможны и другие варианты, например, по двухадресной и одноадресной схемам.

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

2. Задание по работе.

1. Получить вариант задания у преподавателя.

2. Разработать язык формульного транслятора.

3. На основе разработанной регулярной грамматики разработать

программу лексического анализатора.

4. На основе разработанной контекстно-свободной грамматики

разработать программу грамматического разбора исходного

текста на входном языке.

5. Во всех случаях предусмотреть сообщения пользователю о лексических и синтаксических ошибках.

6. Разработать и описать объектный псевдокод.

7. Составить и утвердить техническое задание на программу генерации.

8. Разработать программу генерации объектного псевдокода.

9. Составить отчёт по работе с описанием всех пунктов задания,

представить работающую программу.

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

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

Таблица 1.



Функция

1

acos

2

asin

3

atan

4

sin

5

cos

6

sinh

7

cosh



Таблица 2.



Функции

1

exp

2

abs

3

mod

4

sqrt

5

log

6

ln

7

log10



Таблица 3.



Функции

1

tan

2

tanh

3

cotan

4

cotanh

5

trunk

6

round

7

nearbyint



Подробные сведения о перечисленных функциях можно найти в справочнике программиста по С/C++.

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

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

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

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

5. Контрольные вопросы.

1. Каков приоритет в выполнении арифметических операций в

выражении?

2. Что такое лексема?

3. Каково назначение лексического анализа?

4. Каково назначение грамматического разбора?

5. Как определяется контекстно-свободная грамматика?

6. Что такое "четверки"?

7. Зачем используют псевдокод?

8. В чём особенность объектного кода?

9. Как из объектного кода получить исполняемый код?

Литература.

1. Бек Л. Введение в системное программирование. -М.: Мир, 1988.-448 с.

2. Компаниец Р.И., Маньков Е.В., Филатов Н.Е. Системное программи-

рование. Основы построения трансляторов.-СПб.: КОРОНА принт,

2000 .-256 с.

3. Шильд Г. Справочник программиста по С/С++.-М.: Издательский дом

"Вильямс", 2000.-448 с.

  1   2   3

Похожие:

Лабораторная работа выполняется в дисплейном классе. Результат представляет собой работающую программу, которая может анализировать любые тексты и сообщать об ошибках программирования icon3. Решение задач
Цикл представляет собой последовательность операторов, которая выполняется неоднократно
Лабораторная работа выполняется в дисплейном классе. Результат представляет собой работающую программу, которая может анализировать любые тексты и сообщать об ошибках программирования iconЛабораторная работа №1. Программирование с использованием встроенных функций ввода/вывода
Составить программу, которая переводит одни единицы измерения в другие. Исходные данные вводятся с клавиатуры, результат выводится...
Лабораторная работа выполняется в дисплейном классе. Результат представляет собой работающую программу, которая может анализировать любые тексты и сообщать об ошибках программирования iconЛабораторная работа №10 Основы алгоритмизации и программирования
Это снижает трудоемкость программирования. Однако, текст программы, записанный с помощью языка программирования, должен быть преобразован...
Лабораторная работа выполняется в дисплейном классе. Результат представляет собой работающую программу, которая может анализировать любые тексты и сообщать об ошибках программирования iconЛабораторная работа №1 "Команда ввода" примечание: Результаты работы программ и ответы на вопросы записывать в тетрадь. Задача Записать в оп программу: print «Добрый день»
Исполнить программу. Что появилось на экране? Чем отличается результат от предыдущего?
Лабораторная работа выполняется в дисплейном классе. Результат представляет собой работающую программу, которая может анализировать любые тексты и сообщать об ошибках программирования iconЛабораторная работа Правила работы с вычислительной установки Лабораторная работа Работа с клавиатурой
Лабораторный практикум по информатике представляет собой учебно-практическое издание для студентов педагогического вуза непрофильных...
Лабораторная работа выполняется в дисплейном классе. Результат представляет собой работающую программу, которая может анализировать любые тексты и сообщать об ошибках программирования iconЛабораторная работа 6 измерение 3eниthыx расстояний
Зенитное расстояние представляет собой угол z между отвесной линией в точке наблюдения и направлением на визирную
Лабораторная работа выполняется в дисплейном классе. Результат представляет собой работающую программу, которая может анализировать любые тексты и сообщать об ошибках программирования iconО дипломных проектах и научно исследовательских работах введение Выпускная квалификационная работа инженера (специалиста) представляет собой
Гос по специальности, а также умение применять полученные знания при выполнении конкретной задачи творческого характера. Квалификационная...
Лабораторная работа выполняется в дисплейном классе. Результат представляет собой работающую программу, которая может анализировать любые тексты и сообщать об ошибках программирования iconЛабораторная работа №23 Технология визуального программирования
Цель работы: изучение технологии визуального программирования и элементов объектно-ориентированного программирования
Лабораторная работа выполняется в дисплейном классе. Результат представляет собой работающую программу, которая может анализировать любые тексты и сообщать об ошибках программирования icon1. 3 Технология программирования и основные этапы ее развития
Технология программирования представляет собой набор технологических инструкций, включающих
Лабораторная работа выполняется в дисплейном классе. Результат представляет собой работающую программу, которая может анализировать любые тексты и сообщать об ошибках программирования iconЛабораторная работа №2
Цель работы: изучить методы передачи данных через com-порт и написать программу, которая бы позволяла передачу данных от одного пк...
Разместите кнопку на своём сайте:
Библиотека


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