Навигация
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} без недостижимых символов. Метод состоит в следующем:
Похожие работы
... процессом init (процесс, идентификатор которого pid = 1, становится их новым родителем). Порядок выполнения работы 1. Изучить теоретическую часть лабораторной работы. 2. Организовать функционирование процессов следующей структуры: 2.1. Отец формирует нумерованные сообщения вида: N pid time (N –текущий номер сообщения, pid – pid процесса, time – время записи в формате мм.сс (минуты. ...
... работы со справочной системой работа практикума приостанавливается. 3. Организационно-экономическое обоснование проекта В ходе дипломного проекта был разработан компьютерный лабораторный практикум по курсу «Теория оптимизации и численные методы». В данном разделе рассмотрена экономическая сторона проекта. Рассмотрены следующие вопросы: 1) сетевая модель 2) расчёт ...
... концентрических окружностей с уменьшающимся радиусом по мере затухания колебаний скорости и момента. Аналогичная картина наблюдается при ступенчатом набросе нагрузки. 5. РАЗРАБОТКА ВИРТУАЛЬНОЙ ЛАБОРАТОРНОЙ РАБОТЫ НА БАЗЕ ВИРТУАЛЬНОЙ АСИНХРОННОЙ МАШИНЫ Иную возможность анализа АД представляет специализированный раздел по электротехнике Toolbox Power System Block. В его библиотеке имеются блоки ...
... гистерезисная диаграмма поляризации сегнетоэлектрика. Подобрать масштаб по вертикальной оси осциллографа так, чтобы изображение занимало весь экран. Внимание: в процессе выполнения последующих пунктов лабораторной работы не допускается изменять положение масштабного переключателя осциллографа. Измерить и записать в табл. 6.2 координаты вершины гистерезисного цикла: xm, ym (координаты вершины ...
0 комментариев