[ Министерство образования и науки Украины
Севастопольский национальный технический университет
МЕТОДИЧЕСКИЕ УКАЗАНИЯ
к выполнению лабораторно - вычислительного практикума
по дисциплине
“Операционные системы и системное программирование.
Часть II - системное программирование” для студентов, обучающихся по направлению 05.0101 Компьютерные науки” всех форм обучения Севастополь 2010 Create PDF files without this message by purchasing novaPDF printer (http://www.novapdf.com) УДК 004. Методические указания к выполнению лабораторно - вычислительного практикума по дисциплине “Операционные системы и системное программирование. Часть II - системное программирование” для студентов, обучающихся по направлению 05.0101 - “Компьютерные науки” всех форм обучения/ Разраб. В.Ю. Карлусов. - Севастополь: Изд-во СевНТУ, 2010. – 36 с.
Цель методических указаний: выработка у учащихся необходимых исследовательских и практических навыков применения основных положений теорий конечных автоматов, формальных грамматик и синтаксического анализа и компиляции при решении задач системного программирования, связанных с построением трансляторов.
Методические указания рассмотрены и утверждены на заседании кафедры Информационных систем, протокол № 07 от 17 марта 2010 г.
Допущено учебно-методическим центром СевНТУ в качестве методических указаний.
Рецензент Апраксин Ю.К., д.-р техн. наук, профессор кафедры кибернетики и вычислительной техники.
Create PDF files without this message by purchasing novaPDF printer (http://www.novapdf.com)
СОДЕРЖАНИЕ
Введение 1. Лабораторная работа № 1. “Исследование детерминированного конечного автомата” 2. Лабораторная работа № 2. “Исследование сканера при анализе простых языковых конструкций” 3. Лабораторная работа № 3. “Исследование алгоритма простого нисходящего распознавателя” 4. Лабораторная работа № 4. “Исследование алгоритма нисходящего распознавателя языка LL(k) грамматики” 5. Лабораторная работа № 5. “Исследование алгоритма простого восходящего распознавателя” 6. Лабораторная работа № 6. “Исследование алгоритма восходящего анализатора языка грамматики простого предшествования” 7. Лабораторная работа № 7. “Исследование алгоритма восходящего анализатора языка грамматики операторного предшествования” 8. Лабораторная работа № 8. “Исследование алгоритмов трансляции арифметических выражений” Заключение Библиографический список Приложение А Приложение Б Приложение В Create PDF files without this message by purchasing novaPDF printer (http://www.novapdf.com)ВВЕДЕНИЕ
Одним из немаловажных компонентов информационных технологий является компьютерный анализ синтаксиса текстов. К настоящему времени элементы его присутствуют практически повсеместно: в трансляторах языков программирования – от ассемблеров до объектно-ориентированных алгоритмических языков, контроля орфографии редактора “Word”, с использованием которого набраны настоящие методические указания, разнообразных переводчиков типа Prompt, РУМП и им подобных, наконец, квинтэссенции информационных систем – системах искусственного интеллекта. Поэтому трансляторы являются важной практической областью научных исследований, связанных с изучением ЭВМ[4].В настоящем практикуме изучаются методы, ориентированные на использование теории формальных языков и грамматик при решении задач распознавания синтаксиса. Вопросы генерации объектного кода и его оптимизации опущены по следующим соображениям:
наряду со значительными объёмами текстов соответствующих программ, алгоритмы генерации и оптимизации [6, 13] кодов обладают известной степенью инвариантности и универсализма, что, в немалой степени, препятствует формированию нетривиальных заданий при их изучении и исследовании. Последнее обстоятельство, как известно, толкает студента на путь формалистики и поверхностного изучения дисциплины.
Варианты практических заданий сформулированы на основании [8, 10, 14], примеры аналитических преобразований и вычислений, необходимых в ходе выполнения работ, помещены в [10 – 12].
“ИССЛЕДОВАНИЕ ДЕТЕРМИНИРОВАННОГО КОНЕЧНОГО АВТОМАТА”
1.1. Научиться производить построение детерминированных конечных автоматов (ДКА), допускающих определённые цепочки символов языка.1.2. Освоить приёмы описания конечных автоматов (КА) в виде графов, таблиц переходов и регулярных выражений.
1.3. Научиться выполнять построения ДКА по недетерминированным конечным автоматам (НКА).
1.3. Научиться проводить построение минимальных детерминированных конечных автоматов (МДКА).
Конечным автоматом (КА), под которым, в дальнейшем, будем понимать конечный автомат Мили, формально называют совокупность следующих объектов [15, 16, 19]:
Create PDF files without this message by purchasing novaPDF printer (http://www.novapdf.com) где Q – конечное множество состояния автомата; - алфавит входных символов (букв или литер); - функция переходов КА, определяемая на декартовом произведении Q; q0 Q – начальное состояние КА; FQ – множество заключительных состояний КА. Автомат функционирует на основании следующих эмпирических правил [15].
1. Исходным состоянием КА является начальное состояние q0.
2. Цепочка, составленная из литер алфавита, по одной букве поступает на вход КА.
Возврат к начальным литерам цепочки не возможен.
3. Литера Sj допускается КА, находящимся в состоянии qi, если (qi, Sj){} – иными словами, образ функции переходов не пуст, определён переход из текущего состояния КА в 4. Если литера входной цепочки не допускается, то цепочка отвергается, признаётся не принадлежащей входному языку КА, сам автомат остаётся в текущем состоянии.
5. Цепочка литер допускается КА, если после поступления её последнего символа автомат оказывается в одном из заключительных состояний qrF. В противном случае цепочка отвергается.
Известны теоремы [16], устанавливающие соответствие между классами конечных автоматов и классами цепочек, называемыми регулярными, которые могут быть проверены на принадлежность языку, порождаемому определённой грамматикой, с помощью КА.
Элементы КА могут быть построены и описаны несколькими способами [7 – 9, 15, 16], указанные процедуры излагаются и в методической литературе [10, с. 9 – 17; 11, с. 23 Одним из эффективных способов описания КА является регулярное выражение, особенно когда известен вид цепочек, подлежащих опознаванию.
Правила написания регулярных выражений для типовых конструкций таковы [10, 16], при этом фигурные скобки обозначают итерацию, то, что в них заключено, может повторяться от нуля до бесчисленного числа раз. круглые или квадратные – используют для объединения альтернатив, из которых одна обязательно присутствует.
Пусть имеется алфавит составленный из символов (букв, литер) VT = {x1,x2,...,xn}.
1. Множество всевозможных цепочек, составленных из букв xi VT :
2. Множество цепочек, составленных из литер xi VT и оканчивающихся литерой x1.
3. Множество цепочек, составленных из литер xi VT начинающихся цепочкой l1 и оканчивающихся l2.
4. Множество однолитерных цепочек (однобуквенных слов) совпадает c алфавитом 5. Множество двулитерных цепочек (двухбуквенных слов) С точки зрения техники реализации КА на ЭВМ, предпочтительнее является его описание в виде таблиц переходов и выходов, иногда совмещённых, первая из них есть табличный аналог, символам входного алфавита соответствуют строки, а состояниям – столбцы.
Иногда функция переходов определена неоднозначно, в этом случае КА будет недерминированным. При этом необходимо получить детерминированный конечный автомат (ДКА) по недетерминированному КА. Приёмы построения ДКА по недетерминированному Create PDF files without this message by purchasing novaPDF printer (http://www.novapdf.com) КА, иллюстрируются многочисленными примерами, приводимыми в [10, с. 10 – 13]. Известен [10, 16, 19] следующий алгоритм построения ДКА по НКА.
Для случаев, когда значение функции определено неоднозначно, введём новое состояние, которое является объединением состояний, образующих неоднозначность, в множество состояний автомата,.
2. Для вновь введенного состояния строим функцию переходов; анализируя функцию переходов в состояниях, определяющих данное состояние.
3. Повторяем п.п. 1 – 2 до тех пор, пока множество состояний автомата не будет изменено, а функция переходов приобретёт однозначность.
Технически оправдано иметь таблицу переходов КА минимального размера. Очевидно, что число строк таблицы изменению не подлежит, как определяемое внешними условиями, а число состояний КА и, соответственно, количество столбцов, может быть уменьшено в соответствии с теоремой Майхилла – Нерода [16]. Примеры такого упрощения приводятся в [10, с. 15 – 21; 11, с. 23 - 27]. Программная реализация КА может быть различной [1, с. 60 – 61, 86; 10, с. 15; 11, с. 26 - 37], тем не менее, неизменно наличие следующих этапов.
1. Начальное состояние – нулевое, соответствующий столбец – первый, он же является текущим.
2. Выполнение действий, связанных с обработкой текущего состояния КА.
3. Определение строки управляющей таблицы, соответствующей поступившей литере.
4. Определение следующего состояния КА и соответствующего номера столбца.
5. Пункты 2 – 3 выполняются, пока не будет достигнуто одно из заключительных состояний, после чего принимается решение о принадлежности или непринадлежности к одному из множеств цепочек.
Выполнение работы занимает два аудиторных занятия (4 академических часа) и предполагает интенсивную домашнюю подготовку.
3.1. Домашняя подготовка. На основании кода варианта в виде регулярного выражения, полученного у преподавателя, взять регулярное выражение из приложения А. Выполнить разметку регулярного выражения согласно [10], по необходимости минимизировать.
Если КА не является детерминированным, необходимо привести его к детерминированному виду. Построить таблицу переходов МДКА. Выполнить минимизацию по таблице переходов.
Построить граф конечного автомата для визуального определения недостижимых состояний, и, если таковые обнаружатся, окончательно минимизировать ДКА, построив окончательную таблицу МДКА. Написать черновой вариант программы на языке С (С++).
3.2. Занятие 1 (2 часа). Предъявить результаты домашней подготовки для проверки преподавателю, устранить ошибки согласно замечаниям преподавателя. Ввести программу, реализующую КА, довести её до успешной компиляции.
3.3. Домашняя подготовка. Разработать тестовые последовательности литер, допускаемые и отвергаемые КА. Найти допускаемые последовательности минимальной длины.
Предусмотреть соответствующие диагностические сообщения. Каждая цепочка литер должна быть снабжена соответствующей последовательностью вершин КА, которую он проходит в процессе анализа цепочки.
Подготовить пункты отчёта, касающиеся выполненной работы.
Create PDF files without this message by purchasing novaPDF printer (http://www.novapdf.com) 3.4. Занятие 2 (2 часа). Предъявление материалов тестирования преподавателю и отладка программы. Окончательное оформление отчёта и защита результатов выполнения лабораторной работы.
4.2. Аналитические выкладки по проведению минимизации и, по необходимости построения ДКА, управляющая таблица КА.
4.3. Тестовые примеры для отладки включая допускаемые последовательности минимальной длины.
4.4. Листинги программы, результаты выполнения тестирования и граф конечного автомата, график числа синтаксических ошибок, выявленных на стадии компиляции программы в функции от номера постановки на компиляцию, график числа логических ошибок, выявленных в ходе отладки программы в функции от номера постановки на счёт.
4.5. Содержательные выводы, в которых отражено: изменение числа состояний КА в ходе выполнения лабораторной работы; анализ динамики выявленных ошибок; размер исходного модуля, размер исполнимого модуля.
5. Вопросы для самоконтроля и самоподготовки 5.1. Определение, способы описания и построения конечных автоматов.
5.2. Формулировки теорем о связи КА и формальной грамматики, соответствия недетерминированного КА и детерминированного КА.
5.3. Привести алгоритм построения ДКА по НКА.
5.5. Минимизация КА по регулярному выражению и таблицам переходов и выходов.
5.7. Какие гипотезы положены в основу функционирования КА?
5.8. Какой КА называется недетерминированным?
5.9. Правила написания регулярных выражений.
5.10. Какая цепочка входных литер допускается КА?
5.11. Какая цепочка входных литер не допускается КА?
5.12. В чём заключается отношение эквивалентности применительно к цепочкам, обрабатываемым конечным автоматом?
5.13. Почему для программной или схемной реализации КА необходимо его приведение к детерминированному виду?
5.14. Привести примеры задач, решаемых с применением КА[19].
Create PDF files without this message by purchasing novaPDF printer (http://www.novapdf.com)
“ИССЛЕДОВАНИЕ СКАНЕРА ПРИ АНАЛИЗЕ ПРОСТЫХ ЯЗЫКОВЫХ КОНСТРУКЦИЙ”
1.1. Изучить принципы построения и программирования лексического анализатора на языке С (С++) для простых языковых конструкций.1.2. Получить навыки практического построения лексического анализатора (сканера) на основе теории конечных автоматов.
1.3. Освоить приёмы составления регулярных выражений для описания лексем.
1.4. Закрепить навыки построения минимального КА, осуществляющего сканирование текста программ.
Из общей структуры компилятора [3 – 4; 5, с. 19] видно, что лексический анализатор (сканер) занимает заметное место в аналитической части транслятора и является первой (по времени начала выполнения) системной программой, анализирующей исходный модуль пользователя.
Сканер получил свое наименование благодаря особенности обработки входной информации. В его задачу входит: анализ исходной программы на уровне лексем [7, 9, 18]; выдача диагностических сообщений об обнаруженных ошибках; построение информационных таблиц констант, идентификаторов, служебных слов, разделителей; перекодирование исходной программы в соответствии с построенными таблицами.
Входной информацией сканера является литеры исходной анализируемой программы, а выходной - внутренняя, перекодированная форма программы и таблицы лексем [7]. Для построения сканера широко используют регулярные выражения и конечные автоматы, которые описываются регулярными (автоматными грамматиками) [15, 16, 19]. К сожалению, возможности регулярных языков ограничены. Поэтому роль грамматик, порождающих регулярные языки, сведена к распознаванию лексем, используемых в программе [15]. Указанный этап компиляции получил название лексического анализа.
Построение сканера наиболее формально и точно можно осуществить по регулярному выражению, при этом творческая компонента присутствует при составлении регулярного выражения, уступая затем место строгим алгоритмам. Примеры построения регулярного выражения и конечного автомата на его основе, осуществляющего процедуру лексического анализа, приводятся в [10, с. 22 – 24; 11, с. 33 - 36].
Возможен подход к построению сканера на основании диаграммы состояний (графа) автомата. Указанный подход проектирования является, по сути, эмпирическим, его ясное и подробное изложение выполнено Д. Грисом [7]. За исключением построения управляющей таблицы КА сканера, в нём соблюдается вся методология проектирования программных систем[13, 17], что вполне может быть использовано студентами при выполнении настоящей лабораторной работы.
Create PDF files without this message by purchasing novaPDF printer (http://www.novapdf.com) Выполнение работы занимает два аудиторных занятия (4 академических часа) и предполагает интенсивную домашнюю подготовку.
3.1. Домашняя подготовка. Согласно выданному заданию составить регулярное выражение, описывающее КА, который осуществляет лексический анализ.
Структура такого выражения примерно такова L1 – лексема, состоящая в том, что текущая литера не буква и не цифра.
L2 – текущая литера не принадлежит к образующим константу или литерал.
L3 – литера, не принадлежащая алфавиту конечного автомата.
В ходе домашних экзерциций составить эскизные выражения для описания дизъюнктивных компонент. Построить управляющую таблицу МДКА, Продумать модернизацию программы из предыдущей работы под нужды лексического анализа и текст диагностических сообщений, генерируемых в его ходе. Разработать схему кодирования лексем.
3.2. Занятие 1 (2 часа). Согласовать текст диагностических сообщений с преподавателем, сконструировать текст программы сканера на основании программы МДКА с учётом домашней подготовки. Выявить и устранить синтаксические ошибки.
3.3. Домашняя подготовка. Разработать тестовые примеры правильных и неправильных лексем языка, уточнить диагностические сообщения. Подготовить мероприятия по хронометрированию работы сканера. Продумать структуру выходной информации программы на предмет использования другими программными модулями компилятора. Подготовить 3.4. Занятие 2 (2 часа). Тестировать и окончательно отладить программу. Экспериментально определить время работы сканера для качественно различных структур строк и характера ошибок. Завершить оформление отчёта и защитить результаты выполнения лабораторной работы.
4.2. Регулярное выражение КА, осуществляющего лексический анализ; аналитические преобразования, выполненные при построении детерминированного минимального КА;
управляющая таблица КА.
4.3. Тестовые примеры и тексты диагностических сообщений.
4.4. Листинги сервисных процедур и результатов тестирования.
4.5. Статистика синтаксической и логической отладки программ, выполненная по аналогии п. 4.4. предыдущей работы.
4.6. Осмысленные выводы, в которых должно быть отражено: изменение объёмов (в символах) входной и выходной информации; результаты хронометража - среднее время, затрачиваемое на сканирование строки исходного текста; анализ динамики выявленных ошибок; размер исходного модуля, размер исполнимого модуля.
Create PDF files without this message by purchasing novaPDF printer (http://www.novapdf.com) 5. Вопросы для самоконтроля и самоподготовки 5.1. Назначение сканера и его место в схеме трансляции.
5.2. Типы лексем и система их кодирования.
5.3. Виды таблиц, создаваемых и используемых лексическим анализатором и способы их организации [7, 9, 18].
5.4. Характерные особенности функционирования лексического анализатора.
5.5. Методология построения лексических анализаторов.
“ИССЛЕДОВАНИЕ АЛГОРИТМА ПРОСТОГО НИСХОДЯЩЕГО РАСПОЗНАВАТЕЛЯ”
1.1. Приобрести навыки описания синтаксиса алгоритмических языков средствами формальных грамматик.1.2. Получить опыт разработки структуры данных, необходимых для хранения правил 1.2. Выполнить оценку эффективности работы универсального нисходящего синтаксического анализатора.
Простой нисходящий разбор является исторически одним из первых подходов к осуществлению автоматического синтаксического анализа. При выполнении алгоритма осуществляется попытка построения синтаксического дерева вывода [5; 7; 10, c. 6], и, если таковое удаётся построить, то анализируемая конструкция считается синтаксически корректной. Алгоритм обстоятельно описан в [7, c. 107 – 114], приводится программа на псевдоязыке [5, c.
95 - 108], отмечаются недостатки алгоритма и рассмотрена структура [7, c. 115 – 120] представления грамматики в виде синтаксического графа.
Функционирование алгоритма, в общих чертах, таково (смотри рисунок 3.1).
1. Используются два стека (магазина): магазин поставленных целей (МПЦ) для хранения нетерминальных символов, из которых, предположительно, выведена анализируемая конструкция языка, и магазин достигнутых целей (МДЦ) для хранения нетерминалов, для которых удалось установить такой вывод. Конструкция считается синтаксически корректной, если по окончании разбора в МДЦ будет находиться аксиома формальной грамматики.
2. В ходе обработки правил грамматики, в МПЦ помещаются нетерминальные символы, до тех пор, пока не будет достигнут терминальный.
Create PDF files without this message by purchasing novaPDF printer (http://www.novapdf.com) Create PDF files without this message by purchasing novaPDF printer (http://www.novapdf.com) 3. Этот терминал сопоставляется с очередным символом программы. Если символы несопоставимы, проверяют возможную альтернативу терминалу. Когда все проверки окончатся неудачей, то текущая цель выталкивается из МПЦ, и проверяется нетерминальная альтернатива у глобальной цели.
4. Если альтернативы исчерпаны, то фиксируется ошибка, в противном (удачном) случае удаётся достичь конца правила, и текущая поставленная цель считается достигнутой и переписывается МДЦ.
5. Когда достигнут конец текста, то МДЦ и исходная конструкция образуют синтаксическое дерево.
Входной информацией для анализатора является последовательность кодов, соответствующая тексту исходной программы, которую готовит сканер (смотри лабораторную работу № 2). Информация в синтаксическом графе представляется в этой же системе кодировки терминальных и нетерминальных символов, которая разработана ранее для сканера.
Выполнение работы занимает два аудиторных занятия (4 академических часа) и предполагает интенсивную домашнюю подготовку.
3.1. Домашняя подготовка. Для Вашего варианта задания, согласно рекомендации [2, 4, 5, 7 – 12], по образу и подобию [1] описания языков программирования в форме Бекуса – Наура, выполнить построение формальной грамматики. Особое внимание следует на устранение явной левой рекурсии в правилах, паче таковая непременно возникнет:
Для большей устойчивости работы анализатора рекомендуется преобразовать грамматику в нормальную форму Грейбах [10, с. 37 – 41; 11, с.9 - 10; 16], правда, подобное преобразования приведёт к заметному увеличению количества правил грамматики и размера области хранения её синтаксического графа.
Составить текст программы, реализующей алгоритм простого нисходящего разбора.
Продумать структуру синтаксического графа и диагностические сообщения, которые должны выдаваться при возникновении синтаксических ошибок.
3.2. Занятие 1 (2 часа). Предъявить формальную грамматику преподавателю, обсудить диагностические сообщения. Ввести программу в компьютер устранить синтаксические ошибки, добиться успешной компиляции.
3.3. Домашняя подготовка. Модифицировать грамматику согласно результатам обсуждения с преподавателем. Подготовить информацию для занесения в синтаксический граф.
Продумать ход тестирования программы и разработать тесты [17]. Позаимствовать из предыдущей работы средства хронометража. Подготовить пункты отчёта.
3.4. Занятие 2 (2 часа). Согласовать тесты с преподавателем. Осуществить отладку логики нисходящего анализатора. Зафиксировать время, затрачиваемое анализатором на обработку тестов с разной синтаксической структурой. Предъявить материалы выполнения.
Окончательно оформить отчёт и защитить результаты выполнения лабораторной работы.
Create PDF files without this message by purchasing novaPDF printer (http://www.novapdf.com) 4.2. Формальная грамматика с правилами, свободными от левой рекурсии, порождающая фрагменты программы, соответствующие заданному варианту, дерево программы.
4.3. Разработанную структуру представления правил грамматики.
4.4. Тестовые примеры и тексты диагностических сообщений.
4.5. Листинг результатов тестирования.
4.5. Статистика синтаксической и логической отладки программ, аналогично предыдущим работам.
4.6. Осмысленные выводы, в которых должно быть отражено: минимальное, максимальное и среднее время, затрачиваемое на синтаксический разбор; размер исходного модуля, размер исполнимого модуля.
5. Вопросы для самоконтроля и самоподготовки 5.1. Назначение синтаксического разбора.
5.2. Принцип работы нисходящего распознавателя.
5.3. Основные недостатки простого нисходящего разбора.
5.4. Способы устранения левой рекурсии в правилах формальных грамматик.
5.5. Способы и особенности организации данных для осуществления нисходящего “ИССЛЕДОВАНИЕ АЛГОРИТМА
НИСХОДЯЩЕГО РАСПОЗНАВАТЕЛЯ ЯЗЫКА LL(к) ГРАММАТИКИ”
1.2. Приобрести навыки в исследовании грамматики на принадлежность к классу 1.3. Освоить методы синтеза формальных грамматик класса LL(к) и, по необходимости, преобразования грамматики к этому классу В качестве основного недостатка алгоритма простого нисходящего разбора указывается [7, c. 115 – 120] отсутствие прогноза при выборе возможного правила формальной грамматики из множества альтернатив для построения дерева. Следствием неправильного определения правила, гипотетически использованного при выводе и ведущего к неудаче, поCreate PDF files without this message by purchasing novaPDF printer (http://www.novapdf.com) следующее восстановление правильного хода вывода, приводит к непроизводительным затратам ресурсов ЭВМ и времени выполнения трансляции, варьируемым в широких пределах.
Таким образом, проблемой решаемой на каждом шаге разбора является определение очередного правила подстановки. В этом случае, если по k проанализированным символам исходной программы можно однозначно определить, какую продукцию грамматики необходимо использовать, грамматика называется LL(к) - грамматикой и, в этом случае, применяют алгоритм рекурсивного спуска [5, 16], а сам алгоритм разбора называют иногда прогнозирующим.
Одной из особенностей данной схемы трансляции является её жёсткая ориентация на конкретную грамматику, поэтому метод относят к группе специализированных методов. При этом на каждый символ формальной грамматики, как терминальный, так и нетерминальный, разрабатывается алгоритм, и пишется процедура его распознавания. Порядок вызова процедур определяется местоположением распознаваемых символов в правилах исходной грамматики. Поэтому алгоритм относят к группе методов синтаксических функций [2, 9, 18].
Исследование грамматики на принадлежность к классу LL(к) состоит в отыскании уникальных цепочек терминальных символов, выводимых из головы правой части правила.
Изложение алгоритма, иллюстрация его применения и примеры для закрепления приводятся в [10, c. 24 – 26; 11, 38 – 40]. Там же приводится текст программы на С (С++). Заметим, что рекурсивные вызовы при работе распознавателя могут быть организованы как явным, так и неявным способами. При кажущейся простоте алгоритма, он весьма эффективен и широко распространён: достаточно отметить, что компилятор с алгоритмического языка Pascal построен по данной схеме на основании свойств LL(1) – грамматики. Как недостаток можно отметить однопроходовость такого транслятора: его работа завершается нахождением первой встреченной от начала программы ошибки. Обычно отдают предпочтение LL(1) – грамматике, что упрощает процедуру обработки анализируемого фрагмента строки, а LL(к) грамматики с большим индексом k используют вынужденно.
В качестве входной информации нисходящий рекурсивный распознаватель использует перекодированную программу [7, c. 19], принимаемую после работы сканера.
Выполнение работы занимает два аудиторных занятия (4 академических часа) и предполагает интенсивную домашнюю подготовку.
3.1. Домашняя подготовка. Для Вашего варианта построить формальную LL(1) – грамматику, свободную от левой рекурсии, либо позаимствовать её из предыдущей работы.
Если грамматика не является LL(1) – грамматикой, то её необходимо преобразовать к такому виду [7]. Типичной проблемой, препятствующей отнесению грамматики к классу LL(1), является наличие альтернативных правых частей правил с одинаковыми головами. Преобразование заключается во введении новых правил.
Рекурсия тоже препятствует причислению грамматики к этому классу. Преобразование заключается в использовании итерационного повторителя { }, который программно осуществляется итерационным циклом типа while или until.
Create PDF files without this message by purchasing novaPDF printer (http://www.novapdf.com) Составить текст программы, реализующей рекурсивный алгоритм разбора. Продумать диагностические сообщения, которые должны выдаваться при возникновении синтаксических ошибок.
3.2. Занятие 1 (2 часа). Предъявить формальную LL(1) – грамматику, совместно с доказательством её свойств, преподавателю. Ввести программу в компьютер, добиться успешной компиляции. В ходе отладки синтаксиса программы вести учёт синтаксических ошибок, выявляемых в ходе каждой компиляции.
3.3. Домашняя подготовка. Модифицировать грамматику согласно результатам обсуждения с преподавателем, если возникнет необходимость. Подготовить диагностические сообщения и определить места их размещения в тексте анализатора. Продумать ход тестирования программы и разработать тесты. Позаимствовать из предыдущей работы средства хронометража. Подготовить пункты отчёта.
3.4. Занятие 2 (2 часа). Согласовать тесты с преподавателем. Осуществить отладку логики рекурсивного анализатора. Зафиксировать время, затрачиваемое анализатором на обработку тестов с разной синтаксической структурой, сравнить временные характеристики с характеристиками простого нисходящего распознавателя. Предъявить материалы выполнения.
Окончательно оформить отчёт и защитить результаты выполнения лабораторной работы.
4.2. Формальная грамматика LL(1), порождающая фрагменты программы, соответствующие заданному варианту.
4.3. Текст программы рекурсивного нисходящего распознавателя.
4.4. Тестовые примеры и тексты диагностических сообщений.
4.5. Листинг результатов тестирования.
4.5. Статистика синтаксической и логической отладки программ, полученная по аналогии предыдущих работ.
4.6. Осмысленные выводы, в которых должно быть отражено: среднее время, затрачиваемое на синтаксический разбор, насколько эффективнее данный алгоритм по сравнению с алгоритмом простого нисходящего распознавателя; размер исходного модуля, размер исполнимого модуля.
5. Вопросы для самоконтроля и самоподготовки 5.1. Формулировка теорем о преобразовании формальной грамматики в нормальную форму Грейбах [16].
5.2 Приёмы преобразования грамматик, направленные на устранения левой рекурсии.
5.3. Процедура определения принадлежности грамматики к классу LL(к).
5.4. Сущность и особенности метода синтаксических функций.
5.5. Преимущества нисходящего разбора, основанного на свойствах LL(к) грамматик перед обычным нисходящим разбором.
Create PDF files without this message by purchasing novaPDF printer (http://www.novapdf.com)
“ИССЛЕДОВАНИЕ АЛГОРИТМА ПРОСТОГО ВОСХОДЯЩЕГО РАСПОЗНАВАТЕЛЯ”
1.1. Изучение принципов построения и особенностей функционирования алгоритма простого восходящего разбора.1.2. Закрепление навыков построения синтаксических анализаторов.
1.3. Оценка эффективности работы программы, реализующей алгоритм Термин “восходящий разбор” характеризует направление построения синтаксического дерева (дерева разбора), предполагая движение от сентенциальной формы (оператора) к вершине, которую представляет аксиома грамматики, предложения которой разбираются [2, 4 - 9, 13, 14, 16]. Простой восходящий разбор инвариантен, то есть обладает универсальностью по отношению к свойствам формальной грамматики, за исключением свойства однозначности. Так как при обработке предложения алгоритмического языка априори отсутствуют сведения о том, какие правила грамматики и в каком порядке использованы для его получения, то в ходе применения алгоритма не избежать использования проб и ошибок. Выбор простой фразы в качестве возможной основы разбора при неудаче обуславливает восстановление (полностью либо частично) исходного текста. Указанные действия в алгоритме соответствуют операциям подстановки и отхода, действие которых наглядно проиллюстрировано [5, с. 113]. Одним из удачных решений является алгоритм [5, с. 109 - 118]. Так же, как и все синтаксические анализаторы, он использует информацию, подготовленную сканером. Алгоритм простого восходящего разбора, изображённый на рисунке 5.1, включает следующие эвристики.
1. Языковая конструкция, проверяемая на правописание, анализируется “слева направо” посимвольно.
2. В ходе анализа все подстроки, от начала и до текущей позиции строки, сопоставляются с правыми частями продукций формальной грамматики.
3. При совпадении осуществляется подстановка, состоящая в замене совпавшей подстроки с левой частью (корнем) соответствующего правила. Таким образом, последний нетерминальный символ строки определяет последнюю выполненную подстановку.
4. Если, по достижении конца строки, в ходе выполнения подстановок, она трансформируется в аксиому, то анализируемая конструкция принадлежит языку, порождаемому формальной грамматикой, и, следовательно, является синтаксически правильной.
5. В противном случае, выполняется постепенный отход, состоящий в замене левого нетерминала, правой частью (аргументом) правила, его определяющего.
6. Чтобы избежать зацикливания, правила нумеруются, и номер использованного правила хранится вместе с нетерминалом, полученным в ходе подстановки, а выбор очередного правила производится в порядке возрастания номеров.
7. Если все подстановки не увенчались успехом, а исходная строка не содержит более основ, языковая конструкция признаётся ошибочной.
Create PDF files without this message by purchasing novaPDF printer (http://www.novapdf.com) 2. Поместить в стек ХРАНЕНИЕ символ из ВХОД’а, номер правила Nр положить равным нулю.
3. Поиск правила грамматики, номер которого больше Np, у которого правая 5. Формирование дерева разбора: ДЕРЕВО (разделитель фраз), перепись 12. Восстановить Np и аргумент правила, соответствующего нетерминалу В заключение заметим, что синтаксическое дерево, получаемое в результате разбора, помимо подтверждения правильности предложения, может быть, в случае ошибки, использовано для её нейтрализации [7, с. 353 -356], так, в частности, работали компиляторы PL/I Create PDF files without this message by purchasing novaPDF printer (http://www.novapdf.com) Выполнение работы занимает два аудиторных занятия (4 академических часа) и предполагает интенсивную домашнюю подготовку.
3.1. Домашняя подготовка. Алгоритм простого восходящего разбора является универсальным, поэтому к формальной грамматике не предъявляются иные требование, кроме непустоты порождаемого языка [16, 18] и однозначности самой грамматики [7,9]. Поэтому целесообразно переработать или разработать заново грамматику, составленную в ходе выполнения предыдущих работ, чтобы минимизировать число правил и объём синтаксического Взяв за основу алгоритм [5, с. 109 - 118], разработайте программу, его реализующую.
Продумайте структуры хранения данных, поисковые процедуры, взаимодействие с лексическим анализатором (сканером).
3.2. Занятие 1 (2 часа). Обсудить грамматику с преподавателем, ввести программу в компьютер, добиться успешной компиляции.
3.3. Домашняя подготовка. Если необходимо, внести корректуры в правила формальной грамматики. Разработать тестовые примеры, диагностические сообщения. Позаимствовать из предыдущей работы средства хронометража. Подготовить пункты отчёта.
3.4. Занятие 2 (2 часа). Согласовать тесты с преподавателем. Осуществить отладку логики восходящего анализатора. Зафиксировать время, затрачиваемое анализатором на обработку тестов разной синтаксической структуры, сравнить временные характеристики простого восходящего анализатора с характеристиками простого и рекурсивного нисходящих распознавателей. Предъявить материалы выполнения. Окончательно оформить отчёт и защитить результаты выполнения лабораторной работы.
4.2. Формальная грамматика, порождающая фрагменты программы, соответствующие заданному варианту.
4.3. Текст программы простого восходящего распознавателя.
4.4. Тестовые примеры и тексты диагностических сообщений, результаты тестирования.
4.5. Статистика синтаксической и логической отладки программ, полученная по аналогии предыдущих работ 4.5. Осмысленные выводы, в которых должно быть отражено: среднее время, затрачиваемое на синтаксический разбор, и его сопоставление с временными оценками других программ синтаксического разбора; размер исходного модуля, размер исполнимого модуля.
5. Вопросы для самоконтроля и самоподготовки 5.1. Преимущества и недостатки простого восходящего разбора.
5.3. Каким образом осуществляется поиск основы в ходе анализа.
Create PDF files without this message by purchasing novaPDF printer (http://www.novapdf.com) 5.4. Особенности структур данных, обеспечивающих функционирование алгоритма.
5.5. Возможен ли точный прогноз времени выполнения простого восходящего анализа?
“ИССЛЕДОВАНИЕ АЛГОРИТМА ВОСХОДЯЩЕГО АНАЛИЗАТОРА ЯЗЫКА
ГРАММАТИКИ ПРОСТОГО ПРЕДШЕСТВОВАНИЯ”
1.1. Изучить синтаксические анализаторы, базирующиеся на свойствах простого предшествования.1.2. Освоить описание синтаксиса языков программирования грамматиками предшествования.
1.3. Получить исследовательские навыки построения отношений предшествования.
1.4. Освоить правила преобразования произвольной грамматики в грамматику предшествования 1.5. Исследовать временные показатели программы, реализующие алгоритм разбора предложений языка грамматики простого предшествования.
Отношение простого предшествования между рядом стоящими символами алфавита (объединённого словаря) R и S позволяет определить аргумент продукции при поиске основы синтаксического разбора, так как указывает на одну из четырёх ситуаций: а) R и S стоят рядом в каком либо правиле; б) R – конец правила; в) S - начало правила; г) R и S несовместимы в синтаксически правильной программе [2, 5 – 9, 14].
Однозначные отношения существуют для класса грамматик простого предшествования, прилагательное “простой” нередко опускается. Если грамматика принадлежит к такому классу, то возможно построить эффективный распознаватель её языка, который, по отношению к обычному распознавателю, будет обладать повышенными скоростными характеристиками. Иногда представляется возможным построить функции предшествования (когда последние существуют) [7, параграф 5.4.]. В этом случае удаётся минимизировать размеры матрицы, которой представлены отношения предшествования, с размера nn до 2n. Идеи, положенные в основание алгоритма разбора (рисунок 6.1), просты.
1. Символы последовательно просматриваются слева направо до выполнения отношения >. Его выполнение означает, что предпоследний символ является концевым в каком-то правиле формальной грамматики.
2. Правая часть правила определяется отношением эквивалентности между символами, входящими в него, включая и предпоследний символ. Слева она ограничивается выполнением отношения S?
«