🗊Презентация Методы нисходящего синтаксического анализа

Методы нисходящего синтаксического анализа

Применяемый класс грамматик Контекстно-свободные грамматики Левая часть правила – нетерминальный символ, правая часть – произвольная строка a -> v, где a из N, v из A* Порождаемые языки – контекстно-свободные языки Механизм распознавания – автоматы с магазинной памятью

Нисходящий рекурсивный алгоритм Пусть имеется входная лента, содержащая строку символов в алфавите T. Строка заканчивается специальным символом >. N ={L, E, F, T, P, Q} T = { x, +, *, (, ), > } Правила вывода: L -> E Q E -> T F E -> T F -> + E F -> * T T -> x T -> ( E P P -> ) Q -> > Исходный символ – L Построить алгоритм нисходящего разбора данной строки

Основные множества, управляющие синтаксическим разбором для каждого нетерминального символа построим множества терминальных символов, которые могут за ними следовать fin(E) = { ), > } fin (F) = { ), > } fin(T) = { ), > } Для каждого правила вывода множество символов, с которых может начинаться выводимая из него строка beg (L -> E >) = {x, ( } beg (E -> T F) = { x, ( } dir(E -> TF) = first(F)= { +, * } beg (E -> T) = {x , ( } dir (E -> T) = fin(T) = { ), > } beg (F -> + E) = { + } beg (F -> * T) = { * } beg (T -> x) = { x } beg (T -> ( E P} = { ( } beg (P -> ) ) = { ) }

Последовательность грамматического разбора LL(1) L (1) L -> E > E Q (2) E -> T F dir = + T F Q (6) T -> x a F Q (4) F -> + E a + E Q (2) E -> T F dir = * a + T F Q (6) T -> x a + b F Q (5) F -> * T a + b * T Q (7) T -> ( E P a + b * ( E P Q (2) E -> T F dir = + a + b * ( T F P Q (6) T -> x a + b * ( c F P Q (4) F -> + E a + b * ( c + E P Q (2) E -> T F dir = * a + b * ( c + T F P Q (6) T -> x a + b * ( c + d F P Q (5) F -> * T a + b * ( c + d * T P Q (6) T -> x a + b * ( c + d * e P Q (8) P -> ) a + b * ( c + d * e ) Q (9) Q-> > a + b * ( c + d * e ) >

Ограничения на КС-грамматику, чтобы она была LL(1) Грамматика не должна содержать правил вида: A->Bu, B->Cv, C->Aw, то есть лево рекурсивных цепочек вывода Для любых двух правил с одинаковой левой частью должно выполняться одно из двух следующих правил: beg(A->v) & beg(A->w) == null то есть правла должны различаться по первому выводимому терминальному символу Если это не так, dir(A->v) & dir(A->w) == null, то есть правила должны различаться по второму терминальному символу, выводимому из строк v и w

Дополнительное ограничение В грамматику должны входить только правила следующего вида: N -> u где u из N* N -> tu где t из T и u из N* Например: Из правила T -> (E) следует сделать 2 правила: T -> (ER R -> ) где R – новый нетерминальный символ

Порядок работы В стек помещаем аксиому На входную ленту – строку, подлежащую распознаванию Выбираем самый левый нетерминал N в стеке и самый левый символ x на входной ленте и по этой паре принимаем решение: если существует правило, N->u однозначно определяемое парой N, x, то: если u = xv, то заменяем в стеке N на xv и удаляем символ x из вх ленты если u начинается с нетерминала или u – пустая строка, то только заменяем N на u Если пара N, x не однозначно определяют правило замены, то привлекаем След символ Если не находится правила по паре N, x то ошибка Критерий правильности распознавания: входная лента пуста в стеке – копия входной строки