3.12.2. Пример построения
LR(0)-распознавателя
В качестве иллюстрации применения описанной процедуры рассмотрим построение распознавателя для следующей грамматики:
Г 3. 14 :Функции ВПЕРВ и ВПОСЛЕ для этой грамматики имеют вид:
1. <E> ® <E1> + <T1>
2. <E> ® <T2>
3. <T> ® (<E3>)
4. <T> ® i
ВПЕРВ(<E1>)={<E1>,<T2>,(,i}, | ВПОСЛЕ(<E1>) = {+}, |
ВПЕРВ(<T1>)={<T1>,(,i}, | ВПОСЛЕ(<T1>) = f, |
ВПЕРВ(<T2>)={<T2>,(,i}, | ВПОСЛЕ(<T2>) = f, |
ВПЕРВ(+) = {+}, | ВПОСЛЕ(+) = {<T1>,(,i}, |
ВПЕРВ(i) = {i}, | ВПОСЛЕ(i) = f, |
ВПЕРВ(() = {(}, | ВПОСЛЕ(()={<E1>,<E3>,<T2>,(,i}, |
ВПЕРВ()) = {)}, | ВПОСЛЕ()) = f, |
ВПЕРВ(<E3>)={<E3>,<E1>,<T2>,(,i}, | ВПОСЛЕ(<E0>) = f, |
ВПОСЛЕ(h0)={<E0>,<E1>,<T2>,(,i}, | |
ВПОСЛЕ(<E3>) = {)}. |
Таблица переходов, построенная по функциям ВПОСЛЕ, изображается так:
<E> | <T> | + | ( | ) | i | |
---|---|---|---|---|---|---|
<E0> | ||||||
<E1> | + | |||||
<T1> | ||||||
<T2> | ||||||
+ | <T1> | ( | i | |||
i | ||||||
( | <E1><E3> | <T2> | ( | i | ||
) | ||||||
h0 | <E1><E0> | <T2> | ( | i | ||
<E3> | ) |
Полученная таблица переходов является недетерминированной. После преобразования таблицы, обозначая множество состояний (<E0>, <E1>) = <Ex> и
(<E1>, <E3>) = <Ey> и полагая, что начальным состоянием является h0, получаем:
<E> | <T> | + | ( | ) | i | |
---|---|---|---|---|---|---|
<Ex> | + | |||||
<Ey> | + | ) | ||||
<T1> | ||||||
<T2> | ||||||
+ | <T1> | ( | i | |||
( | <Ey> | <T2> | ( | i | ||
) | ||||||
h0 | <Ex> | <T2> | ( | i | ||
i |
Учитывая состав множеств, обозначенных <Ex> и <Ey>, построим таблицу действий искомого распознавателя.
|
|
|
|
|
|
---|---|---|---|---|---|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Построенный распознаватель является эквивалентным недетерминированному распознавателю, но эти распознаватели имеют разные состояния. Следовательно, им должны соответствовать эквивалентные, но не одинаковые грамматики. Такое различие должно отразиться в операциях сворачивания. В рассматриваемом случае операция Свертка(1) должна учитывать, что недетерминированному распознавателю соответствует грамматика с правилами <E>® <Ex> + <T> и <E> ® <Ey> + <T>.