GNU bölény - GNU Bison
 | |
| Eredeti szerző (k) | Robert Corbett |
|---|---|
| Fejlesztő (k) | A GNU projekt |
| Első kiadás | 1985. június |
| Stabil kiadás | 3.8.1 / 2021. szeptember 11
|
| Adattár | |
| Beírva | C és m4 |
| Operációs rendszer | Unix-szerű |
| típus | Parser generátor |
| Engedély | GPL |
| Weboldal |
www 
|
A GNU Bison , közismert nevén Bison , egy elemző generátor , amely a GNU projekt része . Bölény elolvassa a kontextusmentes nyelv specifikációját , figyelmeztet az értelmezési kétértelműségekre, és létrehoz egy elemzőt, amely elolvassa a tokenek sorozatát, és eldönti, hogy a sorozat megfelel-e a nyelvtan által meghatározott szintaxisnak. A generált elemzők hordozhatók: nem igényelnek külön fordítókat. A Bison alapértelmezés szerint LALR (1) elemzőket generál, de létrehozhat kanonikus LR , IELR (1) és GLR elemzőket is.
A POSIX módban, Bison kompatibilis Yacc , hanem több kiterjesztése át ezt a korábbi program, beleértve a
- Ellenpéldák generálása konfliktusokra
- Helykövetés (pl. Fájl, sor, oszlop)
- Gazdag és nemzetközivé tehető szintaktikai hibaüzenetek a generált elemzőkben
- Testreszabható szintaktikai hiba generálás,
- Visszatérő elemzők
- Push elemzők, automatikus kiegészítéssel
- A megnevezett hivatkozások támogatása
- Többféle jelentés (grafikus, XML) a generált elemzőn
- Több programozási nyelv támogatása ( C , C ++ , D vagy Java )
A Flex -et , az automatikus lexikai elemzőt gyakran használják a Bison -szal a bemeneti adatok tokenizálásához és a Bison tokenek biztosításához.
A Bison -t eredetileg Robert Corbett írta 1985 -ben. Később, 1989 -ben Robert Corbett kiadott egy másik elemző generátort, Berkeley Yacc néven . A bölényt Richard Stallman tette Yacc-kompatibilisvé .
A Bison ingyenes szoftver, és a GNU General Public License alatt érhető el , egy (az alábbiakban tárgyalt) kivétellel, amely lehetővé teszi, hogy generált kódját a licenc copyleft követelményeinek kiváltása nélkül használják .
Jellemzők
Ellenpélda generálása
Az LR elemző generátorok egyik kényes kérdése a konfliktusok megoldása (váltás/csökkentés és konfliktusok csökkentése/csökkentése). A konfliktusok megoldása általában a jelentésekben leírt elemző automatikus elemzést és a felhasználó bizonyos szakértelmét igényli. Az ellenpéldák segítenek néhány konfliktus gyors megértésében, sőt azt is bizonyítani tudják, hogy a probléma az, hogy a nyelvtan valójában kétértelmű.
Például a nyelvtantól, amely a hírhedt lelógó más problémától szenved - írja Bison
doc/ha-akkor-else.y: figyelmeztetés : shift/konfliktus csökkentése az "else" jelzőn [ -találkozópéldák ] Példa: "if" expr "then" "if" expr "then" stmt • "else" stmt Váltási levezetés if_stmt ↳ "ha" expr "majd" stmt ↳ if_stmt ↳ "ha" expr "majd" stmt • "más" STMT Példa: "ha" expr "majd" "ha" expr "majd" stmt • "más" stmt Csökkentse a levezetést if_stmt ↳ "if" expr ", akkor" stmt "else" stmt ↳ if_stmt ↳ "if" expr "then" stmt •
Visszatérés
A Reentrancy egy olyan szolgáltatás, amelyet hozzáadtak a Bison -hoz, és nem létezik a Yacc -ban.
Általában a Bison olyan elemzőt állít elő, amely nem reentrant . Az ismétlődés eléréséhez a nyilatkozatot %define api.purekell használni. A Bölény visszacsatolásról további részletek a Bölény kézikönyvben találhatók.
Kimeneti nyelvek
A bölény képes kódot generálni a C , C ++ , D és Java számára .
Mert a Bison generált értelmező más nyelvek a nyelv kötelező eszköz, mint például korty lehet használni.
Licenc és a generált kód terjesztése
Mivel a Bison forráskódot generál, amelyet más szoftverprojektek forráskódjához adnak hozzá, néhány egyszerű, de érdekes szerzői jogi kérdést vet fel.
GPL-kompatibilis licenc nem szükséges
A Bison által generált kód jelentős mennyiségű kódot tartalmaz magából a Bison projektből. A Bison csomagot a GNU General Public License (GPL) feltételei szerint terjesztik, de hozzáadtak egy kivételt, így a GPL nem vonatkozik a kimenetre.
A Bison korábbi kiadásai kikötötték, hogy a kimenet egyes részeit a GPL alapján is engedélyezték, mivel az eredeti forráskódból származó yyparse () függvény a kimenetben szerepelt.
Csomagok forgalmazása Bison segítségével
A Bison -t használó szabad szoftverprojektek választhatnak, hogy terjesztik -e a projektjük által a Bison -ba táplált forráskódot, vagy a Bison által kiadott C kódot. Mindkettő elegendő ahhoz, hogy a címzett össze tudja állítani a projekt forráskódját. Azonban csak a bemenet terjesztésével jár az a kisebb kényelmetlenség, hogy a címzetteknek telepíteniük kell a Bison kompatibilis példányát, hogy a projekt összeállításakor elő tudják állítani a szükséges C kódot. És terjesztése csak a C kódot kimenet, megteremti a probléma, hogy nagyon nehéz a címzettek nevét, módosíthatja az elemző, mivel ez a kód volt írva sem az emberi, sem az emberekben - az a célja, hogy kell etetni közvetlenül a C fordító.
Ezek a problémák elkerülhetők a bemeneti fájlok és a generált kód terjesztésével. A legtöbb ember a generált kód használatával fordít, nem különbözik más szoftvercsomagoktól, de bárki, aki módosítani szeretné az elemző összetevőt, először módosíthatja a bemeneti fájlokat, és a generálás előtt újra generálhatja a létrehozott fájlokat. A mindkettőt terjesztő projektek rendszerint nem rendelkeznek a generált fájlokkal a felülvizsgálati vezérlőrendszereikben . A fájlok csak kiadáskor jönnek létre.
Egyes licencek, mint például a GPL , megkövetelik, hogy a forráskód " a munka előnyben részesített formája legyen a módosításhoz ". A GPL Bison projektjeinek tehát el kell osztaniuk azokat a fájlokat, amelyek a Bison számára szolgálnak. Természetesen a generált fájlokat is tartalmazhatják.
Használat
Mivel a Bison -t a Yacc helyettesítésére írták, és nagyrészt kompatibilis, a Bison -t használó projektek kódja egyformán betölthető a Yacc -ba. Ez megnehezíti annak megállapítását, hogy egy projekt "használ-e" Bison-specifikus forráskódot vagy sem. Sok esetben a Bölény "használatát" triviálisan helyettesítheti a Yacc vagy más származékai egyenértékű használata.
A Bison olyan tulajdonságokkal rendelkezik, amelyek nem találhatók meg a Yacc -ban, ezért néhány projektről valóban azt mondhatjuk, hogy "használja" a Bison -t, mivel a Yacc nem lenne elegendő.
A következő lista azokról a projektekről szól, amelyekről ismert, hogy "használnak" Bison-t lazább értelemben, szabad szoftverfejlesztő eszközöket használnak, és olyan kódot terjesztenek, amelyet Bison-ba vagy Bison-kompatibilis csomagba kívánnak betölteni.
- A Bash shell yacc nyelvtant használ a parancsbevitel elemzésére.
- Bölény saját nyelvtani elemzőjét a Bölény generálja.
- A CMake több Bison nyelvtant használ.
- A GCC a Bison használatával indult, de 2004-ben (3.4-es verzió) és C-ben és Objective-C-ben (4.1-es verzió) váltott kézzel írott rekurzív-leszármazási elemzőre
- A Go programozási nyelv (GC) a Bison-t használta, de az 1.5-ös verzióban kézzel írott szkennerre és elemzőre váltott.
- A LilyPond megköveteli, hogy a Bison készítse el az elemzőt.
- MySQL
- A GNU Octave egy Bison által generált elemzőt használ.
- A Perl 5 Bison által generált elemzőt használ 5.10-től kezdődően.
- A PHP programozási nyelv (Zend Parser).
- PostgreSQL
- A Ruby MRI , a Ruby programozási nyelv referencia megvalósítása, Bison grammatikán alapul.
- A syslog-ng több Bison grammatikát használ össze.
Egy teljes újrafeldolgozó példa
A következő példa bemutatja, hogyan lehet a Bison és a flex segítségével írni egy egyszerű számolóprogramot (csak összeadás és szorzás) és egy programot absztrakt szintaxisfa létrehozásához . A következő két fájl a szintaxisfa függvények meghatározását és megvalósítását tartalmazza.
/*
* Expression.h
* Definition of the structure used to build the syntax tree.
*/
#ifndef __EXPRESSION_H__
#define __EXPRESSION_H__
/**
* @brief The operation type
*/
typedef enum tagEOperationType
{
eVALUE,
eMULTIPLY,
eADD
} EOperationType;
/**
* @brief The expression structure
*/
typedef struct tagSExpression
{
EOperationType type; /* /< type of operation */
int value; /* /< valid only when type is eVALUE */
struct tagSExpression *left; /* /< left side of the tree */
struct tagSExpression *right; /* /< right side of the tree */
} SExpression;
/**
* @brief It creates an identifier
* @param value The number value
* @return The expression or NULL in case of no memory
*/
SExpression *createNumber(int value);
/**
* @brief It creates an operation
* @param type The operation type
* @param left The left operand
* @param right The right operand
* @return The expression or NULL in case of no memory
*/
SExpression *createOperation(EOperationType type, SExpression *left, SExpression *right);
/**
* @brief Deletes a expression
* @param b The expression
*/
void deleteExpression(SExpression *b);
#endif /* __EXPRESSION_H__ */
/*
* Expression.c
* Implementation of functions used to build the syntax tree.
*/
#include "Expression.h"
#include <stdlib.h>
/**
* @brief Allocates space for expression
* @return The expression or NULL if not enough memory
*/
static SExpression *allocateExpression()
{
SExpression *b = (SExpression *)malloc(sizeof(SExpression));
if (b == NULL)
return NULL;
b->type = eVALUE;
b->value = 0;
b->left = NULL;
b->right = NULL;
return b;
}
SExpression *createNumber(int value)
{
SExpression *b = allocateExpression();
if (b == NULL)
return NULL;
b->type = eVALUE;
b->value = value;
return b;
}
SExpression *createOperation(EOperationType type, SExpression *left, SExpression *right)
{
SExpression *b = allocateExpression();
if (b == NULL)
return NULL;
b->type = type;
b->left = left;
b->right = right;
return b;
}
void deleteExpression(SExpression *b)
{
if (b == NULL)
return;
deleteExpression(b->left);
deleteExpression(b->right);
free(b);
}
A Bison Bars elemzőhöz szükséges tokenek a flex használatával jönnek létre.
%{
/*
* Lexer.l file
* To generate the lexical analyzer run: "flex Lexer.l"
*/
#include "Expression.h"
#include "Parser.h"
#include <stdio.h>
%}
%option outfile="Lexer.c" header-file="Lexer.h"
%option warn nodefault
%option reentrant noyywrap never-interactive nounistd
%option bison-bridge
%%
[ \r\n\t]* { continue; /* Skip blanks. */ }
[0-9]+ { sscanf(yytext, "%d", &yylval->value); return TOKEN_NUMBER; }
"*" { return TOKEN_STAR; }
"+" { return TOKEN_PLUS; }
"(" { return TOKEN_LPAREN; }
")" { return TOKEN_RPAREN; }
. { continue; /* Ignore unexpected characters. */}
%%
int yyerror(const char *msg) {
fprintf(stderr, "Error: %s\n", msg);
return 0;
}
A tokenek neve általában semleges: "TOKEN_PLUS" és "TOKEN_STAR", nem "TOKEN_ADD" és "TOKEN_MULTIPLY". Például, ha támogatnánk az egységes "+" -t (mint a "+1" -ben), helytelen lenne ezt a "+" "TOKEN_ADD" nevet adni. Egy olyan nyelven, mint a C, az "int *ptr" a mutató, nem pedig a termék definícióját jelenti: helytelen lenne ezt a " *" "TOKEN_MULTIPLY" nevet adni.
Mivel a tokeneket a flex biztosítja, biztosítanunk kell az elemző és a lexer közötti kommunikáció eszközét . A kommunikációhoz használt adattípust, YYSTYPE , Bison %union deklarációval állítjuk be .
Mivel ebben a mintában a flex és a yacc reentrant verzióját használjuk, kénytelenek vagyunk megadni a yylex függvény paramétereit , amikor az yyparse meghívja . Ez a Bison %lex-param és %parse-param deklarációkon keresztül történik.
%{
/*
* Parser.y file
* To generate the parser run: "bison Parser.y"
*/
#include "Expression.h"
#include "Parser.h"
#include "Lexer.h"
int yyerror(SExpression **expression, yyscan_t scanner, const char *msg) {
/* Add error handling routine as needed */
}
%}
%code requires {
typedef void* yyscan_t;
}
%output "Parser.c"
%defines "Parser.h"
%define api.pure
%lex-param { yyscan_t scanner }
%parse-param { SExpression **expression }
%parse-param { yyscan_t scanner }
%union {
int value;
SExpression *expression;
}
%token TOKEN_LPAREN "("
%token TOKEN_RPAREN ")"
%token TOKEN_PLUS "+"
%token TOKEN_STAR "*"
%token <value> TOKEN_NUMBER "number"
%type <expression> expr
/* Precedence (increasing) and associativity:
a+b+c is (a+b)+c: left associativity
a+b*c is a+(b*c): the precedence of "*" is higher than that of "+". */
%left "+"
%left "*"
%%
input
: expr { *expression = $1; }
;
expr
: expr[L] "+" expr[R] { $$ = createOperation( eADD, $L, $R ); }
| expr[L] "*" expr[R] { $$ = createOperation( eMULTIPLY, $L, $R ); }
| "(" expr[E] ")" { $$ = $E; }
| "number" { $$ = createNumber($1); }
;
%%
A Bison által generált elemző és a flex által létrehozott szkenner segítségével a szintaxisfa megszerzéséhez szükséges kód a következő.
/*
* main.c file
*/
#include "Expression.h"
#include "Parser.h"
#include "Lexer.h"
#include <stdio.h>
int yyparse(SExpression **expression, yyscan_t scanner);
SExpression *getAST(const char *expr)
{
SExpression *expression;
yyscan_t scanner;
YY_BUFFER_STATE state;
if (yylex_init(&scanner)) {
/* could not initialize */
return NULL;
}
state = yy_scan_string(expr, scanner);
if (yyparse(&expression, scanner)) {
/* error parsing */
return NULL;
}
yy_delete_buffer(state, scanner);
yylex_destroy(scanner);
return expression;
}
int evaluate(SExpression *e)
{
switch (e->type) {
case eVALUE:
return e->value;
case eMULTIPLY:
return evaluate(e->left) * evaluate(e->right);
case eADD:
return evaluate(e->left) + evaluate(e->right);
default:
/* should not be here */
return 0;
}
}
int main(void)
{
char test[] = " 4 + 2*10 + 3*( 5 + 1 )";
SExpression *e = getAST(test);
int result = evaluate(e);
printf("Result of '%s' is %d\n", test, result);
deleteExpression(e);
return 0;
}
Egy egyszerű makefile a projekt felépítéséhez a következő.
# Makefile
FILES = Lexer.c Parser.c Expression.c main.c
CC = g++
CFLAGS = -g -ansi
test: $(FILES)
$(CC) $(CFLAGS) $(FILES) -o test
Lexer.c: Lexer.l
flex Lexer.l
Parser.c: Parser.y Lexer.c
bison Parser.y
clean:
rm -f *.o *~ Lexer.c Lexer.h Parser.c Parser.h test
Lásd még
- Berkeley Yacc (byacc) - egy másik ingyenes szoftver Yacc helyettesítő, ugyanazzal a szerzővel, mint a GNU Bison
- ANTLR Másik eszköz a nyelvfelismeréshez, egy másik nyílt forráskódú elemzőgenerátor
Hivatkozások
További irodalom
- Levine, John (2009. augusztus). flex & bison . O'Reilly Media. ISBN 978-0-596-15597-1.
