Linux bison что это

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

Bison can be found on the main GNU ftp server: http://ftp.gnu.org/gnu/bison/ (via HTTP) and ftp://ftp.gnu.org/gnu/bison/ (via FTP). It can also be found on the GNU mirrors; please use a mirror if possible.

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:

bug-bison is used to discuss most aspects of Bison, including development and enhancement requests, as well as bug reports.
help-bison is for general user help and discussion.
bison-patches 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).

Test releases Trying the latest test release (when available) is always appreciated. Test releases of Bison can be found at http://alpha.gnu.org/gnu/bison/ (via HTTP) and ftp://alpha.gnu.org/gnu/bison/ (via FTP). Development For development sources, issue trackers, and other information, please see the Bison project page at savannah.gnu.org. Translating Bison To translate Bison’s messages into other languages, please see the Translation Project page for Bison. If you have a new translation of the message strings, or updates to the existing strings, please have the changes made in this repository. Only translations from this site will be incorporated into Bison. For more information, see the Translation Project. Maintainer Bison is currently being maintained by Akim Demaille and Paul Eggert. Please use the mailing lists for contact.

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 send general FSF & GNU inquiries to . There are also other ways to contact the FSF. Broken links and other corrections or suggestions can be sent to .

For information on coordinating and submitting translations of our web pages, see Translations README. —> Please see the Translations README for information on coordinating and submitting translations of this article.

Источник

1. Что такое Bison и зачем он нужен

Bison – это GNU -выпуск известной программы YACC , предназначенной для порождения компиляторов по описанной пользователем КС-грамматике.

Одним из следствий расширения возможностей и доступности использования вычислительной техники стало производство прикладных программных систем со всё более разнообразным и сложным поведением. При этом краеугольный принцип кибернетики — принцип необходимого и достаточного разнообразия, сформулированный Н.Виннером и Р.Эшби ещё до 1960 г ., гласит, что степень разнообразия управления подобной сущностью должна соответствовать степени разнообразия её поведения.

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

К примеру, для управления воздушным движением, в т.ч. в Российской Федерации, соответствующими международными организациями разработан и используется формальный язык из нескольких десятков предложений, однозначно сообщающих в автоматизированном и ручном режимах о каждом достаточно значимом событии в использовании самолёта и его характеристиках: взлёте, изменении курса, прохождении контрольной точки полёта, посадке, возникновении различных иных вероятных обстоятельств, которые можно и нужно предвидеть . Обычным является дополнение и уточнение время от времени этого списка команд и/или их параметров по решению соответствующих комитетов. Эти изменения необходимо быстро и надёжно вносить в соответствующие системы управления.

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

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

Важность и всё большая распространённость этой задачи была осознана в программировании довольно быстро и поэтому появился ряд разнообразных программных инструментов для автоматизированной разработки компиляторов для языков, определяемых контекстно-свободными грамматиками. Так, само название известного более двух десятилетий компилятора компиляторов YACC переводится как «ещё один компилятор компиляторов» ( Yet another compiler compiler ). В качестве пробы сил и оттачивания мастерства производство подобных систем продолжается и сейчас, особенно в технических университетах ( см ., например, http :// www . forth . org . ru ) .

Свой компилятор компиляторов под названием «СУПЕР» был создан более 15 лет назад и в ВЦ АН СССР (ныне ВЦ РАН, www.ccas.ru ) под рук . л аур . гос . премии, зав. сект. ВЦ РАН, доц. МФТИ, к.ф.м.н . Владимира Михайловича Курочкина, ныне покойного. Последний более 30 лет назад основал на ФУПМе и курс «Теория и реализация языков программирования».

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

2. Кто его поддерживает и под какой ОС он пасётся

Bison доступен для установки во всех распространённых разновидностях ОС Linux . Возможно, он уже установлен на вашей системе. Просто наберите bison без параметров и посмотрите на её отклик…

3. Где находится исходное описание работы с Bison и где – его русский перевод

http :// www . gnu . org / software / bison / manual / — исходное описание руководства по Bison на английском языке (талантом писать кратко и доступно автор наделён весьма скромно).

4. Общая схема получения пользовательского компилятора с помощью Bison

4.1. Записать КС-грамматику в понятном для Bison виде

Тип н / д должен быть “. y ” (наследие YACC и способ прямой (но не обратной, т .е Bison шире YACC ) совместимости с YACC ). Например, foo . y или task . y .

Читайте также: Nano editor для windows

Тип принимаемых будущим компилятором лексем (основных знаков) определяется макро YYSTYPE , например:

#define YYSTYPE char

#define YYSTYPE double

При этом основные знаки алфавита пользовательской грамматики обозначаются словами из больших (латинских) букв и должны явно определяться после ключевого слова % token , например:

% token ONE , TWO // О пределяются два осн . знака ONE и TWO .

Вспомогательные знаки сразу можно использовать в правилах, их принято обозначать словами из малых латинских букв. Например, для грамматики a ^ n :

exp : exp A // S -> Sa (вид обозначений в пояснениях — уже из курса ТРЯП)

// или, что тоже самое :

Начальным знаком (аксиомой) грамматики по умолчанию считается первый употреблённый вспомогательный знак в первом приведённом правиле грамматики. В данном случае как аксиома будет распознана “ exp ”.

В фигурных скобках после каждого правила грамматики можно указать связанные с ним действия в стиле оператора Си. Наличие таких связок (правило + действие) говорит о том, что это не просто КС-грамматика, а атрибутная грамматика (см. гл. 5 по курсу ТРЯП).

В данном примере подсчитывается степень правильно введённой цепочки из n знаков ‘ a ’ (распознаваемых в лексическом анализаторе yylex (), который пишется (обеспечивается) пользователем). Заодно с помощью printf () показывается порядок применения правил.

Из особых обозначений (кроме обычных для самого языка Си) здесь используются именователи смысловых значений правила, а именно $$ — означает имя переменной, содержащую смысловое значение левой части правила (здесь, число прочитанных знаков ‘ a ’), а $1, $2, …, $ n – соответственно имена переменных для смысловых значений 1-го, 2-го и т.д. члена из правой части правила.

4.2. Запустить Bison для записанной грамматики:

При отсутствии ошибок вы должны получить н / д с именем foo . tab . c , содержащий текст разборщика предложений yyparse ().

4.3. Подготовить в ручную или с использованием других инструментальных средств (например, LEX ) лексический распознаватель yylex (), обработчик ошибок yyerror () и главную программу main ()

Программа main () вызывает порождённый Bison ’ ом разборщик предложений yyparse (). Последняя программа, в свою очередь, обращается по мере необходимости за очередной лексемой к yylex (), а при обнаружении ошибки разбора — к yyerror (). Обратите внимание, что в грамматике для синтаксического разборщика * yyparse ()” необходимо предусмотреть обработку (порождение) знаков конца строки и конца всего н / д , иначе никакая введённая цепочка не будет признана правильной, поскольку содержит хотя бы один из этих знаков.

Примеры программирования указанных функций для соответствующих языков приведены ниже в пунктах 4.2 и 4.3.

4.4. Совместная компиляция подготовленных программ обычным компилятором Си

Вы можете, к примеру, добавить тексты программ yylex (), yyerror () и main () в конец н / д с текстом программы yyparse в н / д foo . tab . c , либо создать короткую программку с простейшими включениями их текстов, например,

# include “ main . c ”

И откомпилировать их обычным компилятором Си. Под Linux эта команда выглядит так (если все программы для компиляции уже собраны в н / д simple _ CF . tab . c , а исполнимую программу мы хотим назвать simple _ CF ):

cc — o simple _ CF simple _ CF . tab . c

4.5. Запуск полученного компилятора

Производится как обычно. Для примера выше, это:

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

5. Законченные примеры применения Bison для некоторых простых грамматик

5.1. Пример для грамматики < а^ n | n >= 0>.

(Примеры цепочек: а, аа , ааа , …, а^ n ).

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

/* Simplest Context free grammar ( a^n ) */

#define YYSTYPE char // Тип входного знака

void yyerror (char const *);

// Main symbols of grammar (synonyms: terminals, tokens, etc.)

%% /* Правила грамматики и связанные с ними действия */

Источник

Парсим Python код с помощью Flex и Bison

Вступление

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

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

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

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

Процесс разработки парсера был разделен на две основных составляющих:

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

Давайте рассмотрим маленький примерчик. Пусть есть выражение (или входной поток данных):

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

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

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

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

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

Грамматика

Полную грамматику для языка Python (версии 2.5.2) можно найти здесь:
http://docs.python.org/release/2.5.2/ref/grammar.txt

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

Для начала опишем нужную часть грамматики с помощью расширенной формы Бэкуса-Наура (РБНФ) (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 в момент, когда лексер возвращает токен.

Запуская Bison с параметром -d , генерируется файл имя.tab.h , он содержит макроопределения типов лексем, которые используются в лексере. Каждой лексеме соответствует число > 257 . Данный файл следует включить в лексер, что мы и сделали: #include «pyparser.tab.h» .

Как работает анализатор. Происходит вызов функции 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 (по стандарту).

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

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

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

Также не забываем игнорить строку комментариев:

Переходим к стековому алгоритму.

Определяем вложенность функции

Действуем по алгоритму, описанному мною выше.

Источник

Linux bison что это

Bison

Официальная ссылка

Содержимое Bison

Программы

Описания

bison

Зависимости Bison