Pull to refresh

Компиляция. 3: бизон

Reading time 13 min
Views 46K
Это единственный пост в серии, в центре внимания которого — старообрядный сишный бизон, так надоевший некоторым. Тем, кто пишет не на Си, пост всё равно должен быть интересен, потому что похожие по принципу работы генераторы LR-парсеров существуют для очень многих языков. Тех же, кто идеологически не приемлет LR-парсеры, мне сегодня привлечь нечем.

Далее в посте:

  1. Компиляция грамматики
  2. Двухступенчатый парсер
  3. Что у него внутри?
  4. Конфликты в грамматике
  5. Как это работает?

Чем мы занимались до сих пор?
В прошлый раз составили грамматику для арифметических выражений:
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-файла.
Весь остальной код парсера универсален: никаких спагетти, никаких рекурсивных функций, вызывающих друг друга в хитрых комбинациях. Правила грамматики действительно компилируются, а не обрамляются в синтаксис языка высокого уровня.
Tags:
Hubs:
+69
Comments 15
Comments Comments 15

Articles