АЛГОРИТМ СИНТАКСИЧЕСКОГО РАЗБОРА
yacc отображает файл спецификаций в процедуру на языке C, которая разбирает входной текст в соответствии с заданной спецификацией. Алгоритм, используемый для того, чтобы перейти от спецификации к C-процедуре, сложен и здесь обсуждаться не будет. Алгоритм же самого разбора относительно прост, знание его облегчит понимание механизма нейтрализации ошибок и обработки неоднозначностей.
yacc порождает алгоритм разбора, использующий конечный автомат со стеком. Кроме того, алгоритм разбора может прочесть и запомнить следующую входную лексему (которая называется предварительно просмотренной). Текущее состояние автомата всегда сохраняется на вершине стека. Состояния конечного автомата задаются небольшими целочисленными значениями. В начальный момент автомат находится в состоянии 0 (стек содержит единственное значение 0) и предварительно просмотренная лексема не прочитана.
В алгоритме имеется всего четыре типа действий - перенос
(shift), свертка (reduce), успех (accept), ошибка (error). Шаг работы алгоритма состоит в следующем:
- Основываясь на текущем состоянии автомата, алгоритм выясняет, требуется ли для выбора очередного действия предварительно просмотренная лексема. Если требуется, но не прочитана, алгоритм запрашивает следующую лексему у функции yylex.
- Используя текущее состояние и, если нужно, предварительно просмотренную лексему, алгоритм выбирает очередное действие и выполняет его. В результате состояния могут быть помещены в стек или извлечены из него, предварительно просмотренная лексема может быть обработана, а может быть и нет.
Действие перенос - наиболее частое действие алгоритма. В выполнении действия перенос всегда участвует предварительно просмотренная лексема. Например, для состояния 56 может быть определено действие
IF shift 34
что означает: в состоянии 56, если предварительно просмотренная лексема равна IF, текущее состояние (56) помещается в стек, текущим становится состояние 34 (заносится на вершину стека). Предварительно просмотренная лексема очищается.
Действие свертка препятствует неограниченному росту стека. Оно выполняется, когда алгоритм, просмотрев правую часть правила, обнаруживает в обрабатываемых данных ее вхождение, которое и заменяет левой частью. Может понадобиться проанализировать предварительно просмотренную лексему (обычно этого не требуется), чтобы решить, выполнять свертку или нет. Часто подразумеваемым действием (которое обозначается точкой) оказывается именно свертка.
Действия свертка ассоциируются с отдельными грамматическими правилами. Грамматические правила (как и состояния) нумеруются небольшими целыми числами, и это приводит к некоторой путанице. В действии
. reduce 18
имеется в виду грамматическое правило 18, тогда как в действии
IF shift 34
- состояние 34.
Предположим, выполняется свертка для правила
A : x y z ;
Действие свертка зависит от символа в левой части правила (в данном случае A) и числа символов в правой части (в данном случае три). При свертке сначала из стека извлекаются три верхних состояния. (В общем случае число извлекаемых состояний равно числу символов в правой части правила). В сущности, эти состояния были занесены в стек при распознавании x, y и z и больше не нужны. После того, как извлечены эти состояния, на вершине стека оказывается состояние автомата на момент перед началом применения данного правила. Для этого состояния и символа, стоящего в левой части правила, выполняется действие, имеющее результат, аналогичный переносу с аргументом A. Конечный автомат переходит в новое состояние, которое заносится в стек, и разбор продолжается. Имеются, однако, существенные отличия между обработкой символа из левой части правила и обычным переносом лексемы, поэтому это действие называется действием переход (goto). В частности, предварительно просмотренная лексема при переносе очищается, а при переходе не затрагивается. В любом случае, открывшееся на вершине стека состояние содержит действие
A goto 20
выполнение которого приводит к тому, что состояние 20 помещается на вершину стека и становится текущим.
В сущности, действие свертка, извлекая состояния из стека, возвращает разбор к состоянию, в котором было начато применение правой части данного правила. После этого алгоритм разбора поступает так, как будто в данный момент обнаружено не вхождение правой части, а символ, стоящий в левой части правила. Если правая часть правила пуста, ни одно состояние из стека не извлекается. Открывающееся состояние - просто то же самое текущее состояние.
Действие свертка важно также для понимания процесса выполнения действий, заданных пользователем, и передачи значений. При свертке правила перед преобразованием стека выполняются действия, ассоциированные с правилом. Кроме стека, содержащего состояния, параллельно поддерживается еще один стек, который содержит значения, возвращаемые лексическим анализатором и действиями. При выполнении переноса в стек значений заносится внешняя переменная yylval. После выполнения пользовательского действия свертка завершается. При выполнении действия переход в стек значений заносится внешняя переменная yyval. Псевдопеременные $1, $2 и т.д. указывают на элементы стека значений.
Понять два других действия алгоритма значительно проще. Действие успех обозначает, что входной текст прочитан и сопоставлен со спецификацией. Это действие выполняется только в том случае, когда предварительно просмотренная лексема равна маркеру конца. Оно обозначает, что работа алгоритма успешно завершена. Действие ошибка, напротив, представляет ситуацию, когда алгоритм не может дальше продолжать разбор в соответствии со спецификацией. Исходные лексемы (вместе с предварительно просмотренной лексемой) таковы, что никакой последующий текст не приведет к допустимым исходным данным. Алгоритм сообщает об ошибке и пытается восстановить ситуацию и продолжить разбор. Позднее будет обсуждаться нейтрализация, а не просто обнаружение ошибок.
Рассмотрим yacc-спецификацию:
%token DING DONG DELL %% rhyme : sound place ; sound : DING DONG ; place : DELL ;
Когда утилита yacc вызывается с опцией -v, порождается файл с именем y.output, содержащий удобочитаемое описание алгоритма разбора. Ниже приводится файл y.output, соответствующий данной спецификации (статистическая информация в конце файла опущена).
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 и т.д. Несколько минут, затраченных на эти и другие простые примеры, окупятся, когда возникнут вопросы в более сложных случаях.
