Начало
Учебные материалы
Разработка компиляторов и интерпретаторов
Способы описания синтаксиса Генератор синтаксических анализаторов BISON Принципы работы BISON, интеграция BISON и FLEX, обработка синтаксических ошибок Создание и обработка деревьев разбора Генератор трансляторов CAIO, пример интерпретатора Пример компилятора Сравнение инструментов для разработки трансляторов Индивидуальное задание LLVM
Генератор синтаксических анализаторов BISON
BISON используется для создания синтаксического блока транслятора. Структура описания такая же как у FLEX:
объявления, опции и вставляемый код %% правила %% дополнительные подпрограммы
По описанию будет сгенерирована функция int yyparse(), набор таблиц и вспомогательных подпрограмм. На вход этой функции поступает последовательность токенов (типизированных лексем), а выходом является дерево синтаксического разбора (последовательность применений правил грамматики). Для получения токена вызывается функция yylex(), которая должна вернуть тип лексемы (целое число), а ассоциированное с ней значение поместить в глобальную переменную yylval. Лексемы, состоящие из одного символа, можно не определять как токены и писать в правилах как символ в апострофах, например, '=' или '('.
В первом разделе задаются стартовый символ грамматики, имена токенов (терминальных символов грамматики) и синонимы для них, приоритеты операций, структура элементов стека.
Стартовый символ грамматики задается с помощью конструкции %start символ. По умолчанию стартовым является первый определяемый нетерминальный символ.
Для вставки произвольного кода в начало генерируемой программы применяются %{ %} и %code top { }. С помощью %code provides { } можно добавить объявления в генерируемый заголовочный файл.
Так как с разными символами грамматики могут связаны значения разных типов, то для хранения этих значений во время разбора с помощью %union определяется тип-объединение, в которой для каждого типа значения задается отдельный элемент:
%union {
int val;
void *ptr;
struct Point { int x,y; } point;
}
По умолчанию с символами связано целое число. Для указания типа нетерминальных символов и токенов используется соответственно %type и %token:
%type <ptr> operator program %type <val> expression %token <val> NUMBER IDENT %token LE GE
Данное определение указывает, что значения для нетерминальных символов operator и program хранятся в элементе ptr объединения, для токенов NUMBER и IDENT – в элементе val, а токенам LE и GE дополнительная информация не нужна.
После имени токена можно написать его лексическое представление в кавычках и использовать его в правилах для повышения наглядности:
%token LE "<=" GE ">=" %token IF "if" ELSE "else"
Имя токена всё равно должно быть задано, так как оно необходимо для определения константы, используемой в лексическом анализаторе.
Для задания приоритетов операций и упрощения правил используются объявления %left, %right и %nonassoc:
%right '=' %nonassoc '<' '>' "<=" ">=" "!=" "==" %left '+' '-' %left '*' '/' %left UMINUS
Операция = имеет наименьший приоритет и выполняется справа налево (a=b=c), операции сравнения не могут комбинироваться и имеют более высокий приоритет, операции сложения и вычитания выполняются слева направо, а операция унарный минус имеет наивысший приоритет.
Во втором разделе задаются правила грамматики в формате:
символ : правило1 | правило2 … ;
Для каждого нетерминального символа должно быть только одно определение. После каждого правила можно написать код на языке C/C++ в {}, получающий из значений, связанных с символами в правиле, значения для определяемого символа. Для обращения к значениям символов используется $n, где n – номер символа в правиле, а для обращения к значению символа-результата – $$.
В последнем разделе можно написать любые подпрограммы на языке на C или C++, которые будут добавлены к сгенерированной программе.
Калькулятор для целых чисел:
%{
#include <ctype.h>
#include <stdio.h>
void yyerror(const char *);
int yylex();
%}
%token DIGIT
%left '+' '-'
%left '*' '/'
%left UMINUS
%%
program:
| program expr '\n' { printf("%d\n",$2); }
;
expr:
expr '+' expr { $$ = $1+$3; }
| expr '-' expr { $$ = $1-$3; }
| expr '*' expr { $$ = $1*$3; }
| expr '/' expr { $$ = $1/$3; }
| '-' expr %prec UMINUS { $$ = -$2; }
| '(' expr ')' { $$ = $2; }
| number { $$ = $1; }
;
number: DIGIT { $$=$1;}
| number DIGIT { $$=$1*10+$2;}
;
%%
int yylex()
{
int ch;
while((ch=getchar())==' ')
; // пропустить пробелы
if(ch==EOF) return 0;
if(isdigit(ch)) {
yylval=ch-'0';
return DIGIT;
}
return ch;
}
void yyerror(const char *msg)
{ printf("%s\n",msg);
}
int main()
{ return yyparse();
}
УпражненияРешите с использованием BISON следующие задачи: 1576, 1511, 459, 95, 49, 1333, 1233, 63
Пример решения для задачи 459:
%{
#include <ctype.h>
#include <stdio.h>
void yyerror(const char *);
int yylex();
int nerrors=0;
int nline=0;
int nop=0;
%}
%token NUMBER
%%
expr: NUMBER znak oper {++nop; } | '-' NUMBER | '-' '(' expr ')' {++nop; }
| '(' expr ')' | expr znak oper {++nop;} ;
znak: '+' | '-' | '*' | '/';
oper: NUMBER | '(' expr ')' ;
%%
char str[200];
int pos;
int yylex()
{
while(str[pos]==' ')
++pos; // пропустить пробелы
if(str[pos]==0 || str[pos]=='\n') return 0;
if(isdigit(str[pos])) {
if(str[pos++]>'0')
while(isdigit(str[pos]))
++pos;
return NUMBER;
}
return str[pos++];
}
void yyerror(const char *msg)
{ printf("%d\n",nline);
++nerrors;
}
int main()
{ while(fgets(str,sizeof(str),stdin))
{ ++nline;
pos=0;
nop=0;
if(yyparse()==0 && nop==0)
yyerror("nop==0");
}
if(nerrors==0) printf("0\n");
}
