8.1.2.Семантический стек

Для естественного обмена данными между действиями, каждый терминал или нетерминал может иметь значение. Для доступа к нему в действиях используются псевдопеременные $$ - значение левого символа правила, $ - значение i-ого символа правой части правила. Другими словами, кроме обычного стека состояний построенный YACC'ом анализатор содержит "семантический" стек, содержащий значения символов. Значения имеют тип YYSTYPE, который по умолчанию определяется как int. Действие

expr : expr '+' expr { $$ = $1 + $3; } ;

может быть использовано в интерпретаторе формул, в котором значение нетерминала "выражение" есть его вычисленное значение.

Если для правила не указано никакого действия, или действие не содержит упоминания псевдопеременной $$, то значение левой части правила становится равным значению первого символа правой части, т.е. неявно выполняется действие { $$ = $1; }. Значение очередной лексемы копируется из переменной int yylval, в которую его заносит сканер.

Естественно, что различные символы грамматики могут иметь значения разных типов. Для этого следует определить тип YYSTYPE как union и специфицировать тип терминалов и нетерминалов в разделе описаний. Например:

%{

#define YYSTYPE yys

typedef union {

int intval;

long longval;

nodeptr *ptrval;

} yys;

%

%token ICONST LCONST

%type ICONST

%type LCONST

%type expr

В этом примере символ грамматики может иметь значение одного из трех типов: intval, longval и ptrval, имена которых совпадают с именами полей типа YYSTYPE. При обращении к значению символа, тип которого объявлен в операторе %type, в порожденной YACC'ом C-програме будет обращение к соответствующему полю объединения yys.

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

8.2.Неоднозначности и конфликты

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

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, и прочитана определенная входная цепочка.

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

Сообщения 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 номера правил печатаются в скобках после самих правил, для которых может быть выполнена свертка. В большинстве состояний возможно заданное по умолчанию действие свертка. Пользователь, обнаруживший непредвиденные конфликты перенос-свертка, захочет, быть может, просмотреть файл описаний, чтобы решить, допустимы ли действия по умолчанию.