Синтаксический анализ. Метод рекурсивного спуска
Выбери формат для чтения
Статья: Синтаксический анализ. Метод рекурсивного спуска
Загружаем конспект в формате docx
Это займет всего пару минут! А пока ты можешь прочитать работу в формате Word 👇
5. Синтаксический анализ. Метод рекурсивного спуска
Синтаксический анализатор – это часть компилятора, которая выполняет выявление синтаксических конструкций входного языка, анализ их корректности. Как правило, синтаксис языков программирования описывается с помощью КС-грамматик. В процессе работы синтаксический анализатор строит дерево разбора, корнем которого является аксиома, листьями - терминалы языка, а узлами – нетерминалы, причем для вершины А и ее потомков а1а2…ак в грамматике должно существовать правило А-> а1а2…ак.
В зависимости от метода грамматического разбора – восходящего или нисходящего, различают различные виды синтаксических анализаторов. К нисходящим анализаторам относятся анализатор, работающий по методу рекурсивного спуска (по методу синт.диаграмм), LL(k)-анализатор. К восходящим анализаторам относятся анализаторы предшествования, LR(k)-анализаторы. Все эти методы предназначены для грамматик, на правила которых введен ряд ограничений для упрощения анализа.
Рассмотрим метод СД, предназначенный для небольших языков программирования. Остальные методы – для больших языков.
Синтаксической диаграммой называется граф, содержащий вершины двух видов – прямоугольники для нетерминалов и скругленные блоки – для терминалов, и строящийся по правилам грамматики следующим образом:
1) каждому нетерминалу соответствует своя СД. Если есть правила А->A1| A2 | … | An, то диаграмма имеет вид:
А
2) для каждого правила А->a1a2…ak диаграмма имеет вид
А
Если построить диаграммы непосредственно по правилам грамматики, то их нельзя использовать для синтаксического анализа, так как они являются леворекурсивными и недетерминированными. В связи с этим СД необходимо преобразовать. Рассмотрим способы преобразования СД.
Преобразование СД
1. Если ветви СД при разветвлениях имеют одинаковые блоки в начале или окончании, то их можно вынести:
А
A
2. Подстановка диаграммы в диаграмму. Это имеет смысл делать для сокращения количества СД, если такая подстановка не увеличивает сложность новой диаграммы.
3. Устранение левой рекурсии.
А
Правило А->A |
Для устранения левой рекурсии рассмотрим вывод А=>A=>A=>*. Обозначим * через T.
A
T
Выполнив подстановку диаграммы в диаграмму, получим:
А
Если цепочка =, то возможны два типа диаграмм:
или
Диаграмма второго типа используется только в том случае, если не несет семантической нагрузки, например, если это запятая в списке идентификаторов. Если это операция, соединяющая два операнда – то нужна диаграмма первого типа. Устранение правой рекурсии осуществляется аналогично.
Разметка ветвей СД. Функции firstk(),followk()
Для того чтобы запрограммировать точки ветвления в СД, необходимо идентифицировать ветви диаграммы. Для этого используются специальные функции. Функции firstk() соответствует множество терминальных цепочек длины не более k, выводимых из цепочки . Функции followk() соответствует множество терминальных цепочек длины не более k, которые при выводе следуют за цепочкой .
firstk(A)={x| xVT* A*x (|x|=k |x|xR (|x|=k |x|а1а2..аm.
Например:
S->while (V) O
O-> {P} | a=V;
P->PO | e
V->V+E | E
E-> a | c | (V)
Построим first1.
S
O
P
V
E
i=0
while
{ a
e
a c (
i=1
while
{ a
{ a e
a c (
a c (
i=2
while
{ a
{ a e
a c (
a c (
Для построения функции followk необходимо дополнить анализируемый текст k знаками конца #, а начинать анализ надо с цепочки S#k. Для S#k cтроятся всевозможные выводы длины k+1 вида a1Afa2, при этом цепочки f, следующие за А, и составляют функцию follow(A). Алгоритм основан на том, что в процессе вывода мы рассматриваем цепочки одинаковой длины k+1. Это означает, что грамматика для построения функции follow должна быть преобразована к эквивалентной неукорачивающей форме.
Для нашего примера
follow(S)= #
follow(O)= # }
follow(P)= } a {
follow(V)= ; ) +
follow(E)= ; ) +
Проще всего определять функции по диаграммам, нужно смотреть, с какой терминальной цепочки будет начинаться конструкция, соответствующая нетерминалу (это first), и какие терминальные цепочки будут при порождении находиться за нетерминалом (follow).
Программирование СД
Правила программирования СД:
1. Каждой СД А ставится в соответствие функция void A(void) { }
2. Ввести в проект кроме scanner модуль analis дополнить defs.h кодами синтаксических ошибок.
3. Функцию PrintError(int err) реализовать как switch по номеру ошибки, дополнив новыми кодами синтаксических ошибок по сравнению с лексическими ошибками сканера. Функция PrintError вызывается в тексте синтаксического анализатора в точках, где находится неверная лексема, причем в синтаксическом анализаторе, работающем до первой ошибки, эта функция должна вызывать завершение работы всей программы.
4. Если в диаграмме встретился нетерминальный элемент, то осуществляется вызов соответствующей функции.
5. Все переменные, используемые при программировании СД, должны быть локальными для соответствующей функции.
void S(void){int uk1,t;LEX l; … }
6. Если в СД терминальный символ, то его обработка, если он несет смысловую нагрузку, выглядит следующим образом:
t=Scaner(l);
if (t==<нужный тип>) {семант.обработка} else PrintError(код);
Выдача ошибки осуществляется в виде – «Ожидался тип …»
Если терминал не несет семантической нагрузки, то код анализатора:
t=Scaner(l);
if (t!=<нужный тип>) PrintError(код);
7. Если в диаграмме идут подряд блоки, то им при программировании соответствует последовательность обработки терминальных и нетерминальных символов.
8. Если в диаграмме имеется разветвление, и все они начинаются терминалами, то диаграмме соответствует код
t=Scaner(l);
if (t==) {реализ.ветви 1 без 1 терминала} else … if (t==) {реализ.ветви n без 1 терминала}
else PrintError(код);
В PrintError выдается ошибка «Ожидался один из first разветвления» или «неверная конструкция».
9. Если в диаграмме разветвление, и хотя бы 1 ветвь начинается нетерминалом, то для того, чтобы был корректный вход в функции, реализующие нетерминалы, необходимо в локальной переменной сохранять старое значение указателя (uk1=GetUk();) и восстановить его в начале каждой ветви, начинающейся нетерминалом. (SetUk(uk1))
10. Для диаграммы вида
возможны два случая. Если ветвь начинается терминалом, то
t=Scaner(l);
do {реализ.ветви без сканирования 1 терминала
uk1=GetUk();
t=Scaner(l);
} while (t==);
SetUk(uk1);
Если ветвь начинается с нетерминала, то
do {реализ.ветви
uk1=GetUk();
t=Scaner(l);
SetUk(uk1);
} while (t==);
11.
Если ветвь начинается нетерминалом
uk1=GetUk(); t=Scaner(l); SetUk();
while (t==)
{ ();
uk1=GetUk(); t=Scaner(l); SetUk();
}
Для терминального начала восстановление указателя выносится из цикла:
uk1=GetUk(); t=Scaner(l);
while (t==)
{ реализ.ветви без сканирования 1 терминала
uk1=GetUk(); t=Scaner(l);
}
SetUk(uk1);
12. В main вызвать функцию, соответствующую аксиоме.
