Операционная система UNIX. Руководство программиста


АЛГОРИТМ СИНТАКСИЧЕСКОГО РАЗБОРА - часть 4


state 0 $accept : _rhyme $end

DING shift 3 . error

rhyme goto 1 sound goto 2

state 1 $accept : rhyme _$end

$end accept . error

state 2

rhyme : sound _place DELL shift 5 . error

place goto 4

state 3 sound : DING _DONG

DONG shift 6 . error

state 4 rhyme : sound place_ (1)

. reduce 1

state 5 place : DELL (3)

. reduce 3

state 6 sound : DING DONG_ (2)

. reduce 2

Здесь приведены действия для каждого состояния, есть описания правил разбора, применяемых в каждом состоянии. Чтобы указать, что уже прочитано, а что еще осталось в каждом правиле, используется знак _. Проследить функционирование алгоритма можно на примере следующей входной цепочки:

DING DONG DELL

В начале текущее состояние есть состояние 0. Чтобы выбрать одно из действий, возможных в состоянии 0, алгоритм разбора должен обратиться к входной цепочке, поэтому первая лексема, DING, считывается и становится предварительно просмотренной. Действие в состоянии 0 над DING - перенос 3, состояние 3 помещается в стек, а предварительно просмотренная лексема очищается. Состояние 3 становится текущим. Читается следующая лексема, DONG, и уже она становится предварительно просмотренной. Действие в состоянии 3 над DING - перенос 6, состояние 6 помещается в стек, а предварительно просмотренная лексема очищается. Теперь стек содержит 0, 3 и 6. В состоянии 6, даже не опрашивая предварительно просмотренную лексему, алгоритм выполняет свертку

sound : DING DONG

по правилу 2. Два состояния, 6 и 3, извлекаются из стека, на вершине которого оказывается состояние 0. В соответствии с описанием состояния 0 выполняется

sound goto 2

Состояние 2 помещается в стек и становится текущим.

В состоянии 2 должна быть прочитана следующая лексема, DELL. Действие - перенос 5, поэтому состояние 2 помещается в стек, который теперь содержит 0, 2 и 5, а предварительно просмотренная лексема очищается. В состоянии 5 возможно единственное действие, свертка по правилу 3. В правой части этого правила один символ, поэтому из стека извлекается единственное состояние 5, а на вершине стека открывается состояние 2. Переход в состоянии 2 к place (левая часть правила 3) приводит к состоянию 4. Теперь стек содержит 0, 2 и 4. В состоянии 4 единственное действие - свертка по правилу 1. В его правой части два символа, поэтому из стека извлекаются два состояния, вновь открывая состояние 0. В состоянии 0 переход к rhyme переводит разбор в состояние 1. В состоянии 1 читается входная цепочка и обнаруживается маркер конца, в файле y.output он обозначается $end. Действие в состоянии 1 (когда найден маркер конца) - успешное завершение разбора.

Читателю настоятельно рекомендуется проследить, как действует алгоритм, если сталкивается с такими некорректными цепочками, как DING DONG DONG, DING DONG, DING DONG DELL DELL и т.д. Несколько минут, затраченных на эти и другие простые примеры, окупятся, когда возникнут вопросы в более сложных случаях.




Начало  Назад  Вперед



Книжный магазин