Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Лабораторная работа №3
Тема: Синтаксический анализ
Цель работы: Разработка синтаксического анализатора на основе грамматики.
Теоретическая часть
Основная проблема предсказывающего разбора - определение правила вывода, которое нужно применить к нетерминалу. Рассмотрим процесс предсказывающего разбора (сверху-вниз) с точки зрения построения дерева разбора. Вначале дерево состоит только из одной вершины, соответствующей аксиоме S. В этот момент по первому символу входного потока предсказывающий анализатор должен определить правило S -> X1X2..., которое должно быть применено к S. Затем необходимо определить правило, которое должно быть применено к X1, и т.д., до тех пор, пока в процессе такого построения сентенциальной формы, соответствующей левому выводу, не будет применено правило Y -> a... . Этот процесс затем применяется для следующего самого левого нетерминального символа сентенциальной формы.
На рис.4.1. приведена структура предсказывающего анализатора, который определяет очередное правило из таблицы. Такую таблицу множно построить непосредственно из грамматики.
Рис. 4.1. Структура анализатора
Таблично-управляемый предсказывающий анализатор имеет входной буфер, таблицу анализа и выход. Входной буфер содержит распознаваемую строку, за которой следует $ - правый концевой маркер, признак конца строки. Магазин содержит последовательность символов грамматики с $ на дне. Вначале стек содержит начальный символ грамматики на верхушке и $ на дне. Таблица анализа - это двумерный массив M[A,a] , где A - нетерминал, и a - терминал или символ $.
Анализатор управляется программой, которая работает следующим образом. Она рассматривает X - символ на верхушке стека и a - текущий входной символ. Эти два символа определяют действие анализатора. Имеются три возможности.
Поведение анализатора может быть описано в терминах конфигураций автомата разбора.
Нерекурсивный предсказывающий анализ.
Repeat X := верхний символ стека;
if X - терминал или $
then if X = InSym
then удалить X из стека;
InSym := очередной символ;
else error()
end
else /*X = нетерминал*/
if M[X,InSym]=X -> Y1Y2...Yk
then удалить X из стека;
поместить Yk, Yk-1,...,Y1 в стек (Y1 на верхушку);
вывести правило X -> Y1Y2...Yk
else error() /*вход таблицы M пуст*/
end
end
Until X = $ /*стек пуст*/
Вначале анализатор находится в конфигурации, в которой стек содержит S$ , (S - начальный символ грамматики), во входном буфере w$ (w - входная цепочка), переменная InSym содержит первый символ входной строки. Программа, использующая таблицу анализатора M для осуществления разбора, изображена на рис.3.3.
Пример. Рассмотрим грамматику арифметических выражений:
Таблица предсказывающего анализатора для нее приведена на рисунке. Здесь пустые клетки - входы ошибок. Непустые дают правила, по которым делается развертка нетерминала.
Рис. 4.2. Управляющая таблица
При входе id+id*id предсказывающий анализатор совершает последовательность шагов, изображенную на рис. 4.3. Если внимательно проанализировать действия анализатора, то видно, что он осуществляет левый вывод, т.е. правила применяются в соответствии с левым выводом. За уже просмотренными входными символами следуют символы грамматики в стеке (сверху вниз), что соответствует левым сентенциальным формам вывода. Дерево разбора приведено на рис. 4.4.
Рис. 4.3. Моделирование работы распознавателя
Рис. 4.4. Дерево разбора
Выполнение работы
СА должен разрабатываться как программа, параметром которой является КС – грамматика некоторого конкретного языка, языковые конструкции которого и будут подвергаться языковому анализу.
Стиль реализации СА и язык программирования выбрать самостоятельно.