 |
|
Описание алгоритма.
10. Построить пополненную грамматику G¢ для исходной грамматики G.
11. Вычислить отношения OBLOW для грамматических вхождений грамматики G¢.
12. Определить функции переходов g(Х) следующим образом:
· Построить таблицу, содержащую по одному столбцу для каждого символа из S È N È {e} и одной отроке для каждого грамматического вхождения грамматики G¢ и маркера дна. Элемент в строке, помеченной грамматическим вхождением Хi или маркером дна ^, и столбце, отмеченном символом грамматики Y, должен содержать все грамматические вхождения, для которых справедливо отношение Хi OBLOW Yj. Заметам, что некоторые элементы построенной таким образом таблицы могут содержать более одного грамматического вхождения, т.е. таблица может быть недетерминированной.
· Интерпретируя построенную таблицу как таблицу конечного автомата (состояния - грамматические вхождения и маркер дна (начальное состояние), а входные символы - символы из S È N È {e}), определить тип автомата: детерминированный или недетерминированный. Недетерминированный автомат преобразовать в эквивалентный ему детерминированный автомат.
· Определить магазинный алфавитVp так, чтобы каждому состоянию детерминированного конечного автомата соответствовал ровно один магазинный символ.
В качестве символов алфавита Vp можно использовать любые символы, не являющиеся символами грамматики G¢Для сохранения наглядности цепочек, представимых магазином, будем считать, что символы из Vp совпадают по написанию с соответствующими грамматическими вхождениями. Если магазинный символ представляет множество грамматических вхождений, то индексы магазинных символов будем обозначать строчными латинскими буквами.
· Заменить совокупности грамматических вхождений, отмечающих состояния автомата, соответствующими символами из Vp.
Полученная таблица представляет собой таблицу функций переходов g(X) LR(0)-анализатора, причем элементы таблицы, соответствующие переходу в пустое множество состояний, имеют значение ОШИБКА.
4. Определить функции действия f(a) для всех магазинных символов, каждому из которых соответствует одна строка таблицы. Количество столбцов таблицыf(a) определяется количеством символов множества S È{e}. Элементы таблицы f(a) определяются следующим образом.
· Если магазинному символу Т соответствует единственное вхождение S0, то в строке, отмеченной символом Т, f(e) = ДОПУСК, а все остальные элементы – ОШИБКА.
· Если магазинному символу Т соответствует только одно грамматическое вхождение Xi, являющееся самым правым вхождением в i-е правило вывода грамматики G, то все элемента строки, помеченной Т, имеют значение (СВЕРТКА, i).
· Если магазинному символу Т соответствует маркер дна магазина ^ или все грамматические вхождения, представляемые символом Т, не являются самыми правыми в своих правилах, то в строке, отмеченной Т, f(e) = ошибка, а значения остальных элементов – ПЕРЕНОС.
· Если множество вхождений, соответствующее магазинному символу Т, содержит начальное вхождение S0 и хотя бы еще одно вхождение, отличное от S0, которое не является самым правым в своем правиле, то в строке, отмеченной Т, f(e) = ДОПУСК, а значение всех остальных элементов – ПЕРЕНОС.
Если имеется множество грамматических вхождений, не удовлетворяющих перечисленным выше условиям, то G не является LR(0)-грамматикой.
Если построение f(a) закончено успешно, то грамматика является LR(0)-грамматикой, а таблица, полученная объединением таблиц, задающих функции f(a)и g(X) – управляющей таблицей T LR(0)-анализатора.
Конец алгоритма
Построим управляющую таблицу LR(0)-анализатора для грамматики, имеющей следующие правила:
| (1) | E | à | E + T | (3) | T | à | (E) | |
| (2) | E | à | T | (4) | T | à | i |
Шаг 1. Определим пополненную грамматику для грамматики G:
G¢= (N È {S}, S, Р È {S à E}, S).
Шаг 2. Вычислим отношение OBLOW для грамматических вхождений грамматики G¢. Матрица отношения OBLOW имеет вид:
| E0 | E1 | +1 | T1 | T2 | (3 | E3 | )3 | i4 | |
| E0 | |||||||||
| E1 | |||||||||
| +1 | |||||||||
| T1 | |||||||||
| T2 | |||||||||
| (3 | |||||||||
| E3 | |||||||||
| )3 | |||||||||
| i4 | |||||||||
| ^ |
Шаг 3. Определим функции переходов g(X).
q Используя отношение OBLOW, построим таблицу переходов конечного (в данном случае недетерминированного) автомата:
| E | T | ( | ) | i | + | |
| E0 | ||||||
| E1 | +1 | |||||
| +1 | T1 | (3 | i4 | |||
| T1 | ||||||
| T2 | ||||||
| (3 | E1, E3 | T2 | (3 | i4 | ||
| E3 | )3 | |||||
| )3 | ||||||
| i4 | ||||||
| ^ | E0, E1 | T2 | (3 | i4 |
q Преобразуем недетерминированный автомат в эквивалентный ему детерминированный автомат, таблица переходов которого будет иметь вид:
| E | T | ( | ) | i | + | |
| {^} | (E0, E1} | {T2} | {(3} | {i4} | ||
| {E0, E1} | {+1} | |||||
| {T2} | ||||||
| {(3} | { E1, E3} | {T2} | {(3} | {i4} | ||
| {i4} | ||||||
| {+1} | {T1} | {(3} | {i4} | |||
| {E1, E3} | {)3} | {+1} | ||||
| {T1} | ||||||
| {)3} |
q Определим множество магазинных символов:
| {E0, E1 } | {E1, E3 } | {^} | {T2} | {(3} | {i4} | {+1} | {T1} | {)3} | |
| Vp | Ex | Ey | ^ | T2 | (3 | i4 | +1 | T1 | )3 |
q Тогда функции переходов g(Х) LR(0)-анализатора для грамматики G имеет вид:
| g(X) | E | T | ( | ) | i | + |
| ^ | Ex | T2 | (3 | i4 | ||
| Ex | +1 | |||||
| T2 | ||||||
| (3 | Ey | T2 | (3 | i4 | ||
| i4 | ||||||
| +1 | T1 | (3 | i4 | |||
| Ey | )3 | +1 | ||||
| T1 | ||||||
| )3 |
Шаг 4. Определим функции действияf(a). Построим таблицу, содержащую по одной строке для каждого магазинного символа и одному столбцу для каждого символа a Î (S È {e}).
Для строки таблицы, отмеченной символом ^, соответствующее множество грамматических вхождений состоит из единственного символа ^, поэтому в этой отроке f(e) = ОШИБКА, а значения остальных элементов – ПЕРЕНОС.
Множество грамматических вхождений, соответствующих магазинному символу Еx, содержит два элемента: Е0 и Е1. Так как в это множество входит начальное вхождение E0, а вхождение Е1 не является самым правым в правиле грамматики (1), то f(e) = ДОПУСК, а остальные элементы строки, отмеченные символом Еx, имеют значение ПЕРЕНОС.
Магазинному символу Т2 соответствует единственное грамматическое вхождение Т2, которое является самым правым в правиле вывода (2) грамматики. Следовательно, значение всех элементов строки, помеченной Т2, – (СВЕРТКА, 2).
Поступая подобным образом для остальных строк, получим таблицу функций переходов f(a):
| f(a) | ( | ) | i | + | e |
| ^ | П | П | П | П | |
| Ex | П | П | П | П | Д |
| T2 | С,2 | С,2 | С,2 | С,2 | С,2 |
| (3 | П | П | П | П | |
| i4 | С,4 | С,4 | С,4 | С,4 | С,4 |
| +1 | П | П | П | П | |
| Ey | П | П | П | П | |
| T1 | С,1 | С,1 | С,1 | С,1 | С,1 |
| )3 | С,3 | С,3 | С,3 | С,3 | С,3 |
Поскольку при построении функции переходов f(a)не возникло конфликтных ситуаций, рассмотренная грамматика является LR(0)-грамматикой. Объединив функции g(X) и f(a) в одну таблицу, получим для управляющую таблицу T LR(0)-анализатора.