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


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


В сущности, действие свертка, извлекая состояния из стека, возвращает разбор к состоянию, в котором было начато применение правой части данного правила. После этого алгоритм разбора поступает так, как будто в данный момент обнаружено не вхождение правой части, а символ, стоящий в левой части правила. Если правая часть правила пуста, ни одно состояние из стека не извлекается. Открывающееся состояние - просто то же самое текущее состояние.

Действие свертка важно также для понимания процесса выполнения действий, заданных пользователем, и передачи значений. При свертке правила перед преобразованием стека выполняются действия, ассоциированные с правилом. Кроме стека, содержащего состояния, параллельно поддерживается еще один стек, который содержит значения, возвращаемые лексическим анализатором и действиями. При выполнении переноса в стек значений заносится внешняя переменная yylval. После выполнения пользовательского действия свертка завершается. При выполнении действия переход в стек значений заносится внешняя переменная yyval. Псевдопеременные $1, $2 и т.д. указывают на элементы стека значений.

Понять два других действия алгоритма значительно проще. Действие успех обозначает, что входной текст прочитан и сопоставлен со спецификацией. Это действие выполняется только в том случае, когда предварительно просмотренная лексема равна маркеру конца. Оно обозначает, что работа алгоритма успешно завершена. Действие ошибка, напротив, представляет ситуацию, когда алгоритм не может дальше продолжать разбор в соответствии со спецификацией. Исходные лексемы (вместе с предварительно просмотренной лексемой) таковы, что никакой последующий текст не приведет к допустимым исходным данным. Алгоритм сообщает об ошибке и пытается восстановить ситуацию и продолжить разбор. Позднее будет обсуждаться нейтрализация, а не просто обнаружение ошибок.

Рассмотрим yacc-спецификацию:

%token DING DONG DELL %% rhyme : sound place ; sound : DING DONG ; place : DELL ;

Когда утилита yacc вызывается с опцией -v, порождается файл с именем y.output, содержащий удобочитаемое описание алгоритма разбора. Ниже приводится файл y.output, соответствующий данной спецификации (статистическая информация в конце файла опущена).




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