Bison linux что это

Обновлено: 05.07.2024

В этой главе вводятся многие основные понятия, без которых детальное описание Bison не будет иметь смысла. Если вы ещё не знаете, как использовать Bison или Yacc, мы предлагаем вам начать с внимательного чтения этой главы.

Для того, чтобы Bison мог разобрать программу на каком-то языке, этот язык должен быть описан контекстно-свободной грамматикой . Это означает, что вы определяете одну или более синтаксических групп и задаёте правила их сборки из составных частей. Например, в языке C одна из групп называется `выражение'. Правило для составления выражения может выглядеть так: "Выражение может состоять из знака `минус' и другого выражения". Другое правило: "Выражением может быть целое число". Как вы может видеть, правила часто бывают рекурсивными, но должно быть по крайней мере одно правило, выводящее из рекурсии.

Наиболее распространённой формальной системой для представления таких правил в удобном для человека виде является форма Бэкуса-Наура (БНФ, Backus-Naur Form, BNF), которая была разработана для описания языка Algol 60. Любая грамматика, выраженная в форме Бэкуса-Наура является контекстно-свободной грамматикой. Bison принимает на вход, в сущности, особый вид БНФ, адаптированный для машинной обработки.

Bison может работать не со всеми контекстно-свободными грамматиками, а только с грамматиками класса LALR(1). Коротко, это означает, что должно быть возможно определить, как разобрать любую часть входа, заглядывая вперёд не более, чем на одну лексему. Строго говоря, это описание LR(1)-грамматики, класс LALR(1) имеет дополнительные ограничения, которые не так просто объяснить. Но в обычной практике редко встречаются LR(1)-грамматики, которые не являются LALR(1). См. раздел 6.7 Загадочные конфликты свёртка/свёртка, для получения большей информации.

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

Для примера терминальных и нетерминальных символов можно использовать язык C. Лексемами C являются идентификаторы, константы (числовые и строковые), и различные ключевые слова, знаки арифметических операций и пунктуации. Таким образом, терминальные символы грамматики C это: `идентификатор', `число', `строка' и по одному символу на каждое ключевое слово, знак операции или пунктуации: `if', 'return', `const', `static', `int', `char', `знак плюс', `открывающая скобка', `закрывающая скобка', `запятая' и многие другие (эти лексемы могут быть разбиты на литеры, но это уже вопрос составления словарей, а не грамматики).

Вот простая функция на языке C, разбитая на лексемы:

Синтаксические группы C это: выражение, оператор, объявление и определение функции. Они представлены в грамматике C нетерминальными символами `выражение', `оператор', `объявление' и `определение функции'. Полная грамматика, для того, чтобы выразить смысл этих четырёх, использует десятки дополнительных языковых конструкций, каждой из которых соответствует свой нетерминальный символ. Пример выше является определением функции, он содержит одно объявление и один оператор. В операторе каждое `x' , так же, как и `x * x' являются выражениями.

Каждому нетерминальному символу должны быть сопоставлены правила грамматики, показывающие, как он собирается из более простых конструкций. Например, одним из операторов C является оператор return , это может быть описано правилом грамматики, неформально читающимся так:

`Оператор' может состоять из ключевого слова `return', `выражения' и `точки с запятой'.

Должно существовать множество других правил для `оператор', по одному на каждый вид оператора C.

Один нетерминальный символ должен быть отмечен как специальный, определяющий завершённое высказывание на языке. Он называется начальным символом . В компиляторе это означает полную программу на входе. В языке C эту роль играет нетерминальный символ `последовательность определений и объявлений'.

Например, `1 + 2' является правильным выражением C -- правильной частью программы на C -- но не является правильной целой программой на C. В контекстно-свободной грамматике C это следует из того, что `выражение' не является начальным символом.

Анализатор Bison читает на входе последовательность лексем и группирует их, используя правила грамматики. Если вход правилен, конечным результатом будет свёртка всей последовательности лексем в одну группу, которой соответствует начальный символ грамматики. Если мы используем грамматику C, весь входной текст в целом должен быть `последовательностью определений и объявлений'. Если это не так, анализатор сообщит о синтаксической ошибке.

Формальная грамматика -- это математическая конструкция. Чтобы определить язык для Bison, вы должны написать файл, описывающий грамматику в синтаксисе Bison -- файл грамматики Bison . См. раздел 4. Файлы грамматики Bison.

Нетерминальный символ формальной грамматики на входе Bison представляется идентификатором, таким же как идентификатор C. По соглашению их нужно записывать в нижнем регистре, например: expr , stmt или declaration .

Представление в Bison нетерминальных символов также называется типом лексем . Типы лексем также могут быть представлены идентификаторами в стиле C. По соглашению эти идентификаторы следует записывать в верхнем регистре, чтобы отличить их от нетерминалов, например, INTEGER , IDENTIFIER , IF , или RETURN . Терминальный символ, соответствующий конкретному ключевому слову языка следует называть так же, как это ключевое слово выглядит в верхнем регистре. Терминальный символ error зарезервирован для восстановления после ошибок. См. раздел 4.2 Символы, терминальные и нетерминальные.

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

Третий способ представления терминального символа -- представление строковой константой C из нескольких литер. См. раздел 4.2 Символы, терминальные и нетерминальные, для получения большей информации.

Правила грамматики также содержат выражение в синтаксисе Bison. Например, вот правило Bison для оператора C return . Точка с запятой в кавычках является однолитерной лексемой, представляющей часть синтаксиса оператора C, а отдельная точка с запятой и двоеточие являются знаками пунктуации Bison, используемыми во всех правилах.

Формальная грамматика выбирает лексемы только по их виду, например, если в правиле упоминается терминальный символ `целочисленная константа', это означает, что в этой позиции грамматически допустима любая целочисленная константа. Точное значение константы не имеет значения для разбора -- если `x+4' грамматически допустимо, то `x+1' или `x+3989' равно допустимы.

Но точное значение очень важно, чтобы после разбора определить, что означает входной текст. Компилятор, не могущий различить в программе константы 4, 1 и 3989, бесполезен! Поэтому каждая лексема в грамматике Bison характеризуется как типом лексемы, так и семантическим значением . См. раздел 4.5 Определение семантики языка.

Тип лексемы -- это терминальный символ, определённый в грамматике, такой как INTEGER , IDENTIFIER или ',' . Он даёт всю информацию, необходимую для принятия решения, где допустимо появления лексемы и как группировать её с другими лексемами. Правила грамматик не знают о лексемах ничего, кроме их типов.

Семантическое значение несёт всю остальную информацию о смысле лексемы, такую как значение целого или имя идентификатора (такие лексемы как ',' , просто знаки пунктуации, не нуждаются в каком-либо семантическом значении).

Например, входная лексема может классифицироваться как лексема типа INTEGER и иметь семантическое значение 4. Другая входная лексема может иметь тот же тип INTEGER , но значение 3989. Если правило грамматики говорит, что допустима лексема типа INTEGER , будет принята любая из этих двух лексем, потому что обе они имеют тип INTEGER . Когда анализатор принимает лексему, он отслеживает её семантическое значение.

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

Чтобы быть полезной, программа должна делать нечто большее, чем разбор входного текста -- она должны также создавать некий выход, основанный на входе. В грамматике Bison правило грамматики может содержать действие , состоящее из операторов C. Каждый раз, когда анализатор распознаёт текст, соответствующий правилу, выполняется его действие. См. раздел 4.5.3 Действия.

Чаще всего целью действия является вычисление семантического значения всей конструкции по семантическим значениям её частей. Предположим, например, что у нас есть правило, гласящее, что выражение может быть суммой двух выражений. Когда анализатор распознаёт такую сумму, каждое из подвыражений имеет семантическое значение, описывающее, как оно построено. Действию этого правила следует создать значение подобного вида для только что распознанного большего выражения.

Например, вот правило, говорящее, что выражение может быть суммой двух подвыражений:

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

Каждая лексема имеет семантическое значение. Аналогично, каждой лексеме сопоставлено положение, но тип положений одинаков для всех лексем и групп. Более того, создаваемый анализатор снабжён структурой данных для информации о положениях, задаваемой по умолчанию (см. раздел 4.6 Отслеживание положений, для получения дальнейшей информации).

Как и с семантическими значениями, в действиях можно получить доступ к положениям, используя специальный набор конструкций. В приведённом выше примере положение группы в целом -- @$ , в то время как положения подвыражений -- @1 и @3 .

Когда обнаруживается текст, соответствующий правилу, для вычисления семантического значения его левой части используется действие по умолчанию (см. раздел 4.5.3 Действия). Точно так же, для положений используется другое действие по умолчанию. Однако действия для положений в большинстве случаев достаточно, в том смысле, что обычно не нужно описывать формирование @$ для каждого правила. При вычислении нового положения для данной группы по умолчанию анализатор берёт начало первого символа и конец последнего.

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

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

Лексемы поступают из функции, называемой лексическим анализатором , которую вы должны каким-либо образом предоставить (например, написав её на C). Анализатор Bison вызывает лексический анализатор каждый раз, когда ему нужна новая лексема. Он не знает, что находится "внутри" лексемы (хотя её семантическое значение может отражать это). Обычно лексический анализатор получает лексемы анализом литер текста, но Bison не зависит от этого. См. раздел 5.2 Функция лексического анализатора yylex .

Обработайте описание грамматики Bison чтобы получить анализатор.
Скомпилируйте код, созданный Bison, так же, как любой другой файл с исходным кодом.
Соберите объектные файлы чтобы получить конечный продукт.

`%%' , `%' -- это знаки пунктуации, присутствующие в любом файле грамматики Bison для разделения его секций.

Объявления Bison задают имена терминальных и нетерминальных символов и могут также описывать приоритет операций и типы данных семантических значений различных символов.

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

Дополнительный код на C может содержать любой код на C, который вы хотите использовать. Часто здесь находится определение лексического анализатора yylex и подпрограммы, вызываемые действиями правил грамматики. В простых программах здесь может находится и вся остальная часть программы.

Уже около двух лет я участвую в OpenSource проекте SourceAnalyzer, и вот появилась необходимость написать парсер для языка Python, который должен уметь строить граф вызовов (Call Graph) и граф зависимостей классов (Class Graph Dependency). Если точнее, граф строится с помощью других инструментов, а парсер должен лишь подготовить для этих инструментов данные.

Процесс работы над парсером был довольно занятным и мне бы хотелось поделиться с вами приобретенным опытом, а также поведать о некоторых подводных камнях, которые встретились на этапе разработки.

Терминология

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

Анализ входного потока и разбиения его на токены (Лексический анализ)
Разбор токенов набором синтаксических правил (Синтаксический Анализ)

Построим правила преобразования входного потока:

Таким образом, после лексического анализа получим:

Далее следует пример грамматики, с помощью которой впоследствии, применяя правила, можно сделать разбор выражения:

В данном примере NUMBER, MULT, PLUS — по определению терминалы, или токены, определенные на этапе лексического анализа. expr, sign — не терминалы, так как являются составными единицами.

Данное введение не является сколь-либо исчерпывающим, поэтому за теорией следует обратиться к книге Flex&Bison O’Relly.

Грамматика

В мою задачу входило лишь выявление определения классов, функций и вызовов функций.

Для начала опишем нужную часть грамматики с помощью расширенной формы Бэкуса-Наура (РБНФ) (wiki).

Здесь [X] — 0 или 1 вхождение X , — 0 и более вхождений Y .

Для определения имени класса и его зависимостей вполне достаточно. Теперь для функций.

Кстати, предполагается, что код пользователя будет корректным (с точки зрения интерпретатора), иначе правила грамматики надо определять строже.

Отлично, на этом пока закончим с грамматикой и перейдем к лексеру (лексическому анализатору), так как перед разбором грамматики исходный python-код следует разбить на токены.

Лексический анализатор

Лексер генерируется программой Flex. Простейший пример:

Как скомпилировать данный пример:

ОК, теперь определимся с токенами. В грамматике мы уже использовали следующие:
CLASS, COLON, COMMA, DEF, DOT, ID, LBRACE, MESSAGE, RBRACE, OTHER, STAR
Еще нам понадобится DEFINED — зарезервированные слова Python.

Краткий разбор: комментарии, пустые строки и пробелы игнорируем. Все остальное (так называемый, поток токенов) отдаем на вход Bison.

Набор символов, который находит паттерн (например, по шаблону [ \t]+ ), помещается в yytext . По умолчанию yytext — это char pointer, но если добавить ключ -l при компиляции, то yytext будет восприниматься как char array. Перед тем, как вернуть бизону токен, запишем определенное по шаблону значение в переменную yylval (подробнее — далее).

Самое время перейти к описанию грамматики для Бизона.

Bison

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

Итак, заглядывая в пункт статьи Грамматика, попробуем составить грамматику для бизона:

В правиле Bison каждая лексема имеет значение. Значение группы, собираемой текущим правилом, хранится в $ , значения остальных лексем — в $1, $2, …

Значение, хранящееся в $n есть не что иное, как значение переменной yylval в момент, когда лексер возвращает токен.

Как работает анализатор. Происходит вызов функции yyparse из main , которая запускает анализ — читает лексемы, производит какие-то действия и завершает работу, если встречает конец входного текста ( return 0 ) или синтаксическую ошибку ( return 1 ).

Пробуем скомпилировать и затестить то, что имеем:

В принципе, верно, хотя и не совсем. Хотелось бы видеть “полное имя” в определении функции, то есть:

Для этого поступим следующим образом: заведем стек, в который будем добавлять имя текущего класса. Как только встречается определение функции — постепенно достаем из стека имена классов, конкатенируя с именем функции. Если встречается новый класс глубже по уровню — добавляем в стек, иначе удаляем из стека элементы, пока не дойдем до текущего уровня вложенности (и еще на единицу меньше), и добавляем новый класс в стек.

Идея и реализация далее.

Особенности Python

Очевидная проблема — узнать уровень вложенности. Как известно, в Python для этого используется табуляция (или пробелы). Поэтому надо хранить текущий отступ в какой-то глобальной переменной, доступной и анализатору, и лексеру. Руководство Bison говорит, что функция yyparse ожидает, что положение только что разобранной лексемы в тексте находится в глобальной переменной yylloc .

yylloc — это структура из четрыех элементов: first_line, first_column, last_line и last_column . В first_line будем хранить номер текущей строки (пригодится для отладки, да и входит в мою задачу), в last_column будем хранить отступ.

Вносим изменения в код. В лексере определим тип переменной yylloc и значение по умолчанию для номера строки:

Когда встречаем новую строку:

Если строка начинается с пробелов:

yyleng — длина найденной шаблоном лексемы. SPACES_PER_INDENT по умолчанию зададим равным 4 (по стандарту).

Если строка начинается с символа табуляции:

Теперь подкорректируем подсчет строк. В питоне есть тройные кавычки, используются обычно для длинного комментария документации. Для игнора напишем функцию:

Тут, на самом деле, можно было обойтись регулярным выражением, но тогда не получится верно определить номер строки — мы не сможем узнать количество съеденных регэкспом строк (или сможем? если да — пишите способ).

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

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

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

Компиляция грамматики

Общий принцип такой же, как с flex в первой части: мы перечисляем правила грамматики, и напротив каждого правила пишем сишный код, который будет выполняться во время свёртки правила.

В прошлый раз упомянули, что во время свёртки мы вынимаем из стека набор символов (строк или переменных), смотрим на их значения, задаём значение для свернувшейся переменной, и кладём её в стек вместо вынутых.

Разбор кода

%%, как и в 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 задаёт сам.

%%

Функция yylex нам больше не нужна: теперь входные символы будут поступать не из stdin , а от flex .
Кроме того, стёрли '\n' после EXPR (его проглотит flex ), и убрали все правила про NUM и DIGIT .

%option yylineno
%option noyywrap

Чтобы передать токен бизону, его значение записываем в глобальную (ох ужас!) переменную 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 состояний, и описаны они примерно так:

Для каждого состояния указаны правила, которые в этом состоянии распознаются (вместе с их номерами в грамматике), и перечислены действия, выполняемые для каждого входного символа. Не указано следующее состояние после свёртки; вместо этого автомат возвращается в состояние, прочитанное из стека, и в нём ищет правило «go to», соответствующее свежесвёрнутому нетерминалу. Таким образом, таблица переходов автомата получается двумерной: в каждом состоянии действие зависит только от входного символа, и не зависит от содержимого стека. (Но из стека берётся следующее состояние после свёртки.)

%%
int main ()

Код после второго тега %% копируется в парсер неизменным так же, как если бы он был в % .
Теперь, раз мы определили 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 не задан, тогда угадывать придётся и значения прочитанных токенов: бизон будет печатать только пустые скобки.

Конфликты в грамматике

Поскольку типичный источник конфликтов — арифметические выражения, то и намёки даются в виде указания приоритета операторов (выполнять умножение раньше сложения) и их ассоциативности (из операторов с равным приоритетом, который выполнять раньше). Чем ниже оператор в списке, тем выше приоритет. Операторы в одной строчке списка получают одинаковый приоритет.

%%

Для правоассоциативных операторов есть директива %right .
Противоестественность хака с приоритетами можно оценить на примере двусмысленности if (1) if (2) foo(); else bar();
Чтобы она распарсилась привычным образом — if (1) < if (2) foo(); else bar(); >— нужно, чтобы приоритет else был выше, чем у ')'
Оба этих терминала тяжело назвать операторами, и тем более тяжело задать им «естественный» приоритет.
Зато это работает!

«Грамматика с намёками» компактнее однозначной и в исходном виде (короче вдвое), и в виде автомата (сэкономили одно состояние).

Даже в однозначной грамматике могут возникать конфликты, связанные с принципом работы магазинного автомата: во время выполнения каждого действия он видит только один следующий символ ввода. Например, грамматика — однозначная, и ей соответствует всего два слова — sail и sale. Когда парсер сдвинул первую букву 's' и видит после неё 'a', он не может сделать выбор, сворачивать S1 или S2 : правильная свёртка зависит от того, какая буква будет после 'a'; но её автомат ещё не видит.
Это вторая причина, по которой парсер делают двухступенчатым: за счёт того, что лексер сжимает строки в токены и отбрасывает ненужные символы между токенами, LR-парсеру удаётся «дальше» заглядывать: не на одну букву, а на один токен вперёд.

Как это работает?

Как и у flex , ядро парсера — таблица переходов и небольшой цикл. Используется два параллельных стека: стек состояний yyssa и стек значений yyvsa — всё равно состояния и символы входят и выходят из стека всегда парами.

Как и в прошлый раз, символы, идентичные с точки зрения парсера, объединены в классы. В данном случае, классов 7, и они перечислены в файле .output . Массив static const unsigned char yytranslate[259] сопоставляет всем терминалам класс. (От 0 до 255 — обычные символы; 258 — объявленный нами терминал NUM ).

Таблицы переходов хитроумно объединены. В основной таблице хранятся описания действий: для сдвига (положительное число) — в какое состояние перейти; для свёртки (отрицательное) — по какому правилу свернуть. Удивительно, что таблица не только одномерная, но даже элементов в ней меньше, чем наших состояний (их 14).
Трюк в том, что индекс первого действия для каждого состояния хранится в отдельной таблице: YYPACT_NINF означает, что состоянию не соответствует ни один элемент yytable ; иначе говоря, выполняемое действие не зависит от входного символа.
Действия по умолчанию для каждого состояния хранятся в другой отдельной таблице: Не зависеть от входного символа может только выполнение свёртки, поэтому значения в yydefact — номера правил грамматики, по которым нужно сворачивать.

По индексу из yypact[n] хранится действие для состояния n и для класса символов 0. Действие для класса символов k хранится в yytable[yypact[n]+k] ; поэтому в yypact могут быть отрицательные индексы — это лишь «база», к которой будет прибавляться номер класса.

Чтобы проверить, к которому символу относится каждое действие в yytable , есть ещё одна таблица: Что мы видим? yytable[0] относится к символам класса 4, yytable[1] к символам класса 5, и так далее.
Попробуем найти какое-нибудь действие, например приведённые выше:
Класс терминала 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[] справа

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

Bison is upward compatible with Yacc: all properly-written Yacc grammars ought to work with Bison with no change. Anyone familiar with Yacc should be able to use Bison with little trouble. You need to be fluent in C or C++ programming in order to use Bison. Java is also supported as an experimental feature.

Downloading Bison

Documentation

Documentation for Bison is available online, as is documentation for most GNU software. You may also find more information about Bison by running info bison or man bison, or by looking at /usr/share/doc/bison/, /usr/local/doc/bison/, or similar directories on your system. A brief summary is available by running bison --help.

Mailing lists

Bison has the following mailing lists:

is used to discuss most aspects of Bison, including development and enhancement requests, as well as bug reports. is for general user help and discussion. is for patches to the source code, to improve or fix bugs in Bison. We prefer patches against the latest Savannah sources.

Announcements about Bison and most other GNU software are made on info-gnu (archive).

Security reports that should not be made immediately public can be sent directly to the maintainer. If there is no response to an urgent issue, you can escalate to the general security mailing list for advice.

Getting involved

Development of Bison, and GNU in general, is a volunteer effort, and you can contribute. For information, please read How to help GNU. If you'd like to get involved, it's a good idea to join the discussion mailing list (see above).

Licensing

Bison is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3 of the License, or (at your option) any later version.

“The Free Software Foundation (FSF) is a nonprofit with a worldwide mission to promote computer user freedom. We defend the rights of all software users.”

Please see the Translations README for information on coordinating and submitting translations of this article.

Читайте также: