Министерство образования Российской Федерации
Саратовский государственный технический университет
Построение детерминированного синтаксического
анализатора.
методические указания к выполнению лабораторной
работы по курсу «Теория вычислительных процессов
структур» для студентов специальности ПВС
Составил доцент кафедры ПВС
Сайкин А.И.
Саратов, 2001 г.
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}.
PAGE 2
PAGE 4
Нашли опечатку? Выделите и нажмите CTRL+Enter
