[ новости /+++ | форум | теги | ]

Каталог документации / Раздел "Программирование, языки" / Оглавление документа

[ Содержание ] [ Предыдущая ] [ Следующая ]

Глава 4. Как работает парсер

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

     Парсер, созданный Yaccом, состоит из машины конечных состояний со стеком. Парсер также способен читать и запоминать следующий входной токен (LT - lookahead token). Текущее состояние - всегда на вершине стека. Состояниям машины конечных состояний присваиваются небольшие целые метки; изначально машина находится в состоянии 0, и не прочитано ни одного LT.

     Машине доступно только четыре действия, называемые сдвиг, понижение, принятие и ошибка. Каждый шаг парсера происходит следующим образом:

1. Основываясь на текущем состоянии парсер определяет, нужен ли ему LT для решения, какое действие нужно произвести; если ему требуется LT и он его не имеет, то вызывает yylex для получения следующего токена.
2. Используя текущее состояние и, если необходимо, LT парсер принимает решение о следующем действии и производит его. В результате состояния могут быть записаны в стек или прочитаны из него или LT обработан или оставлен.

    Действие сдвига - самое частое действие, которое производит парсер. Когда исполняется действие сдвига, всегда есть LT. Hапример, в состоянии 56 может быть действие:

IF shift 34

    которое означает, в состоянии 56, если LT есть IF, текущее состояние (56) продвигается дальше в стеке, и состояние 34 становится текущим (на вершине стека). LT очищается.

     Действие понижения предохраняет стек от неограниченного возрастания. Действия понижения соответствуют тому, что парсер увидел правую часть правила и готовится объявить, что он увидел случай, подчиняющийся правилу, заменяя его правую часть на левую. Может понадобиться проанализировать LT чтобы решить, необходимо ли понижение, но обычно этого не требуется; в действительности, действие по умолчанию (представляемое в виде ".") -- это часто действие понижения.

     Действия понижения связаны с индивидуальными грамматическими правилами. Грамматическим правилам также даются небольшие целые номера, что ведет к некоторому замешательству. Действие

. reduce 18

    относится к грамматическому правилу 18, тогда как действие

IF shift 34

    относится к состоянию 34.

     Предположим, что понижаемое правило

A : x y z ;

    Действие понижения зависит от символа слева (в данном случае A), и количества символов справа (в данном случае 3). Для понижения сначала вытолкнем из стека три состояния (В общем, количество выталкиваемых состояний равно количеству символов в правой части правила). В сущности, этп состояния, которые были помещены в стек при распознавании x, y и z и более не важны. После выталкивания этих состояний открывается состояние, в котором парсер находился перед началом обработки правила. Используя это открывшееся состояние и символ в левой части правила, представим, что произойдет в результате сдвига A. Получается новое состояние, записывается в стек и разбор продолжается. существует, однако, значительная разница между обработкой символа слева и простым сдвигом токена, так что это действие называется действием перехода. В частности, LT очищается при сдвиге и не изменяется при переходе. В любом случае открывшееся состояние содержит такую запись как:

A goto 20

    вызывающее запись состояния 20 в стек, при этом оно становится текущим.

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

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

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

     Время привести пример! Предположим, что имеется спецификация

%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, поэтому читается и становится LT первый токен, DING. Действие в состоянии 0 при токене DING есть "сдвиг 3", так что состояние 3 записывается в стек и очищается LT. Состояние 3 становится текущим. Читается и становится LT следующий токен, DONG. Действие в состоянии 3 при токене DONG есть "сдвиг 6", так что состояние 6 записывается в стек и очищается LT. Теперь стек содержит 0, 3 и 6. В состоянии 6 без анализа LT парсер понижается по правилу 2.

sound : DING DONG

    Это правило имеет два символа справа, поэтому два состояния, 6 и 3, выталкиваются из стека, открывая состояние 0. В соответствии с описанием состояния 0, ищем переход при sound, получаем

sound goto 2

    таким образом, состояние 2 записывается в стек, становясь текущим состоянием.

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

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

[ Содержание ] [ Предыдущая ] [ Следующая ]

Партнёры:

Хостинг: