НЕОДНОЗНАЧНОСТИ И КОНФЛИКТЫ
Множество грамматических правил неоднозначно, если существует входная цепочка, которую можно структурировать несколькими различными способами. Например, правило
expr : expr '-' expr ;
- естественный способ выразить тот факт, что арифметическое выражение можно сформировать, взяв два других выражения и разделив их знаком минус. К сожалению, это правило не полностью определяет способ структуризации всей совокупности исходных дан- ных. Так, если входная цепочка - это
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 по умолчанию использует два метода разрешения неоднозначностей:
- При конфликте перенос-свертка по умолчанию выполняется перенос.
- При конфликте свертка-свертка по умолчанию выбирается правило, встретившееся в yacc-спецификации первым.
Первый метод устанавливает, что свертки менее предпочтительны, чем переносы, если есть выбор. Второй метод дает пользователю довольно грубый механизм управления разбором, поэтому, когда возможно, конфликтов свертка-свертка следует избегать.
Конфликты могут возникать либо из-за ошибок в исходных данных или в логике спецификаций, либо из-за того, что грамматические правила (вполне корректные) требуют более сложного алгоритма разбора, чем может построить yacc. Использование действий внутри правил также может вызывать конфликты, если действие должно выполняться до того, как алгоритм сможет определить достоверно, какое правило следует применить. В таких случаях указанные методы разрешения неоднозначностей не подходят, поскольку приводят к некорректному алгоритму разбора. По этой причине yacc
всегда сообщает число конфликтов перенос-свертка и свертка-свертка, разрешенных при помощи метода 1 и метода 2.
Вообще говоря, если можно применить методы разрешения неоднозначностей и породить корректный алгоритм разбора, то можно и переписать грамматические правила таким образом, чтобы они обрабатывали те же исходные данные, но не содержали конфликтов. По этой причине большинство более ранних генераторов компиляторов считали конфликты фатальными ошибками. Опыт показал, однако, что подобное переписывание противоестественно и порождает медленные алгоритмы. Поэтому yacc порождает алгоритмы разбора даже при наличии конфликтов.
Рассмотрим методы разрешения неоднозначностей на следующем примере.
stat : IF '(' cond ')' stat | IF '(' cond ')' stat ELSE stat ;
Это - фрагмент спецификации языка программирования, включающего оператор if-then-else. В приведенном правиле 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, прочитать S2, а затем выполнить свертку правой части цепочки
IF ( C1 ) IF ( C2 ) S1 ELSE S2
по if-else-правилу и получить
IF ( C1 ) stat
что в свою очередь свертывается по простому if-правилу. Это соответствует второй интерпретации, которая обычно считается более предпочтительной.
Такой конфликт перенос-свертка возникает только тогда, когда текущим является определенный входной символ, ELSE, и прочитана определенная входная цепочка,
IF ( C1 ) IF ( C2 ) S1
Вообще говоря, может быть много конфликтов, и каждому соответствует входной символ и прочитанная перед ним входная цепочка. Прочитанная входная цепочка задает состояние алгоритма разбора.
Сообщения yacc о конфликтах лучше всего понять, анализируя описание алгоритма, формируемое по опции -v. Например, фрагмент, описывающий рассмотренное выше конфликтное состояние, выглядит так:
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, выполняется свертка
stat : IF ( cond ) stat
по грамматическому правилу 18.
Вновь напомним, что номера, следующие за командами переноса, указывают состояния, а номера, следующие за командами свертки, обозначают грамматические правила. В файле y.output номера правил печатаются в скобках после самих правил, для которых может быть выполнена свертка. В большинстве состояний возможно заданное по умолчанию действие свертка. Пользователь, обнаруживший непредвиденные конфликты перенос-свертка, захочет, быть может, просмотреть файл описаний, чтобы решить, допустимы ли действия по умолчанию.
