Лабораторная работа 3 Тема- Синтаксический анализ Цель работы- Разработка синтаксического анализат
Работа добавлена на сайт samzan.net:
Лабораторная работа №3
Тема: Синтаксический анализ
Цель работы: Разработка синтаксического анализатора на основе грамматики.
Теоретическая часть
Основная проблема предсказывающего разбора - определение правила вывода, которое нужно применить к нетерминалу. Рассмотрим процесс предсказывающего разбора (сверху-вниз) с точки зрения построения дерева разбора. Вначале дерево состоит только из одной вершины, соответствующей аксиоме S. В этот момент по первому символу входного потока предсказывающий анализатор должен определить правило S -> X1X2..., которое должно быть применено к S. Затем необходимо определить правило, которое должно быть применено к X1, и т.д., до тех пор, пока в процессе такого построения сентенциальной формы, соответствующей левому выводу, не будет применено правило Y -> a... . Этот процесс затем применяется для следующего самого левого нетерминального символа сентенциальной формы.
На рис.4.1. приведена структура предсказывающего анализатора, который определяет очередное правило из таблицы. Такую таблицу множно построить непосредственно из грамматики.
Рис. 4.1. Структура анализатора
Таблично-управляемый предсказывающий анализатор имеет входной буфер, таблицу анализа и выход. Входной буфер содержит распознаваемую строку, за которой следует $ - правый концевой маркер, признак конца строки. Магазин содержит последовательность символов грамматики с $ на дне. Вначале стек содержит начальный символ грамматики на верхушке и $ на дне. Таблица анализа - это двумерный массив M[A,a] , где A - нетерминал, и a - терминал или символ $.
Анализатор управляется программой, которая работает следующим образом. Она рассматривает X - символ на верхушке стека и a - текущий входной символ. Эти два символа определяют действие анализатора. Имеются три возможности.
- Если X=a=$ , анализатор останавливается и сообщает об успешном окончании разбора.
- Если X=a , анализатор удаляет X из стека и продвигает указатель входа на следующий входной символ.
- Если X - нетерминал, программа заглядывает в таблицу M[X,a] . По этому входу хранится либо правило для X, либо ошибка. Если, например, M[X,a]=(X -> UVW) , анализатор заменяет X на верхушке стека на WVU {на верхушке U }. Будем считать, что анализатор в качестве выхода просто печатает использованные правила вывода. Если M[X,a]=error , анализатор обращается к подпрограмме анализа ошибок.
Поведение анализатора может быть описано в терминах конфигураций автомата разбора.
Нерекурсивный предсказывающий анализ.
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. Дерево разбора
Выполнение работы
- Разработать программу (синтаксический анализатор - СА), моделирующую вывод в КС – грамматике.
СА должен разрабатываться как программа, параметром которой является КС – грамматика некоторого конкретного языка, языковые конструкции которого и будут подвергаться языковому анализу.
Стиль реализации СА и язык программирования выбрать самостоятельно.
- Провести тестирование СА для чего:
- по заданному варианту входного языка сформировать (вручную или с помощью Лексического анализатора ) лексемы, которые должны играть в грамматике роль терминальных символов;
- по заданному варианту входного языка составить грамматику (без символов действий), в соответствии с которой будет производиться тестирование входных цепочек;
- инициализировать программу СА разработанной грамматикой;
- для заданной языковой конструкции получить допуск или не допуск на основании разбора СА.
- Отчетом по лабораторной работе является:
- грамматика для данного типа языковых конструкций;
- демонстрация тестовых примеров.
2. Стены и башни Московского Кремля
3. тематический и именной каталоги.
4. лейтенант служби цивільного захисту М
5. Петербурге и на Урале много их в Казахстане и Узбекистане.
6. Жизнь и труды Аристотеля
7. Во всём сомневаться девиз- Дж
8. Бизнес-план торгового предприятия
9. Джуз основная часть чего ответвление
10. Система управления временем БФранклина
11. Пусть в системе в точках с координатами в моменты времени происходят два события
12. Кембриджская и американская школы Вклад А Маршалла Дж Кларка А Пигу в экономическую теорию
13. S Pemberton Compny en 1879 V~t~rn de cette guerre u cours de lquelle il est bless~ John Pemberton contrct~ une ddiction ~ l morphine pour soulger l douleur due ~ ses blessures
14. Одесских Новостей Пушкинская ул дом 11 1893 год Предисловие Во всех умственных занятиях
15. Активы в финансовом менеджменте
16. Пояснительная записка Студент УБ 1102
17. Школы менеджмента
18. Проекция Гаусса
19. Лекция 1 Предмет и задачи интернетжурналистики
20. Вариант 19 В задачах 19 найти неопределённые интегралы ответ проверить дифференцированием