М.Ю. Харламов, ВНУ им. В.Даля, 2010

Восходящие распознаватели выполняют построение дерева вывода снизу вверх (от листьев к корню). Результатом их работы является правосторонний вывод Тема 6. Восходящий синтаксический анализ Рассмотрим грамматику S а АВе A Аbc | b В d Предложение abbcde сводится к S с помощью следующих шагов: abbcde (b A) aAbcde(Abc A) aAde(d B) aABe(aABe S) S Рассмотрим грамматику S а АВе A Аbc | b В d Предложение abbcde сводится к S с помощью следующих шагов: abbcde (b A) aAbcde(Abc A) aAde(d B) aABe(aABe S) S

LR(k)-анализ - технология восходящего синтаксического анализа L означает сканирование входного потока слева направо R построение обращенных правых порождений k число входных символов LR-анализ - наиболее мощный метод анализа без возвратов типа сдвиг-свертка LR-анализаторы могут быть построены для практически всех конструкций языков программирования класс грамматик, которые могут быть проанализированы LR-методом, строго включает класс грамматик, которые могут быть проанализированы анализаторами типа LL(1) Тема 6. Восходящий синтаксический анализ

LR-анализатор SmSm XmXm a1a1 …aiai … Действия Стек Входной буфер Выходной поток anan $ Переходы … S0S0 S m-1 X m-1 Конфигурацией LR-анализатора называется пара - содержимое стека и непросмотренная часть входного потока: (s 0 X 1 s 1 X 2 s 2... X m s m, a i a i+1... a n $) X i - символ грамматики S i – символ состояния

Действия Исходя из значений s m и a i программа выполняет действие согласно таблице Действия[s m, a i ]: 1) сдвиг s (shift), где s - символ состояния В стек помещаются входной символ a i и символ очередного состояния s, определяемый Действия[s m, a i ]. Текущим входным символом становится a i+1 2) свертка A γ (reduce) Анализатор сначала удаляет из магазина 2r символов (r символов состояния и r символов грамматики, где r - длина γ), так что на верхушке оказы­вается состояние s m-r. Затем анализатор помещает в стек A -левую часть правила вывода, и s - символ состояния, определяемый Переходы[s m-r,A]. Текущий входной символ не меняется. 3) успех (accept) Разбор успешно завершен 4) ошибка (error) Выполнение действий по диагностике и восстановлению ошибки Тема 6. Восходящий синтаксический анализ

Ситуация Ситуация - множество правил грамматики, записанных с учетом положения считывающей головки автомата Начальная ситуация: {S 1 ;S 2 ; …S n }, где S целевой символ грамматики G, и в G входят правила S 1 | 2 | … n. Правила построения последовательности LR(0) ситуаций: Если в ситуации есть правило вида А B, то в нее должны быть добавлены B 1 ; B 2 ; … B n (если есть правила B 1 | 2 … n ) Если ситуация содержит правила вида А x, где х - произвольный символ, то из нее может быть построена но­вая ситуация, содержащая правила вида А x (ситуация проистекает из исходной на основании x) Тема 6. Восходящий синтаксический анализ А,В VN,, (VN VT)* А,В VN,, (VN VT)*

T Построение управляющей таблицы T: каждой строке Т i, в таблице Т соответст­вует ситуация R i в последовательности ситуаций; для всех ситуаций R i выполняется следующее: если в R i есть правило вида S, где S це­левой символ грамматики, то в строке Т i графы «Действия» записываем «успех»; если в R i есть правило вида A, (А не является целевым символом) и грамматика содержит правило вида A, с номером m, то в строке Т i графы «Действия» записываем число т (свертка по правилу с номером m); если в R i есть правила вида А x, где х - произвольный символ, то в графе «Действия» строки Т i записываем «сдвиг» если ситуация R j, проистекает из ситуации R i и связана с нею через символ х, то в графе «Переходы» в стро­ке Т i для символа х записываем число j клетки таблицы T, оставшиеся пустыми после заполнения, соответствуют состоянию «ошибка» Тема 6. Восходящий синтаксический анализ А VN,, (VN VT)* x (VN VT) А VN,, (VN VT)* x (VN VT)

Рассмотрим грамматику G({a,b}, {S}, {S aSS | b}, S). Пополненная грамматика - G({a,b}, {S, S}, { S S, S aSS | b}, S) Тема 6. Восходящий синтаксический анализ R0: S S S aSS S b R0: S S S aSS S b R1: S S R3: S b R2: S a SS S aSS S b R2: S a SS S aSS S b R4: S aS S S aSS S b R4: S aS S S aSS S b R5: S aSS S b a S a b S b Действия Переходы Sab 0Сдвиг 123 1Успех, 1 2Сдвиг 423 3Свертка, 3 4Сдвиг 523 5Свертка, 2

Начальная ситуация: {S 1 /$;S 2 /$; … S n /$}, где S целевой символ грамматики G, и в G входят правила S 1 | 2 | … n ; а VT - аванцепочка Правила построения последовательности LR(1) ситуаций: Если в ситуации есть правило вида А Bb /a, и правила B 1 | 2 … n входят в G, то в ситуацию добавляются правила B 1 /b; B 2 /b; … B n /b Если в ситуации есть правило вида АB/а, и правила B 1 | 2 … n входят в G, то в ситуацию добавляются правила B 1 /a; B 2 /a; … B n /a Если в ситуации есть правило вида А BC /a, и правила B 1 | 2 … n входят в G, то в ситуацию добавляются правила B 1 /c; B 2 /c; … B n /c, где c FIRST(C) Если ситуация содержит правила вида А x /a, где х - произвольный символ, то из нее может быть построена но­вая ситуация, содержащая правила вида А x /a (ситуация проистекает из исходной на основании x) Тема 6. Восходящий синтаксический анализ А,В,C VN,, (VN VT)* x (VN VT) a,b,c VT А,В,C VN,, (VN VT)* x (VN VT) a,b,c VT

T Построение управляющей таблицы T: для всех ситуаций R i выполняется следующее: если в R i есть правило вида S /a, где S це­левой символ грамматики, то в строке Т i графы «Действия» для символа a записываем «успех»; если в R i есть правило вида A /a, (А не является целевым символом) и грамматика содержит правило вида A, с номером m, то в строке Т i графы «Действия» для символа a записываем число т (свертка по правилу с номером m); если в R i есть правила вида А x /a, где х - произвольный символ, то в графе «Действия» строки Т i для a записываем «сдвиг» если ситуация R j, проистекает из ситуации R i и связана с нею через символ х, то в графе «Переходы» в стро­ке Т i для символа х записываем число j клетки таблицы T, оставшиеся пустыми после заполнения, соответствуют состоянию «ошибка» Тема 6. Восходящий синтаксический анализ

Рассмотрим грамматику G({a,b}, {S}, {S SaSb | e}, S). Пополненная грамматика - G({a,b}, {S, S}, { S S, S SaSb | e}, S) Тема 6. Восходящий синтаксический анализ R0: S S/$ S SaSb/$ S /$ S SaSb/a S /a R0: S S/$ S SaSb/$ S /$ S SaSb/a S /a R1: S S /$ S S aSb/$ S S aSb/a R1: S S /$ S S aSb/$ S S aSb/a R2: S Sa Sb/$ S Sa Sb/a S SaSb/b S /b S SaSb/a S /a R2: S Sa Sb/$ S Sa Sb/a S SaSb/b S /b S SaSb/a S /a R3: S SaS b/$ S SaS b/a S S aSb/b S S aSb/a R3: S SaS b/$ S SaS b/a S S aSb/b S S aSb/a R4: S Sa Sb/b S Sa Sb/a S SaSb/b S SaSb/a S /b S /a R4: S Sa Sb/b S Sa Sb/a S SaSb/b S SaSb/a S /b S /a R5: S SaSb /$ S SaSb /a R5: S SaSb /$ S SaSb /a R7: S SaSb /b S SaSb /a R7: S SaSb /b S SaSb /a R6: S SaS b/b S SaS b/a S S aSb/b S S aSb/a R6: S SaS b/b S SaS b/a S S aSb/b S S aSb/a S S a b a S a b

Тема 6. Восходящий синтаксический анализ Действия Переходы abS ab$ 0Свертка, 3 1 1Сдвиг Успех, 12 2Свертка, 3 Сдвиг Свертка, 3 6 5Свертка, 2 6Сдвиг 47 7Свертка, 2

LALR(1)-анализатор можно построить на основе множества LR(1)-ситуаций, имеющих одно и то же ядро (core), т.е. отличающимися только аванцепочкой: 1. Строится система множеств LR(1)-ситуаций 2. Для каждого ядра, имеющегося среди множества LR(1)-ситуаций, находим все мно­жества, имеющие это ядро, и заменяем эти множества их объединением 3. Графа «Действия» для LALR(1) строится аналогично LR(1) 4. Графа «Переходы» для LALR(1) строится следующим образом: 1. Если J - объединение одного или не­скольких множеств LR(1)-ситуаций (J = R 1 R 2 … R k ), тогда «Переходы»(J, X) = K, где K - объединение всех множеств ситуаций, имеющих то же ядро, что и goto(R i, X). Тема 6. Восходящий синтаксический анализ

Рассмотрим грамматику G({a,b}, {S}, {S SaSb | e}, S). Пополненная грамматика - G({a,b}, {S, S}, { S S, S SaSb | e}, S) Тема 6. Восходящий синтаксический анализ R0: S S/$ S SaSb/a/$ S /a/$ R0: S S/$ S SaSb/a/$ S /a/$ R1: S S /$ S S aSb/a/$ R1: S S /$ S S aSb/a/$ R24: S Sa Sb/a/b/$ S SaSb/a/b S /a/b R24: S Sa Sb/a/b/$ S SaSb/a/b S /a/b S S a b R36: S SaS b/a/b/$ S S aSb/a/b/$ R36: S SaS b/a/b/$ S S aSb/a/b/$ R57: S SaSb /a/b/$ R57: S SaSb /a/b/$ a Действия Переходы abS ab$ 0Свертка, 3 1 1Сдвиг Успех, Свертка, Сдвиг Свертка, 2

S prog L end. L O | L; O | L; B B or C | C D G | not D G E E | E=E | (B) K G then O M K else O Q G do O O if M | if K| begin L end | while Q | c:=E E E-F | E+F | E*F|E/F| F (E) | c S prog L end. L O | L; O | L; B B or C | C D G | not D G E E | E=E | (B) K G then O M K else O Q G do O O if M | if K| begin L end | while Q | c:=E E E-F | E+F | E*F|E/F| F (E) | c