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

3.12.1. Построение таблиц распознавателя.
          Алгоритм работы распознавателя.
 

Для грамматических вхождений определим две функции ВПЕРВ и ВПОСЛЕ. Функция ВПЕРВ по аналогии с функцией ПЕРВ(Y) определяет множество грамматических вхождений, которые могут стоять на первом месте в цепочках, выводимых из Y. Это множество строится следующим образом: в него входит символ Y и все символы, начинающие промежуточные цепочки, выводимые из Y без применения аннулирующих правил. Формально вторая часть утверждения означает, что X О ВПЕРВ(Y), если 
     Y Ю* <L>b Ю Xab
и X является самым левым вхождением в правой части правила <L> ® Xa.

В качестве примера построим функции ВПЕРВ для символов следующей грамматики, не содержащей аннулирующих правил:

Г3. 13:
<I> ® a1<I12><I13>b1
<I> ® с2
Эти функции имеют следующий вид: 
     ВПЕРВ(a1) = {a1},
     ВПЕРВ(<I12>) = {<I12>, a1, с2},
     ВПЕРВ(<I13>) = {<I13>, a1, с2},
     ВПЕРВ(b1) = {b1},
     ВПЕРВ(<C2>) = {с2},
     ВПЕРВ(<I0>) = {<I0>, a1, с2}.
Функция ВПОСЛЕ(Y) является аналогом функции СЛЕД. Она определяет множество грамматических вхождений, которые могут встречаться непосредственно после Y в цепочках, выводимых из начального символа грамматики. Правило вычисления функции ВПОСЛЕ(Y) можно записать так: если в правой части некоторого правила после Y непосредственно следует Z, то 
     ВПОСЛЕ(Y) = ВПЕРВ(Z).
При построении распознавателей необходимо учитывать наличие маркера дна, поэтому, забегая вперед, сформулируем еще одно правило вычисления этой функции: если Y является маркером дна магазина, то 
     ВПОСЛЕ(h0) = ВПЕРВ(<I0>),
где <I0>—начальное вхождение.

Для грамматики Г3. 12функции ВПОСЛЕ имеют вид 

     ВПОСЛЕ(a1) = {<I12>, a1, с2},
     ВПОСЛЕ(<I12>) = {<I13>, a1, с2},
     ВПОСЛЕ(<I13>) = {b1},
     ВПОСЛЕ(b1) = Ж,
     ВПОСЛЕ(<C2>) = Ж,
     ВПОСЛЕ(<I0>) = Ж,
     ВПОСЛЕ(h0) = {<I0>, a1, с2}.
Согласно определению функции ВПОСЛЕ(Y) она определяет грамматические вхождения, которые могут следовать после вхождения Y в выводимых или сворачиваемых цепочках. Например, если очередным грамматическим вхождением является символ a1 и за ним должен следовать грамматический символ I, то по значению функции ВПОСЛЕ( a1 ) можно определить, что символу I в этом случае соответствует вхождение I12. Таким образом, при сворачивании  с помощью функции ВПОСЛЕ(Y) можно определить, какому грамматическому вхождению соответствует очередной грамматический символ сворачиваемой цепочки.
Если взять последовательность  грамматических символов,  то пользуясь функциями ВПОСЛЕ ей можно поставить в соответствие последовательность грамматических вхождений. В этом случае удобно рассматривать грамматические вхождения, как состояни конечного автомата, а грамматические символы, как входные воздействия. Смену состояний этого автомата можно представить в виде таблицы переходов, которая строится следующим образом.  Каждому грамматическому вхождению выделим одну строку таблицы, а каждому грамматическому символу—один столбец. Клетки таблицы заполняются элементами функций ВПОСЛЕM таким образом, что элемент XkО ВПОСЛЕ(Yj) заносится в клетку, находящуюся на пересечении строки Yj и столбца, отмеченного грамматическим символом X.

Таблица переходов распознавателя, построенная для рассматриваемой грамматики, имеет вид:

Таблица 3.1
a  b  <C>  <I>
a1 a1   <C2> <I12>
<I12> a1   <C2> <I13>
<I13>   b1    
b1        
<C2>        
h0 a1   <C2> <I0>
<I0>        
Эта таблица задает функцию

                        f(  Bij , X  ) = Xkl,
которая для текущего грамматического вхождения Bij  и очередного символа грамматики X определяет грпмматическое вхождение очередного символа Xkl.
Следует отметить, что при построении таблицы переходов в клетках таблицы могут оказаться по несколько грамматических вхождений соответствующих символов. Такая таблица является  недетерминированной, и ее нужно преобразовать в детерминированную таблицу с помощью приемов, использованных для преобразования таблиц конечных автоматов. В результате может получиться таблица, у которой строки отмечены множествами грамматических вхождений.

Построенная таблица переходов описывает смену состояний распознавателя, но она никак  не отражет в каких случаея  распознаватель должен выполнять действия переноса прочитанных символов в магазин и сворачивания. Если для хранения промежуточных цепочек, полученных в процессе сворачивания, использовать магазин,  то таблица переходов может быть использована для определения грамматических вхождений, записываемых в магазин.
Для описания порядка действий магазинного распознавателя построим еще одну таблицу. В этой таблице обозначим действие переноса  символов из входной цепочки в магазин символом П (Перенос), а  действия, связанные со сворачивание цепочек, соответствующих правым частям правил,  обозначаим символом С(К), где К—номер использованного правила. Для обозначения действий, осуществляющих передачу на выход результатов работы распознавателя, условимся использовать начальные буквы слов Допустить (Д) и Отвергнуть (О).
Учитывая, что действия преобразователя зависят как от символов входной цепочки, так и от символов, находящихся в магазине, обозначим строки таблицы грамматическими вхождениями, а столбцы - терминальными символами грамматики и символом конца цепочки ^.
Основанием для заполнения таблицы являются следующие два положения:
1. Операция сворачивания должна выполняться независимо от входного символа всегда, если в вершине магазина находится самое правое грамматическое вхождение некоторого правила. Для таких грамматических вхождений значением функции ВПОСЛЕ является пустое множество.
2. Если в вершине магазина находится грамматическое вхождение, не являющиеся самым правым вхождением какого-либо правила, то следует выполнить перенос очередного символа входной цепочки в магазин.
Следуя эти положениям и учитывая, что прцесс распознавания заканчивается успешно при обнаружении символа ^ на входе и символа Iо в магазине, и что в оставшихся случаях входная цепочка должна быть отвергнута, получаем таблицу действий в следующем виде:

Таблица 3.2
  a b <C> ^
a1 П П П О
<I12> П П П О
<I13> П П П О
b1 С(1) С(1) С(1) С(1)
<C2> С(2) С(2) С(2) С(2)
h0 П П П О
<I0> О О О Д
Эта таблица задает функцию действий
                f ( Bi j , x )  ( - { Д, О, С (1), С (2), ..., С (N)  },
где N - число правил заданной грамматики, которая определяет какое действие должен выполнить распознаватель, находящийся в состоянии Bi j и прочитавший выходной символ x.
Для рассматриваемого примера операции свертки определяются следующим образом:
                C (1) = { a1<I12><I13>b1 | => I0 },
                C (2) = { c2 | => I0 }.
Последняя таблица, которую иногда называют управляющей таблицей распознавателя, и таблица состояний полностью задают работу распознавателя. Алгоритм работы, использующий таблицу состояний и таблицу действий можно описать так:
  1. Прочитать очередной символ входной цепочки—x.
  2. Прочитать символ состояния, находящийся в вершине магазина—YK1.
  3. Прочитать значение элемента таблицы действий, находящегося в строке YK1 и столбце x.
  4. Если прочитанное значение есть 0 или D, то работу следует закончить, поскольку результат получен.
  5. Если прочитанное значение определяет операцию, результатом которой является грамматический символ Z, то прочитать в таблице состояний элемент Z i j, находящийся в строке YK1 и столбце Z. Записать YK1 и прочитанный символ Z i j в магазин и выполнять п.1.
Используя описанный алгоритм, работу распознавателя, заданного таблицами 7.1 и 7.2, можно представить в виде последовательности конфигураций:
Магазин Вход Действие
 1. h0
 aaccbcb^ П
 2. h0a1
 accbcb^ П
 3. h0a1a1
 ccbcb^ П
 4. h0a1a1c2
 cbcb^ С(2)
 5. h0a1a1<I12>
 cbcb^ П
 6. h0a1a2<I12>c2
 bcb^ С(2)
 7. h0a1a2<I12><I13>
 bcb^ П
 8. h0a1a2<I12><I13>b1
 cb^ С(1)
 9. h0a1<I12>
 cb^ П
10. h0a1<I12>c2
 b^ С(2)
11. h0a1<I12><I13>
 b^ П
12. h0a1<I12><I13>b1
 ^ С(1)
13. h0I0
 ^ Д
В общем случае процедуру построения восходящего распознавателя по заданной грамматике, не содержащей аннулирующих правил, можно описать следующим образом:
      1. Вычислить для данной грамматики функции ВПЕРВ и ВПОСЛЕ.
      2. Построить недетерминированную таблицу, имеющую по одному столбцу для каждого грамматического символа и по одной строке для каждого грамматического вхождения и маркера дна. Элемент в строке Rj и столбце С должен содержать все грамматические вхождения CK, такие, что CK О ВПОСЛЕ(Rj).
      3. Если таблица, построенная на шаге 2, получается недетерминированной, то нужно преобразовать эту таблицу в детерминированную, рассматривая ее как недетерминированную таблицу переходов конечного автомата с начальным состоянием ho.
      4. Состояния, полученные на шаге 3 (кроме состояния, соответствующего пустому множеству), следует использовать в качестве магазинных символов. Полученная таблица переходов может содержать переходы в пустое множество. Такие элементы следует понимать как запрещенные и рассматривать переходы в них как ошибки.
      5. Таблица действий заполняется строка за строкой согласно множествам грамматических вхождений, помечающих строки, следующим образом:
        6. а.
        Если строка отмечена начальным вхождением I0, то в столбец, соответствующий маркеру конца строки ^, заносится операция Допустить, а во все остальные строки - операция Отвергнуть.
        б.
        Если строка отмечена грамматическим вхождением, являющимся самым правым вхождением в правиле с номером k, то во все элементы строки помещается операция Cвертка(k).
        в.
        Если строка отмечена маркером дна h0 или если все грамматические вхождения, входящие во множество, помечающее строку, не являются самыми правыми в своих правилах, то в столбец, отмеченный концевым маркером строки, заносится операция Отвергнуть, а во все остальные столбцы — операция Перенос.
        г.
        Если множество, помечающее строку после преобразования НКА, содержит начальное вхождение и хотя бы одно вхождение, отличное от начального, но не содержит ни одного самого правого вхождения, то в столбец, помеченный символом конца строки, нужно поместить операцию Допустить, а в остальные столбцы — Перенос.
      Приведенная процедура обеспечивает построение распознавателя, только если заданная грамматика принадлежит подклассу LR(0), поскольку действия в каждой строке управляющей таблицы одинаковы, то есть не зависят от входного символа. Если же в процессе построения обнаруживается, что хотя бы один из пунктов (а), (б), (в) или (г) выполнить нельзя, то это означает, что для заданной грамматики нельзя построить LR(0)-распознаватель и что она не является LR(0)-грамматикой.
Пред.Страница  След.Страница   Раздел   Содержание
Hosted by uCoz