Пред.Страница  След.Страница   Раздел   Содержание 

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>) = {)}.
Таблица переходов, построенная по функциям ВПОСЛЕ, изображается так:
Таблица 3.3
<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, получаем:
Таблица 3.4
<E>  <T>  +  (  )  i 
<Ex>     +      
<Ey>     +   )  
<T1>            
<T2>            
+   <T1>   (   i
( <Ey> <T2>   (   i
)            
h0 <Ex> <T2>   (   i
i            
Учитывая состав множеств, обозначенных <Ex> и <Ey>, построим таблицу действий искомого распознавателя.
Таблица 3.5
 
^
+
( 
) 
i 
Ex
 D
П 
П 
П 
П 
Ey
 О
П
П 
П 
П 
T1
С (1) 
 С (1)
С (1) 
С (1)
С (1) 
T2
 С (2)
 С (2)
С (2) 
С (2)
С (2) 
+
О
П 
П
П 
П
i
 С (4)
 С (4)
С (4) 
С (4) 
С (4) 
(
О
П 
П
П 
П
)
С (3) 
 С (3)
С (3) 
С (3) 
С (3) 
h0
О
П 
П
П 
П
Построенный распознаватель является эквивалентным недетерминированному распознавателю, но эти распознаватели имеют разные состояния. Следовательно, им должны соответствовать эквивалентные, но не одинаковые грамматики. Такое различие должно отразиться в операциях сворачивания. В рассматриваемом случае операция Свертка(1) должна учитывать, что недетерминированному распознавателю соответствует грамматика с правилами   <E>® <Ex> + <T> и <E> ® <Ey> + <T>.
Пред.Страница  След.Страница   Раздел   Содержание