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

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

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

Глава 5. Двусмысленность и конфликты

    Hабор грамматических правил двусмысленен, если существуют некоторые входные строки, которые могут быть структурированы двумя или более различными способами. Hапример, грамматическое правило

expr : expr '-' expr

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

expr - expr - expr

    то правило позволяет структурирвоать их либо как

( expr - expr ) - expr

    или как

expr - ( expr - expr )

    (Первое правило называется левым связыванием, второе - правым связыванием).

     Yacc определяет такие двусмысленности, когда пытается построить парсер. Поучительно было бы представить проблему, встающую перед парсером, когда на входе

expr - expr - expr

    Когда парсер прочел второе expr, входные данные, которые он прочел, это

expr - expr

    соответствующие правой части вышеприведенного правила. Парсер может понизить входные данные, применяя это правило; после применения входные данные понижаются до expr (левой части правила). Парсер затем прочитывает оставшуюся часть данных:

- expr

    и снова понижает. Эффектом этого является левоассоциациативная интерпретация.

    С другой стороны, когда парсер увидел

expr - expr

    он может отложить немедленно применение правила и продолжить читать входные данные, пока не увидит

expr - expr - expr

    Теперь он может применить правило к трем самым правым символам, понижая их до expr и оставляя

expr - expr

    Теперь правило понижается еще раз; эффектом является правоассоциативная интерпретация. Таким образом, прочтя

expr - expr

    парсер может сделать две разрешенные вещи - сдвиг и понижение, и нет способа выбрать отдать одному из них предпочтение. Это называется конфликтом сдвига/ понижения. Также может случиться, что у парсера будет выбор между двумя разрешенными понижениями; это называется конфликт понижения/понижения. Заметьте, что конфликтов сдвиг/сдвиг не бывает.

    Когда присутствуют конфликты сдвига/понижения или понижения/понижения, Yacc все еще может произвести парсер. Он выбирает одно из возможных действий. Правило, описывающее, какой выбор делать в данной ситуации, называется правилом устранения двусмысленности.

    Yacc пользуется по умолчанию двумя правилами устранения двусмысленности:

1. В случае конфликта сдвиг/понижение по умолчанию делается сдвиг.
2. В случае конфликта понижение/понижение по умолчанию производится понижение по первому грамматическому правилу (во входном потоке).

    Правило 1 означает, что понижения задерживаются в пользу сдвигов при наличии выбора. Правило 2 предоставляет пользователю достаточно грубый контроль над поведением парсера в этой ситуации, но конфликтов понижение/понижение надо избегать всгда, когда возможно.

    Конфликты могут возникать из-за ошибок в данных или логике или потому, что грамматические правила, хотя и являющиеся согласующимися, требуют более комплексного парсера, чем тот, который может произвести Yacc. Использование действий внутри правил также может вызвать конфликты если действие должно произвестись перед тем, как парсер окончательно знает, какое правило распознается. В этих случаях применение правил устранения двусмысленности неуместно и ведет к некорректному парсеру. По этой причине Yacc всегда сообщает о количестве конфликтов сдвиг/понижение и понижение/понижение, устраненных с помощью правил 1 и 2.

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

    В качестве примера силы правил, устраняющих двусмысленность, представим фрагмент из языка программирования, содержащего конструкцию "if-then-else".

stat : IF '(' cond ')' stat
  | IF '(' cond ')' stat ELSE stat
  ;

    В этих правилах IF и ELSE являются токенами, cond есть нетерминальный символ, описывающий условные (логические) выражения, а stat есть нетерминальный символ, описывающий операторы. Первое правило называется правилом "простое-if", а второе - правило "if-else".

    Эти два правила формируют противоречивую конструкцию, потому что входные данные

IF ( C1 ) IF ( C2 ) S1 ELSE S2

    могут быть структурированы, используя эти правила, двумя способами:

IF ( C1 )
{
   IF ( C2 ) S1
}
ELSE S2

    или

IF ( C1 ) 
{
   IF ( C2 ) S1 
   ELSE S2
}

    Именно вторая интерпретация применяется в большинстве языков программирования, имеющих эту конструкцию. Каждый ELSE относится к последнему предыдущему IF, не имеющему своего ELSE. В данном случае, представим ситуацию, в которой парсер увидел

IF ( C1 ) IF ( C2 ) S1

    и ищет ELSE. Он может немедленно понизить по правилу "простое-if" и получить

IF ( C1 ) stat

    а затем прочитать оставшиеся входные данные

ELSE S2

    и понизить

IF ( C1 ) stat ELSE S2

    по правилу "if-else". Это едет к первому типу группирования входных данных.

    С другой стороны, ELSE может быть сдвинут, прочитан C2 и затем правая сторона

IF ( C1 ) IF ( C2 ) S1 ELSE S2

    может быть понижена по правилу "if-else" для получения

IF ( C1 ) stat

    что может быть понижено по правилу "простое-if". Это ведет ко второму типу группировки, что обычно и требуется.

    Повторяем, парсер может делать две разрешенные вещи - есть конфликт сдвиг/понижение. Применени правил устранения двусмысленности говорит парсеру сделать сдвиг в данном случае, что ведет к требуемой группировке.

    Конфликт сдвиг/понижение появляется только когда есть особенный входной символ, ELSE и уже были прочитаны особенные данные, такие как

IF ( C1 ) IF ( C2 ) S1

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

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

23: shift/reduce conflict (shift 45, reduce 18) on ELSE
state 23
  stat : IF ( cond ) stat_      (18)
  stat : IF ( cond ) stat_ELSE stat
  ELSE shift 45
  . reduce 18

    Первая строка описывает конфликт, сообщая о статусе и входном символе. Потом следует обычное описание состояния, с перечислением грамматических правил, активных в состоянии и действий парсера. Вспомним, что подчерк означает часть увиденных грамматических правил. Таким образом, в данном примере, в состоянии 23 парсер обработал входные данные, относящиеся к

IF ( cond ) stat

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

stat : IF ( cond ) stat ELSE_stat

    так как ELSE будет сдвинут в это состояние. Возвращаясь к состоянию 23, видим, что альтернативное действие, описанное как "." должно производиться если входной символ не указан явно в вышеуказанных действиях; таким образом в данном случае если входной символ не ELSE, парсер понижает по грамматическому правилу 18:

stat : IF '(' cond ')' stat

    Еще раз заметим, что номера, следующие за командами сдвига относятся к другим состояния, тогда как номера, следующие за командами понижения относятся к номерам грамматических правил. В файле y.output номера правил написаны после тех правил, которые могут быть понижены. В большинстве состояний будет возможно по крайней мере действие сдвига, которое и будет командой по умолчанию. Пользователю, столкнувшемуся с неожиданными конфликтами сдвиг/понижение, скорее всего будет полезно взглянуть на подробный отчет y.output чтобы решить, подойдет ли ему действие по умолчанию. В действительно сложных случаях пользователю надо иметь максимум информации о поведении и конструкции парсера, что может быть описано в отчете. В этом случае можно проконсультироваться с теоретическими работами [2], [3], [4]. Также можно обратиться к ближайшему "гуру".

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

Партнёры:

Хостинг: