Оцените презентацию от 1 до 5 баллов!
Тип файла:
ppt / pptx (powerpoint)
Всего слайдов:
8 слайдов
Для класса:
1,2,3,4,5,6,7,8,9,10,11
Размер файла:
120.50 kB
Просмотров:
53
Скачиваний:
0
Автор:
неизвестен
Слайды и текст к этой презентации:
№1 слайд![Методы нисходящего](/documents_6/1dfa53cae53601d1d0fd40b766cdff46/img0.jpg)
Содержание слайда: Методы нисходящего синтаксического анализа
№2 слайд![Применяемый класс грамматик](/documents_6/1dfa53cae53601d1d0fd40b766cdff46/img1.jpg)
Содержание слайда: Применяемый класс грамматик
Контекстно-свободные грамматики
Левая часть правила – нетерминальный символ, правая часть – произвольная строка
a -> v, где a из N, v из A*
Порождаемые языки – контекстно-свободные языки
Механизм распознавания – автоматы с магазинной памятью
№3 слайд![Нисходящий рекурсивный](/documents_6/1dfa53cae53601d1d0fd40b766cdff46/img2.jpg)
Содержание слайда: Нисходящий рекурсивный алгоритм
Пусть имеется входная лента, содержащая строку символов в алфавите 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
Построить алгоритм нисходящего разбора данной строки
№4 слайд![Основные множества,](/documents_6/1dfa53cae53601d1d0fd40b766cdff46/img3.jpg)
Содержание слайда: Основные множества, управляющие синтаксическим разбором
для каждого нетерминального символа построим множества терминальных символов, которые могут за ними следовать
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 -> ) ) = { ) }
№5 слайд![Последовательность](/documents_6/1dfa53cae53601d1d0fd40b766cdff46/img4.jpg)
Содержание слайда: Последовательность грамматического разбора 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 ) >
№6 слайд![Ограничения на КС-грамматику,](/documents_6/1dfa53cae53601d1d0fd40b766cdff46/img5.jpg)
Содержание слайда: Ограничения на КС-грамматику, чтобы она была LL(1)
Грамматика не должна содержать правил вида: A->Bu, B->Cv, C->Aw, то есть лево рекурсивных цепочек вывода
Для любых двух правил с одинаковой левой частью должно выполняться одно из двух следующих правил:
beg(A->v) & beg(A->w) == null то есть правла должны различаться по первому выводимому терминальному символу
Если это не так, dir(A->v) & dir(A->w) == null, то есть правила должны различаться по второму терминальному символу, выводимому из строк v и w
№7 слайд![Дополнительное ограничение В](/documents_6/1dfa53cae53601d1d0fd40b766cdff46/img6.jpg)
Содержание слайда: Дополнительное ограничение
В грамматику должны входить только правила следующего вида:
N -> u где u из N*
N -> tu где t из T и u из N*
Например:
Из правила
T -> (E)
следует сделать 2 правила:
T -> (ER
R -> )
где R – новый нетерминальный символ
№8 слайд![Порядок работы В стек](/documents_6/1dfa53cae53601d1d0fd40b766cdff46/img7.jpg)
Содержание слайда: Порядок работы
В стек помещаем аксиому
На входную ленту – строку, подлежащую распознаванию
Выбираем самый левый нетерминал N в стеке и самый левый символ x на входной ленте и по этой паре принимаем решение:
если существует правило, N->u однозначно определяемое парой N, x, то:
если u = xv, то заменяем в стеке N на xv и удаляем символ x из вх ленты
если u начинается с нетерминала или u – пустая строка, то только заменяем N на u
Если пара N, x не однозначно определяют правило замены, то привлекаем След символ
Если не находится правила по паре N, x то ошибка
Критерий правильности распознавания:
входная лента пуста
в стеке – копия входной строки