Это единственный пост в серии, в центре внимания которого — старообрядный сишный бизон, так надоевший некоторым. Тем, кто пишет не на Си, пост всё равно должен быть интересен, потому что похожие по принципу работы генераторы LR-парсеров существуют для очень многих языков. Тех же, кто идеологически не приемлет LR-парсеры, мне сегодня привлечь нечем.
Чем мы занимались до сих пор?
В прошлый раз составили грамматику для арифметических выражений:
Закончили тем, что пристально рассмотрели автомат, который её парсит.
Придумывать парсящие автоматы сами мы не умеем, да и не надо — ведь бизон умеет строить их за нас!
С бизоньей помощью сможем скомпилировать наш парсер, и поглядеть, как всё это работает взаправду.
Общий принцип такой же, как с
В прошлый раз упомянули, что во время свёртки мы вынимаем из стека набор символов (строк или переменных), смотрим на их значения, задаём значение для свернувшейся переменной, и кладём её в стек вместо вынутых.

Так же, как в
%%, как и в
Если код свёртки не задан, и в правой части правила один символ, то по умолчанию бизон «наследует» его значение:
Самая первая объявленная переменная считается «корнем» грамматики, т.е. весь входной текст должен в итоге свернуться в этот корень.
При компиляции парсера нужно указать библиотеку
В отличие от калькулятора торговок с рынка, который умел игнорировать пробелы и комментарии, бизоний калькулятор понимает строго заданный синтаксис: цифры, знаки операций, перевод строки в конце. Чтобы предусмотреть, например, пробелы между любой парой символов, пришлось бы добавлять их в грамматику явно:
Ясно, что это неудобно. Да и писать для распознавания цифр 10 разных правил неудобно; а если бы нам нужны были латинские буквы, например в именах переменных, мы бы задавали 52 правила?!
До чего здорово было бы совместить преимущества
Если у нас уже есть
Чтобы такой симбиоз был возможен,
Функция
Кроме того, стёрли
Соответствующий файл
Файл с определениями токенов получает суффикс
Единственное, что в нём есть —
Все токены получают номера выше 256, чтобы отличаться от «обычных» символов.
Чтобы передать токен бизону, его значение записываем в глобальную (ох ужас!) переменную
Обычные символы передаём обычным способом (возвращаем код символа).
Опция
Компилируем двухступенчатый парсер:
По поводу терминологии: в такой двухступенчатой модели нижний парсер, распознающий токены, по традиции называют лексическим анализатором («лексером»), а верхний, распознающий конструкции из токенов — синтаксическим анализатором. Это указание именно роли парсера, а не его устройства: другие системы разбора могут, например, использовать для обеих ступеней магазинно-автоматные парсеры.
Чтобы увидеть сгенерированный автомат, не нужно нырять в пучины сишного кода: у бизона могучие средства для отладки грамматик. Указываем ключ
После переноса парсинга чисел в лексер, в автомате осталось 14 состояний, и описаны они примерно так:
Для каждого состояния указаны правила, которые в этом состоянии распознаются (вместе с их номерами в грамматике), и перечислены действия, выполняемые для каждого входного символа. Не указано следующее состояние после свёртки; вместо этого автомат возвращается в состояние, прочитанное из стека, и в нём ищет правило «go to», соответствующее свежесвёрнутому нетерминалу. Таким образом, таблица переходов автомата получается двумерной: в каждом состоянии действие зависит только от входного символа, и не зависит от содержимого стека. (Но из стека берётся следующее состояние после свёртки.)
Чтобы не ползать с карандашом по распечатке автомата, подставляя в него символ за символом, можно попросить бизона во время парсинга печатать все переходы из состояния в состояние. Для этого компилируем грамматику с ключом
Если мы, кроме того, хотим, чтобы печатались значения символов, то нужно определить макрос
Код после второго тега %% копируется в парсер неизменным так же, как если бы он был в %{ %}.
Теперь, раз мы определили
Из стека печатаются только состояния; типы символов в стеке, и их значения, остаётся угадывать из контекста.
Если макрос
В прошлый раз упомянули неоднозначные грамматики, допускающие для одного выражения несколько вариантов разбора.
Что скажет бизон, если попытаемся скомпилировать неоднозначную грамматику?
Когда из одного состояния грамматика допускает несколько продолжений, бизону непонятно, что именно выполнять. В нашем случае он колеблется между сдвигом и свёрткой. Можно исправить грамматику, как мы в прошлый раз сделали; а можно «подтолкнуть» бизона в нужную сторону, и намекнуть, что делать в случае конфликта. Стоит относиться к этому как к быстрому хаку: парсер начинает работать, но отлаживать «грамматику с намёками» становится сложнее.
Поскольку типичный источник конфликтов — арифметические выражения, то и намёки даются в виде указания приоритета операторов (выполнять умножение раньше сложения) и их ассоциативности (из операторов с равным приоритетом, который выполнять раньше). Чем ниже оператор в списке, тем выше приоритет. Операторы в одной строчке списка получают одинаковый приоритет.
Для правоассоциативных операторов есть директива
Противоестественность хака с приоритетами можно оценить на примере двусмысленности
Чтобы она распарсилась привычным образом —
Оба этих терминала тяжело назвать операторами, и тем более тяжело задать им «естественный» приоритет.
Зато это работает!
«Грамматика с намёками» компактнее однозначной и в исходном виде (короче вдвое), и в виде автомата (сэкономили одно состояние).
Даже в однозначной грамматике могут возникать конфликты, связанные с принципом работы магазинного автомата: во время выполнения каждого действия он видит только один следующий символ ввода. Например, грамматика
Это вторая причина, по которой парсер делают двухступенчатым: за счёт того, что лексер сжимает строки в токены и отбрасывает ненужные символы между токенами, LR-парсеру удаётся «дальше» заглядывать: не на одну букву, а на один токен вперёд.
Как и у
Как и в прошлый раз, символы, идентичные с точки зрения парсера, объединены в классы. В данном случае, классов 7, и они перечислены в файле
Таблицы переходов хитроумно объединены. В основной таблице хранятся описания действий: для сдвига (положительное число) — в какое состояние перейти; для свёртки (отрицательное) — по какому правилу свернуть.
Трюк в том, что индекс первого действия для каждого состояния хранится в отдельной таблице:
Действия по умолчанию для каждого состояния хранятся в другой отдельной таблице:
По индексу из
Чтобы проверить, к которому символу относится каждое действие в
Попробуем найти какое-нибудь действие, например приведённые выше:
Класс терминала NUM — 3.
Ищем первый сдвиг:
Второй сдвиг:
Аналогичным образом побита на три массива таблица «go to», которая задаёт, в какое состояние нужно перейти после свёртки.
Код собственно парсера: (неинтересные куски вырезаны, а интересные прокомментированы)
Вновь видим: весь парсер, вместе с вычислением выражения, уложился в пару страниц кода; да и то, его треть — мудрёный поиск по сжатым таблицам.
В следующий раз займёмся парсингом игрушечного языка программирования.
Достоинство бизона и ему подобных в том, что от усложнения языка вырастут в парсере только таблицы и свитч с действиями при свёртке, скопированными из
Весь остальной код парсера универсален: никаких спагетти, никаких рекурсивных функций, вызывающих друг друга в хитрых комбинациях. Правила грамматики действительно компилируются, а не обрамляются в синтаксис языка высокого уровня.
Далее в посте:
- Компиляция грамматики
- Двухступенчатый парсер
- Что у него внутри?
- Конфликты в грамматике
- Как это работает?
Чем мы занимались до сих пор?
В прошлый раз составили грамматику для арифметических выражений:
EXPR: TERM | EXPR '+' TERM | EXPR '-' TERM ; TERM: NUM | TERM '*' NUM | TERM '/' NUM ; NUM: DIGIT | NUM DIGIT ; DIGIT: '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' ;
Закончили тем, что пристально рассмотрели автомат, который её парсит.
Придумывать парсящие автоматы сами мы не умеем, да и не надо — ведь бизон умеет строить их за нас!
С бизоньей помощью сможем скомпилировать наш парсер, и поглядеть, как всё это работает взаправду.
Компиляция грамматики
Общий принцип такой же, как с
flex
в первой части: мы перечисляем правила грамматики, и напротив каждого правила пишем сишный код, который будет выполняться во время свёртки правила.В прошлый раз упомянули, что во время свёртки мы вынимаем из стека набор символов (строк или переменных), смотрим на их значения, задаём значение для свернувшейся переменной, и кладём её в стек вместо вынутых.
%{
#include <stdio.h>
int yylex() { return getc(stdin); }
void yyerror(char *s) {
fprintf (stderr, "%s\n", s);
}
%}
%%
EVALUATE: EXPR '\n' { printf("%d\n", $$) } ;
EXPR: TERM
| EXPR '+' TERM { $$ = $1 + $3; }
| EXPR '-' TERM { $$ = $1 - $3; }
;
TERM: NUM
| TERM '*' NUM { $$ = $1 * $3; }
| TERM '/' NUM { $$ = $1 / $3; }
;
NUM: DIGIT
| NUM DIGIT { $$ = $1*10+$2; }
;
DIGIT: '0' { $$=0; } | '1' { $$=1; } | '2' { $$=2; } | '3' { $$=3; }
| '4' { $$=4; } | '5' { $$=5; } | '6' { $$=6; } | '7' { $$=7; }
| '8' { $$=8; } | '9' { $$=9; }
;
%%
Разбор кода

Так же, как в
lex
-файлах, код в тегах %{ %} копируется в парсер неизменным. Есть две функции, которые необходимо определить: int yylex()
возвращает следующий входной символ, и void yyerror(char *s)
печатает сообщение об ошибке. Классический yacc
включал готовую реализацию yyerror
, которую можно было в случае необходимости переобъявить; но его GNU-клон bison
требует от программиста явную реализацию.%%, как и в
lex
-файлах, разделяет область объявлений и область правил грамматики. Правила перечисляются в том же виде, как мы уже привыкли; в конце правила добавляем код свёртки. В коде свёртки, чтобы сослаться на значения символов на стеке парсера, используем $-теги. $$
ссылается на сворачиваемую переменную (левую часть правила), $1
на самый левый символ в правой части правила (самый глубокий в стеке парсера), $2
на второй слева, и т.д. Если в правой части правила N символов, то можно пользоваться значениями от $1
до $N
.Если код свёртки не задан, и в правой части правила один символ, то по умолчанию бизон «наследует» его значение:
$$=$1
Самая первая объявленная переменная считается «корнем» грамматики, т.е. весь входной текст должен в итоге свернуться в этот корень.
EXPR
подходил бы в качестве корня, но тогда печать вычисленного выражения пришлось бы засунуть в свёртку EXPR
; а значит, печаталось бы ещё и значение каждого подвыражения по дороге. Для удобства печати заведём новую переменную EVALUATE
, которая используется только в качестве корня. Это заодно даёт возможность прочитать в конце выражения перевод строки — кроме удобства печати, получаем удобство ввода.При компиляции парсера нужно указать библиотеку
liby
, в которой лежит стандартная бизонья main()
.[tyomitch@home ~]$ bison 2.y
[tyomitch@home ~]$ cc -ly 2.tab.c
[tyomitch@home ~]$ ./a.out
22+3*4-5
=29
[tyomitch@home ~]$ ./a.out
2 + 2
syntax error
В отличие от калькулятора торговок с рынка, который умел игнорировать пробелы и комментарии, бизоний калькулятор понимает строго заданный синтаксис: цифры, знаки операций, перевод строки в конце. Чтобы предусмотреть, например, пробелы между любой парой символов, пришлось бы добавлять их в грамматику явно:
EXPR: TERM | EXPR WS '+' WS TERM | EXPR WS '-' WS TERM ;
TERM: NUM | TERM WS '*' WS NUM | TERM WS '/' WS NUM ;
NUM: DIGIT | NUM DIGIT ;
DIGIT: '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' ;
WS: | WS ' ' ;
Ясно, что это неудобно. Да и писать для распознавания цифр 10 разных правил неудобно; а если бы нам нужны были латинские буквы, например в именах переменных, мы бы задавали 52 правила?!
До чего здорово было бы совместить преимущества
flex
и bison
! Чтобы простые выражения (числа, пробелы) распознавать было просто, и чтобы сложные выражения распознавать было возможно.Двухступенчатый парсер
Если у нас уже есть
flex
-парсер, который успешно распознаёт числа и удаляет комментарии и пробелы, то прогоним входной текст через него; а то, что получится, прогоним через продвинутый бизоний парсер. На самом деле, нет надобности хранить промежуточный результат: обе ступени можно выполнить за один проход. flex
читает входной текст символ за символом, время от времени передавая «наверх» бизону токены — терминальные символы грамматики. Значения для токенов flex
задаёт сам.Чтобы такой симбиоз был возможен,
flex
должен как-то узнать терминальные символы бизоньей грамматики. Будем запускать bison
с ключом -d
, тогда он сгенерирует .h
-файл с перечислением всех терминалов. Для этого нужно объявить (указанием %token
) терминалы в файле грамматики — и останется лишь сослаться на сгенерированный .h
-файл в файле .lex
.%{
#include <stdio.h>
void yyerror(char *s) {
fprintf (stderr, "%s\n", s);
}
%}
%token NUM
%%
EVALUATE: EXPR { printf("=%d\n", $$); } ;
EXPR: TERM
| EXPR '+' TERM { $$ = $1 + $3; }
| EXPR '-' TERM { $$ = $1 - $3; }
;
TERM: NUM
| TERM '*' NUM { $$ = $1 * $3; }
| TERM '/' NUM { $$ = $1 / $3; }
;
%%
Функция
yylex
нам больше не нужна: теперь входные символы будут поступать не из stdin
, а от flex
.Кроме того, стёрли
'\n'
после EXPR
(его проглотит flex
), и убрали все правила про NUM
и DIGIT
.Соответствующий файл
.lex
:%{
#include "3.tab.h"
%}
%option yylineno
%option noyywrap
%%
[/][/].*\n ; // comment
[0-9]+ { yylval = atoi(yytext);
return NUM;
}
[ \t\r\n] ; // whitespace
. { return *yytext; }
%%
Файл с определениями токенов получает суффикс
.tab.h
Единственное, что в нём есть —
#define NUM 258
Все токены получают номера выше 256, чтобы отличаться от «обычных» символов.
Чтобы передать токен бизону, его значение записываем в глобальную (ох ужас!) переменную
yylval
, и возвращаем код токена.Обычные символы передаём обычным способом (возвращаем код символа).
Опция
noyywrap
указывает, что входной текст один, и после чтения EOF
не нужно пытаться перейти к следующему тексту. Эта опция устанавливалась автоматически, пока мы пользовались %option main
, задававшей чтение с stdin
. Сейчас main()
будет бизонья, поэтому нам не нужно ни просить у flex
стандартную main()
, ни писать свою.Компилируем двухступенчатый парсер:
[tyomitch@home ~]$ lex 3.lex
[tyomitch@home ~]$ bison -d 3.y
[tyomitch@home ~]$ cc -ly lex.yy.c 3.tab.c
[tyomitch@home ~]$ ./a.out
22+ // hello
3*4 - 5
=29
[tyomitch@home ~]$ ./a.out
22+x
syntax error
По поводу терминологии: в такой двухступенчатой модели нижний парсер, распознающий токены, по традиции называют лексическим анализатором («лексером»), а верхний, распознающий конструкции из токенов — синтаксическим анализатором. Это указание именно роли парсера, а не его устройства: другие системы разбора могут, например, использовать для обеих ступеней магазинно-автоматные парсеры.
Что у него внутри?
Чтобы увидеть сгенерированный автомат, не нужно нырять в пучины сишного кода: у бизона могучие средства для отладки грамматик. Указываем ключ
-v
, и глядим в файл с суффиксом .output
.После переноса парсинга чисел в лексер, в автомате осталось 14 состояний, и описаны они примерно так:
... state 7 4 EXPR: EXPR '-' . TERM NUM shift, and go to state 1 TERM go to state 11 state 8 6 TERM: TERM '*' . NUM NUM shift, and go to state 12 state 9 7 TERM: TERM '/' . NUM NUM shift, and go to state 13 state 10 3 EXPR: EXPR '+' TERM . 6 TERM: TERM . '*' NUM 7 | TERM . '/' NUM '*' shift, and go to state 8 '/' shift, and go to state 9 $default reduce using rule 3 (EXPR) ...
Для каждого состояния указаны правила, которые в этом состоянии распознаются (вместе с их номерами в грамматике), и перечислены действия, выполняемые для каждого входного символа. Не указано следующее состояние после свёртки; вместо этого автомат возвращается в состояние, прочитанное из стека, и в нём ищет правило «go to», соответствующее свежесвёрнутому нетерминалу. Таким образом, таблица переходов автомата получается двумерной: в каждом состоянии действие зависит только от входного символа, и не зависит от содержимого стека. (Но из стека берётся следующее состояние после свёртки.)
Чтобы не ползать с карандашом по распечатке автомата, подставляя в него символ за символом, можно попросить бизона во время парсинга печатать все переходы из состояния в состояние. Для этого компилируем грамматику с ключом
-t
, и в парсере появится глобальный флаг yydebug
. Его нужно установить в 1 — например, в main()
.Если мы, кроме того, хотим, чтобы печатались значения символов, то нужно определить макрос
YYPRINT
:%{
#include <stdio.h>
void yyerror(char *s) {
fprintf (stderr, "%s\n", s);
}
#define YYPRINT(file, type, value) fprintf(file, "%d", value);
%}
%token NUM
%%
EVALUATE: EXPR { printf("=%d\n", $$); } ;
EXPR: TERM
| EXPR '+' TERM { $$ = $1 + $3; }
| EXPR '-' TERM { $$ = $1 - $3; }
;
TERM: NUM
| TERM '*' NUM { $$ = $1 * $3; }
| TERM '/' NUM { $$ = $1 / $3; }
;
%%
int main () { yydebug=1; return yyparse(); }
Код после второго тега %% копируется в парсер неизменным так же, как если бы он был в %{ %}.
Теперь, раз мы определили
main()
сами, уже не нужно при компиляции подключать liby
:[tyomitch@home ~]$ lex 3.lex
[tyomitch@home ~]$ bison -dt 3.y
[tyomitch@home ~]$ cc lex.yy.c 3.tab.c
[tyomitch@home ~]$ ./a.out
Starting parse
Entering state 0
Reading a token: 22+3*4-5
Next token is token NUM (22)
Shifting token NUM, Entering state 1
Reducing stack by rule 5 (line 20), NUM -> TERM
Stack now 0
Entering state 4
Reading a token: Next token is token '+' (22)
Reducing stack by rule 2 (line 15), TERM -> EXPR
Stack now 0
Entering state 3
Next token is token '+' (22)
Shifting token '+', Entering state 6
Reading a token: Next token is token NUM (3)
Shifting token NUM, Entering state 1
Reducing stack by rule 5 (line 20), NUM -> TERM
Stack now 0 3 6
Entering state 10
Reading a token: Next token is token '*' (3)
Shifting token '*', Entering state 8
Reading a token: Next token is token NUM (4)
Shifting token NUM, Entering state 12
Reducing stack by rule 6 (line 21), TERM '*' NUM -> TERM
Stack now 0 3 6
Entering state 10
Reading a token: Next token is token '-' (4)
Reducing stack by rule 3 (line 16), EXPR '+' TERM -> EXPR
Stack now 0
Entering state 3
Next token is token '-' (4)
Shifting token '-', Entering state 7
Reading a token: Next token is token NUM (5)
Shifting token NUM, Entering state 1
Reducing stack by rule 5 (line 20), NUM -> TERM
Stack now 0 3 7
Entering state 11
Reading a token: Now at end of input.
Reducing stack by rule 4 (line 17), EXPR '-' TERM -> EXPR
Stack now 0
Entering state 3
Now at end of input.
Reducing stack by rule 1 (line 13), EXPR -> EVALUATE
=29
Stack now 0
Entering state 2
Now at end of input.
Из стека печатаются только состояния; типы символов в стеке, и их значения, остаётся угадывать из контекста.
Если макрос
YYPRINT
не задан, тогда угадывать придётся и значения прочитанных токенов: бизон будет печатать только пустые скобки.Конфликты в грамматике
В прошлый раз упомянули неоднозначные грамматики, допускающие для одного выражения несколько вариантов разбора.
Что скажет бизон, если попытаемся скомпилировать неоднозначную грамматику?
%{
#include <stdio.h>
void yyerror(char *s) {
fprintf (stderr, "%s\n", s);
}
%}
%token NUM
%%
EVALUATE: EXPR { printf("=%d\n", $$) } ;
EXPR: NUM
| EXPR '+' EXPR { $$ = $1 + $3; }
| EXPR '-' EXPR { $$ = $1 - $3; }
| EXPR '*' EXPR { $$ = $1 * $3; }
| EXPR '/' EXPR { $$ = $1 / $3; }
;
%%
[tyomitch@home ~]$ bison 4.y
4.y: conflicts: 16 shift/reduce
Когда из одного состояния грамматика допускает несколько продолжений, бизону непонятно, что именно выполнять. В нашем случае он колеблется между сдвигом и свёрткой. Можно исправить грамматику, как мы в прошлый раз сделали; а можно «подтолкнуть» бизона в нужную сторону, и намекнуть, что делать в случае конфликта. Стоит относиться к этому как к быстрому хаку: парсер начинает работать, но отлаживать «грамматику с намёками» становится сложнее.
Поскольку типичный источник конфликтов — арифметические выражения, то и намёки даются в виде указания приоритета операторов (выполнять умножение раньше сложения) и их ассоциативности (из операторов с равным приоритетом, который выполнять раньше). Чем ниже оператор в списке, тем выше приоритет. Операторы в одной строчке списка получают одинаковый приоритет.
%{
#include <stdio.h>
void yyerror(char *s) {
fprintf (stderr, "%s\n", s);
}
%}
%token NUM
%left '+' '-'
%left '*' '/'
%%
EVALUATE: EXPR { printf("=%d\n", $$) } ;
EXPR: NUM
| EXPR '+' EXPR { $$ = $1 + $3; }
| EXPR '-' EXPR { $$ = $1 - $3; }
| EXPR '*' EXPR { $$ = $1 * $3; }
| EXPR '/' EXPR { $$ = $1 / $3; }
;
%%
Для правоассоциативных операторов есть директива
%right
.Противоестественность хака с приоритетами можно оценить на примере двусмысленности
if (1) if (2) foo(); else bar();
Чтобы она распарсилась привычным образом —
if (1) { if (2) foo(); else bar(); }
— нужно, чтобы приоритет else
был выше, чем у ')'
Оба этих терминала тяжело назвать операторами, и тем более тяжело задать им «естественный» приоритет.
Зато это работает!
«Грамматика с намёками» компактнее однозначной и в исходном виде (короче вдвое), и в виде автомата (сэкономили одно состояние).
Даже в однозначной грамматике могут возникать конфликты, связанные с принципом работы магазинного автомата: во время выполнения каждого действия он видит только один следующий символ ввода. Например, грамматика
WORD: S1 'a' 'i' 'l' | S2 'a' 'l' 'e' ; S1: 's' ; S2: 's' ;— однозначная, и ей соответствует всего два слова — sail и sale. Когда парсер сдвинул первую букву 's' и видит после неё 'a', он не может сделать выбор, сворачивать
S1
или S2
: правильная свёртка зависит от того, какая буква будет после 'a'; но её автомат ещё не видит.Это вторая причина, по которой парсер делают двухступенчатым: за счёт того, что лексер сжимает строки в токены и отбрасывает ненужные символы между токенами, LR-парсеру удаётся «дальше» заглядывать: не на одну букву, а на один токен вперёд.
Как это работает?
Как и у
flex
, ядро парсера — таблица переходов и небольшой цикл. Используется два параллельных стека: стек состояний yyssa
и стек значений yyvsa
— всё равно состояния и символы входят и выходят из стека всегда парами.Как и в прошлый раз, символы, идентичные с точки зрения парсера, объединены в классы. В данном случае, классов 7, и они перечислены в файле
.output
. Массив static const unsigned char yytranslate[259]
сопоставляет всем терминалам класс. (От 0 до 255 — обычные символы; 258 — объявленный нами терминал NUM
).Таблицы переходов хитроумно объединены. В основной таблице хранятся описания действий: для сдвига (положительное число) — в какое состояние перейти; для свёртки (отрицательное) — по какому правилу свернуть.
static const unsigned char yytable[] = { 6, 7, 5, 8, 9, 10, 11, 1, 12, 13 };Удивительно, что таблица не только одномерная, но даже элементов в ней меньше, чем наших состояний (их 14).
Трюк в том, что индекс первого действия для каждого состояния хранится в отдельной таблице:
#define YYPACT_NINF -5 static const yysigned_char yypact[] = { 4, -5, 2, -4, -3, -5, 4, 4, 5, 6, -3, -3, -5, -5 };
YYPACT_NINF
означает, что состоянию не соответствует ни один элемент yytable
; иначе говоря, выполняемое действие не зависит от входного символа.Действия по умолчанию для каждого состояния хранятся в другой отдельной таблице:
static const unsigned char yydefact[] = { 0, 6, 0, 2, 3, 1, 0, 0, 0, 0, 4, 5, 7, 8 };Не зависеть от входного символа может только выполнение свёртки, поэтому значения в
yydefact
— номера правил грамматики, по которым нужно сворачивать.По индексу из
yypact[n]
хранится действие для состояния n и для класса символов 0. Действие для класса символов k хранится в yytable[yypact[n]+k]
; поэтому в yypact
могут быть отрицательные индексы — это лишь «база», к которой будет прибавляться номер класса.Чтобы проверить, к которому символу относится каждое действие в
yytable
, есть ещё одна таблица: static const unsigned char yycheck[] = { 4, 5, 0, 6, 7, 6, 7, 3, 3, 3 };Что мы видим?
yytable[0]
относится к символам класса 4, yytable[1]
к символам класса 5, и так далее.Попробуем найти какое-нибудь действие, например приведённые выше:
... state 7 4 EXPR: EXPR '-' . TERM NUM shift, and go to state 1 TERM go to state 11 state 8 6 TERM: TERM '*' . NUM NUM shift, and go to state 12 ...
Класс терминала NUM — 3.
Ищем первый сдвиг:
yytable[yypact[7]+3]==yytable[4+3]==1
(и действительно, yycheck[yypact[7]+3]==3
)Второй сдвиг:
yytable[yypact[8]+3]==yytable[5+3]==12
(и действительно, yycheck[yypact[7]+3]==3
)Аналогичным образом побита на три массива таблица «go to», которая задаёт, в какое состояние нужно перейти после свёртки.
Код собственно парсера: (неинтересные куски вырезаны, а интересные прокомментированы)
yynewstate:
*++yyssp = yystate; // кладём в стек текущее состояние
yyn = yypact[yystate]; // индекс первого действия
if (yyn == YYPACT_NINF)
goto yydefault; // не зависит от входного символа
yychar = yylex(); // читаем входной символ
yytoken = yytranslate[yychar]; // определяем класс
yyn += yytoken; // индекс внутрь yytable
if (yyn < 0 || YYLAST < yyn || yycheck[yyn] != yytoken)
goto yydefault; // нет подходящего действия
yyn = yytable[yyn];
if (yyn <= 0) {
yyn = -yyn;
goto yyreduce;
}
*++yyvsp = yylval; // сдвигаем
yystate = yyn; // следующее состояние
goto yynewstate;
yydefault:
yyn = yydefact[yystate];
if (yyn == 0) // ошибка синтаксиса:
goto yyerrlab; // ни одно действие не подошло,
// и нет действия по умолчанию
yyreduce:
yylen = yyr2[yyn]; // длина правой части правила
yyval = yyvsp[1-yylen]; // по умолчанию: унаследовать $1
// действия при свёртке:
// вместо $-тегов бизон подставил yyval слева и yyvsp[] справа
switch (yyn) {
case 2:
{ printf("=%d\n", yyval); }
break;
case 4:
{ yyval = yyvsp[-2] + yyvsp[0]; }
break;
case 5:
{ yyval = yyvsp[-2] - yyvsp[0]; }
break;
case 7:
{ yyval = yyvsp[-2] * yyvsp[0]; }
break;
case 8:
{ yyval = yyvsp[-2] / yyvsp[0]; }
break;
}
yyvsp -= yylen; // удаление из стека
yyssp -= yylen;
*++yyvsp = yyval; // кладём свежесвёрнутую переменную
yyn = yyr1[yyn]; // номер переменной по номеру правила
// вычисление следующего состояния после свёртки
yystate = yypgoto[yyn - YYNTOKENS] + *yyssp;
if (0 <= yystate && yystate <= YYLAST && yycheck[yystate] == *yyssp)
yystate = yytable[yystate];
else
yystate = yydefgoto[yyn - YYNTOKENS];
goto yynewstate;
Вновь видим: весь парсер, вместе с вычислением выражения, уложился в пару страниц кода; да и то, его треть — мудрёный поиск по сжатым таблицам.
В следующий раз займёмся парсингом игрушечного языка программирования.
Достоинство бизона и ему подобных в том, что от усложнения языка вырастут в парсере только таблицы и свитч с действиями при свёртке, скопированными из
.y
-файла.Весь остальной код парсера универсален: никаких спагетти, никаких рекурсивных функций, вызывающих друг друга в хитрых комбинациях. Правила грамматики действительно компилируются, а не обрамляются в синтаксис языка высокого уровня.