6. Алгоритм анализатора Bison

Когда Bison читает лексемы, он помещает их в стек вместе с их семантическими значениями. Стек называется стеком анализатора. Помещение лексемы в стек традиционно называется сдвигом.

Например, предположим, что инфиксный калькулятор прочёл `1 + 5 *', а далее во входном тексте следует `3'. Стек будет содержать четыре элемента, по одному на каждую лексему, для которой был выполнен сдвиг.

Но стек не всегда содержит по элементу для каждой прочитанной лексемы. Когда последние n лексем и групп, для которых был выполнен сдвиг, соответствуют компонентам правила грамматики, они могут быть объединены в соответствии с этим правилом. Это называется свёрткой. Эти лексемы и группы заменяются в стеке одной группой, символ которой является результатом (левой частью) этого правила. Выполнение действия правила -- часть процесса свёртки, потому что именно тогда вычисляется семантическое значение полученной группы.

Например, если стек анализатора инфиксного калькулятора содержит:

1 + 5 * 3

и следующая лексема -- это литера новой строки, то последние три элемента могут быть свёрнуты до 15 правилом:

expr: expr '*' expr;

После этого стек будет содержать только три элемента:

1 + 15

В этот момент можно произвести ещё одну свёртку, получая единственное значение 16. Затем можно выполнить сдвиг для лексемы новой строки.

Анализатор пытается сдвигами и свёртками свернуть весь входной текст до единственной группы, символом которой является начальный символ грамматики (см. раздел 2.1 Языки и контекстно-свободные грамматики).

Этот тип анализаторов известен в литературе как анализатор снизу вверх.

6.1 Предпросмотренные лексемы

Анализатор Bison не всегда выполняет свёртку немедленно, как только последние n лексем и групп соответствуют правилу. Причина этого в том, что такая простая стратегия не подоходит для обработки большинства языков. Вместо этого, когда свёртка возможна, анализатор иногда "смотрит вперёд" на следующую лексему, чтобы решить, что делать.

Когда лексема прочитана, сдвиг не выполняется сразу же, сначала она становится предпросмотренной лексемой, которая не помещена в стек. Теперь анализатор может выполнить одну или более свёрток лексем и групп в стеке, в то время, как предпросмотренная лексема остаётся за его пределами. Когда больше свёрток выполнять не следует, предпросмотренная лексема сдвигается в стек. Это не означает, что произведены все возможные свёртки, это зависит от типа предпросмотренной лексемы, некоторые правила могут предпочесть отложить своё применение.

Вот простой случай, когда нужен предпросмотр. Эти три правила определяют выражения, содержащие бинарную операцию сложения и постфиксную унарную операцию факториала (`!'), а также допускают группировку скобками.

expr:     term '+' expr
        | term
        ;

term:     '(' expr ')'
        | term '!'
        | NUMBER
        ;

Предположим, что прочитаны и сдвинуты лексемы `1 + 2', что следует делать дальше? Если далее следует лексемы `)', то первые три лексемы должны быть свёрнуты до expr. Это единственный правильный вариант, поскольку сдвиг `)' создаст последовательность символов term ')', но ни одно правило этого не допускает.

Если же далее следует лексема `!', она должна быть немедленно сдвинута, чтобы `2 !' можно было свернуть до term. Если бы вместо этого анализатор выполнил свёртку ранее сдвига, `1 + 2' стало бы expr. Тогда было бы невозможно сдвинуть `!', потому что сдвиг создал бы в стеке последовательность символов expr '!'. Ни одно правило не допускает такой последовательности.

Текущая предпросмотренная лексема находится в переменной yychar. См. раздел 5.4 Специальные возможности, используемые в действиях.

6.2 Конфликты сдвиг/свёртка

Предположим, мы разбираем язык, имеющий операторы if-then и if-then-else, с помощью такой пары правил:

if_stmt:
          IF expr THEN stmt
        | IF expr THEN stmt ELSE stmt
        ;

Здесь мы предполагаем, что IF, THEN и ELSE -- терминальные символы лексем конкретных ключевых слов.

Когда лексемы ELSE прочитана и стала предпросмотренной лексемой, содержимое стека (предполагая, что входной текст правилен), как раз подходит для свёртки по первому правилу. Но законно также и сдвинуть ELSE, потому что это приведёт к последующей свёртке по второму правилу.

Такая ситуация, когда допустимы как сдвиг, так и свёртка, называется конфликтом сдвиг/свёртка. Bison разработан так, что он разрешает эти конфликты, выбирая сдвиг, за ислючением случаев, когда объявления приоритета операций указывают обратное. Чтобы понять причину этого решения, сравним его с другой возможной альтернативой.

Поскольку анализатор предпочитает сдвинуть ELSE, в результате предложение else будет относиться к самому внутреннем оператору if, что сделает два следующих входных текста эквивалентными:

if x then if y then win (); else lose;

if x then do; if y then win (); else lose; end;

Но если анализатор выбирал при возможности свёртку, а не сдвиг, в результате предложение else относилось бы к самому внешнему оператору if, что сделает эквивалентными следующие два входных текста:

if x then if y then win (); else lose;

if x then do; if y then win (); end; else lose;

Конфликт возникает потому что грамматика написана неоднозначно: правомерен любой способ разбор простого вложенного оператора if. Общепринятое соглашение состоит в том, что такие неоднозначности разрешаются отнесением предложения else к самому внутреннему оператору if. Именно это делает Bison, выбирая сдвиг, а не свёртку (идеальным было бы написать однозначную грамматику, но в данном случае это сделать очень трудно). Эта конкретная неоднозначность впервые встретилась в спецификации Algol 60 и называется неоднозначностью "кочующего else".

Чтобы избежать предупреждений Bison о предсказуемых, законных конфликтах сдвиг/свёртка используйте объявление %expect n. Тогда предупреждений не последует до тех пор, пока число конфликтов сдвиг/свёртка в точности равно n. См. раздел 4.7.5 Подавление сообщений о конфликтах.

Определение if_stmt выше лишь несёт ответственность за возникновение конфликта, но на самом деле конфликт не возникнет без дополнительных правил. Вот полный фходной файл Bison, действительно обнаруживающий конфликт:

%token IF THEN ELSE variable
%%
stmt:     expr
        | if_stmt
        ;

if_stmt:
          IF expr THEN stmt
        | IF expr THEN stmt ELSE stmt
        ;

expr:     variable
        ;

6.3 Приоритет операций

Другая ситуация, когда возникают конфликты сдвиг/свёртка, -- это в арифметических выражениях. Здесь сдвиг -- не всегда предпочтительное решение, объявления Bison приоритета операций позволят вам указать, когда выполняется сдвиг, а когда свёртка.

6.3.1 Когда необходим приоритет

Рассмотрим следующий фрагмент неоднозначной грамматики (неоднозначной, потому что входной текст `1 - 2 * 3' может юбыть разобран двумя разными способами):

expr:     expr '-' expr
        | expr '*' expr
        | expr '<' expr
        | '(' expr ')'
        ...
        ;

Предположим, что анализатор рассмотрел лексемы `1', `-' и `2'. Должен ли он выполнить свёртку по правилу для операции вычитания? Это зависит от следующей лексемы. Конечно, если далее следует лексема `)', мы должны выполнить свёртку, сдвиг будет неверным решением, потому что ни одно правило не может свернуть ни последовательность лексем `- 2 )', ни что-либо, начинающееся с неё. Но если следующая лексема -- `*' или `<', у нас есть выбор: как сдвиг, так и свёртка позволят удачно завершить разбор, но с разными результатами.

Чтобы решить, что должен делать Bison, мы должны рассмотреть результаты. Если сдвинуть следующую лексему знака операции op, она должна быть свёрнута первой, чтобы дать возможность свернуть разность. Результатом (на самом деле) будет `1 - (2 op 3'. С другой стороны, если вычитание свернуть до сдвига op, результатом будет `(1 - 2) op 3'. Поэтому ясно, что выбор сдвига или свёртки должен зависеть от относительного приоритета операций `-' и op: `*' должна быть сначала сдвинута, а `<' -- нет.

А что можно сказать о таком входном тексте, как `1 - 2 - 5', должен ли он означать `(1 - 2) - 5' или `1 - (2 - 5'? Для большинства операций мы предпочтаем первый вариант, называемый левой ассоциативностью. Второй вариант -- правая ассоциативность желателен для операций присваивания. Выбор левой или правой ассоциативности -- это вопрос о том, будет анализатор выбирать сдвиг или свёртку, когда стек содержит `1 - 2' и предпросмотренная лексема -- `-'. Сдвиг даёт правую ассоциативность.

6.3.2 Задание приоритета операций

Bison позволяет вам указать требуемый выбор с помощью объявлений приоритета операций %left и %right. Каждое такое объявление содержит список лексем, являющихся операциями, приоритет и ассоциативность которых определяется объявлением. Объявление %left делает эти все эти операции левоассоциативными, а %right -- правоассоциативными. Третий вариант -- %nonassoc, устанавливающий, что появление одной операции два раза "подряд" будет синтаксической ошибкой.

Относительный приоритет различных операций управляется порядком, в котором они объявляются. Первое в файле объявление %left или %right задаёт операции самого низкого приоритета, следующее такое объявление задаёт операции, приоритет которых немного выше и т.д.

6.3.3 Примеры приоритета

В нашем примере нам нужны были следующие объявления:

%left '<'
%left '-'
%left '*'

В более законченном примере, поддерживающем также другие операции, нам следует объявлять их группами равного приоритета. Например, '+' объявляется вместе с '-':

%left '<' '>' '=' NE LE GE
%left '+' '-'
%left '*' '/'

(здесь NE и т.п. соответствуют операциям "не равно" и т.д. Мы полагаем, что эти лексемы содержат более одной литеры, и поэтому представляются именами, а не строками).

6.3.4 Как работает приоритет

Во-первых, объявление приоритета присваивает уровни приоритета объявленным терминальным символам. Во-вторых, присваиваются уровни приоритета определённым правилам: каждое правило получает приоритет, равный приоритету последнего терминального символа среди его компонентов (вы можете также явно задать приоритет правила. См. раздел 6.4 Контекстно-зависимый приоритет.)

Наконец, конфликт разрешается сравнением приоритета рассматриваемого правила с приоритетом предпросмотренной лексемы. Если приоритет лексемы выше, выполняется сдвиг, если ниже -- свёртка. Если приоритеты одинаковы, выбор делается исходя из ассоциативности этого уровня приоритета. Подробный выходной файл, создаваемый при использовании параметра `-v' (см. раздел 10. Вызов Bison), объясняет, как был разрешён каждый конфликт.

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

6.4 Контекстно-зависимый приоритет

Часто приоритет операции зависит от контекста. На первый взгляд, это звучит странно, но на самом деле это очень распространённый случай. Например, знак "минус" обычно имеет очень высокий приоритет как унарная операция, и несколько меньший (меньший, чем умножение) как бинарная операция.

Объявления приоритета Bison -- %left, %right и %nonassoc -- для данной лексемы могут использоваться только один раз, поэтому лексема имеет только один приоритет, объявленный таким образом. Чтобы воспользоваться контекстно-зависимым приоритетом, вам нужно использовать дополнительный механизм: модификатор правил %prec.

Модификатор %prec объявляет приоритет конкретного правила, указывая терминальный символ, приоритет которого следует использовать для этого правила. Этот символ не обязательно должен появляться в самом правиле. Синтаксис модификатора таков:

%prec терминальный_символ

Он ставится после всех компонентов правила. В результате правилу вместо приоритета, который должен быть присвоен ему обычным способом, присваивается приоритет символа терминальный_символ. Затем изменённый приоритет правила влияет на разрешение конфликтов с участием этого правила (см. раздел 6.3 Приоритет операций).

Вот как %prec решает проблему унарного минуса. Во-первых, объявим приоритет фиктивного терминального символа UMINUS. Лексем такого типа нет, этот символ служит только для определения его приоритета.

...
%left '+' '-'
%left '*'
%left UMINUS

Теперь приоритет UMINUS можно использовать в правилах:

exp:    ...
        | exp '-' exp
        ...
        | '-' exp %prec UMINUS

6.5 Состояния анализатора

Функция yyparse реализована с использованием машины с конечным числом состояний. Значения, помещаемые в стек анализатора -- не просто коды типов лексем, они представляют всю последовательность терминальных и нетерминальных символов на вершине стека или около неё. Текущее состояния содержит всю информацию о более раннем входном тексте, относящуюся к решению вопрос, что делать далее.

Каждый раз, когда читается предпросмотренная лексема, текущее состояние анализатора и тип предпросмотренной лексемы ищутся в таблице. Эта ячейка таблицы может говорить, например: "Выполнить сдвиг для предпросмотренной лексемы". В этом случае она также задаёт новое состояние анализатора, помещаемое на вершину стека. Или же она может говорить: "Выполнить свёртку, используя правило номер n". Это означает, что определённое количество лексем и групп снимаются с вершины стека и заменяются одной группой. Другими словами, из стека вынимаются несколько состояний, и в него помещается одно новое.

Есть ещё одна возможность -- таблица может сказать, что предпросмотренная лексема в текущем состоянии недопустима. Это запускает процесс обработки ошибок (см. раздел 7. Восстановление после ошибок).

6.6 Конфликты свёртка/свёртка

Конфликт свёртка/свёртка возникает, когда есть два правила или более, применимых к одной последовательности входного текста. Это обычно свидетельствует о серьёзной ошибке в грамматике.

Например, вот ошибочная попытка определить последовательность нуля или более групп word:

sequence: /* пусто */
                { printf ("пустая последовательность\n"); }
        | maybeword
        | sequence word
                { printf ("добавлено слово %s\n", $2); }
        ;

maybeword: /* пусто */
                { printf ("maybeword пусто\n"); }
        | word
                { printf ("одиночное слово %s\n", $1); }
        ;

Ошибка состоит в неоднозначности: есть более одного способа разобрать одиночное слово word в sequence. Оно может быть свёрнуто до maybeword, а затем до sequence по второму правилу. Или же "совсем ничто" может быть свёрнуто до sequence по первоум правилу, и объединено с word, используя третье правило для sequence.

Есть также более одного способа свёртки "совсем ничего" в sequence. Это может быть непосредственно сделано по первому правилу, или косвенно через maybeword, и затем применением второго правила.

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

Bison разрешает конфликты свёртка/свёртка, выбирая правило, появляющееся в грамматике раньше, но полагаться на это очень рискованно. Каждый конфликт свёртка/свёртка должен быть изучен и обычно исключён. Вот правильный способ определения sequence:

sequence: /* пусто */
                { printf ("пустая последовательность\n"); }
        | sequence word
                { printf ("добавлено слово %s\n", $2); }
        ;

Вот ещё одна распространённая ошибка, приводящая к конфликтам свёртка/свёртка:

sequence: /* пусто */
        | sequence words
        | sequence redirects
        ;

words:    /* пусто */
        | words word
        ;

redirects:/* пусто */
        | redirects redirect
        ;

Здесь сделана попытка определить последовательность, которая может содержать либо группы word, либо redirects. Сами по себе определения sequence, words и redirects не содержат ошибок, но все вместе создают тонкую неоднозначность: даже пустая строка может быть разобрана бесконечным числом способов!

А именно: "совсем ничто" может быть words. Или оно может быть двумя words подряд, тремя, или любым другим количеством. Или оно может быть words, за которым следуют три redirects, а затем ещё одно words. И так далее.

Есть два способа исправить эти правила. Во-первых, сделать последовательность одноуровнневой:

sequence: /* пусто */
        | sequence word
        | sequence redirect
        ;

Во-вторых, запретить, чтобы words или redirects были пустыми:

sequence: /* пусто */
        | sequence words
        | sequence redirects
        ;

words:    word
        | words word
        ;

redirects:redirect
        | redirects redirect
        ;

6.7 Загадочные конфликты свёртка/свёртка

Иногда могут возникать конфликты свёртка/свёртка, выглядящие неоправданными. Вот пример:

%token ID

%%
def:    param_spec return_spec ','
        ;
param_spec:
             type
        |    name_list ':' type
        ;
return_spec:
             type
        |    name ':' type
        ;
type:        ID
        ;
name:        ID
        ;
name_list:
             name
        |    name ',' name_list
        ;

Может показаться, что эта грамматика может быть разобрана с предпросмотром только на одну лексему: если прочитано param_spec, то ID является name, если далее следует запятая или двоеточие, и type, если следует ID. Другими словами, эта грамматика является LR(1)-грамматикой.

Тем не менее, Bison, как и большинство генераторов анализаторов, на самом деле может обрабатывать не все LR(1)-грамматики. В этой грамматике два контекста -- после ID в начале param_spec и контекст в начале return_spec достаточно похожи, чтобы Bison полагал их одинаковыми. Они оказываются похожими, потому что должен действовать один и тот же набор правил -- правило свёртки до name и правило свёртки до type. В этой стадии обработки Bison неспособен определить, что в разных контекстах правилам потребуются разные предпросмотренные лексемы, и поэтому создаёт одно состояние анализатора для них обоих. Объединение этих двух контекстов позднее вызовет конфликт. В терминологии синтаксических анализаторов, этот случай означает, что грамматика не является LALR(1).

В общем, лучше устранить недостатки, чем документировать их. Но этот конкретный недостаток по его природе трудно устранить -- генератор анализаторов, который может обрабатывать LR(1)-грамматики трудно написать, и он будет создавать очень большие анализаторы. На практике Bison более полезен в том виде, в котором он существует сейчас.

Когда возникает эта проблема, вы часто можете решить её, выявив два состояния анализатора, которые были смешаны, и добавляя что-нибудь, чтобы они выглядели по-разному. В вышеприведённом примере добавление одного правила к return_spec, как указано ниже, устранит проблему:

%token BOGUS
...
%%
...
return_spec:
             type
        |    name ':' type
        /* Это правило никогда не используется.  */
        |    ID BOGUS
        ;

Это решит проблему, поскольку появляется возможность использования ещё одного правила в контексте после ID в начале return_spec. Это правило не действует в соответствующем контекта в param_spec, поэтому эти два контекста получат разные состояния анализатора. До тех пор, пока лексема BOGUS не генерируется yylex, добавленное правило не изменит способ разбора ни одного реального входного текста.

В этом конкретном примере есть и другой способ решения проблемы: переписать правило для return_spec, чтобы оно использовало ID непосредственно, а не через name. Это также приведёт к тому, что два путающихся контекста будут иметь различные наборы действующих правил, потому что контекст return_spec задействует изменённое правило для return_spec, а не правило для name.

param_spec:
             type
        |    name_list ':' type
        ;
return_spec:
             type
        |    ID ':' type
        ;

6.8 Переполнение стека и как его избежать

Стек анализатора Bison может переполниться, если для слишком многих лексем выполнен сдвиг и не выполнена свёртка. Когда это происходит: функция анализатора yyparse завершает работу и возвращает ненулевое значение, лишь вызвав перед этим yyerror чтобы сообщить об ошибке.

Определяя макрос YYMAXDEPTH, вы можете указать, какой глубины может достичь стек анализатора перед тем, как произойдёт переполнение стека. Определите этот макрос целым значением. Это значение -- максимальное число лексем, для которых может быть выполнен сдвиг (и не выполнена свёртка) до того, как произойдёт переполнение. Оно должно быть константным выражением, значение которого известно во время компиляции.

Не обязательно выделять всё допустимое для стека пространство. Если вы задаёте большое значение YYMAXDEPTH, анализатора на самом деле сначала выделяет небольшой стек, и затем постепенно увеличивает его по мере необходимости. Это последовательное выделение происходит автоматически и незаметно. Поэтому вам не нужно делать YYMAXDEPTH болезненно малым только для того, чтобы сберечь память для обычных входных текстов, не нуждающихся в большом объёме стека.

Значение YYMAXDEPTH по умолчанию, если вы не определили его, составляет 10000.

Вы можете управлять размером стека, выделяемого при инициализации, определяя макрос YYINITDEPTH. Это значение также должно быть целочисленной константой, доступной во время компиляции. Значение по умолчанию составляет 200.