GNU Bison

Fra Wikipedia, den frie encyklopedi
Hopp til navigering Hopp til søk
GNU Bison
GNU Bison
SkaperRobert Corbett
UtviklerRobert Corbett, Richard Stallman m.fl.
Utgitt1988; 30 år siden (1988)
Nyeste versjon3.4.1 (22. mai 2019; 29 dager siden (2019-05-22))
StatusAktiv
OperativsystemUnix, Unix-lignende m.fl.
Skrevet iC og m4
TypeParsergenerator
LisensGNU General Public License versjon 3[1]
Nettstedwww.gnu.org/software/bison/
ForgjengerYacc, yacchack, Berkeley Yacc, zoo, Byson
EtterfølgerPLY, goyacc og omaclyacc

GNU Bison er en fri og åpen parsergenerator for Unix og Unix-liknende operativsystemer.[2] GNU Bison inngår i GNU-prosjektet og er tilgjengelig under GNU General Public License versjon 3, med unntak som tillater den genererte kode å bli brukt uten lisensen copyleft.[1][3]

GNU Bison leser en spesifikasjon i en kontekstfri grammatikk, advarer mot tvetydigheter og genererer en parser i C, C++[4] eller Java.[5] Parseren leser sekvensen av token og bestemmer hvorvidt sekvensen følger syntaksen som er spesifisert av grammatikken. Den genererte parser er plattformuavhengig, og er ikke avhengig av noen spesifikk kompilator. GNU Bison genererer LALR-parsere som standard, men kan også generere LR(1)-, IELR(1)- og GLR-parsere.[6][7] Flex, som genererer leksikalske analysatorer, kan dele strømmen av innmatede data opp i token før de behandles av GNU Bison.

GNU Bison ble skapt i 1988 av Robert Corbett fra University of Berkeley; den 2. september 1989 lanserte han også parsergeneratoren Berkeley Yacc, og GNU Bison ble påvirket mye av tidligere versjoner av Berkeley Yacc.[8] Richard Stallman gjorde programmet kompatibelt med POSIX og Yacc,[9] men det har flere forbedringer i forhold til Yacc. Siste versjon er 3.4.1 og ble lansert 22. mai 2019.

Historie[rediger | rediger kilde]

Yacc[rediger | rediger kilde]

Utdypende artikler: Yacc og TMG

GNU Bison oppstod som en avlegger av YaccYet Another Compiler Compiler.[10][11] Yacc ble laget i 1971 av Stephen C. Johnson ved Bell Laboratories innenfor AT&T Corporation.[12] Programmet ble opprinnelig skrevet i programmeringsspråket B på en 36-biter stormaskin av typen Ge-635 fra General Electric.[12][13] Det ble imidlertid raskt skrevet på nytt i C.[13]

Yacc var i sin tur etterfølgeren til parsergeneratoren TMG (TransMoGrifier).[12] TMG ble skapt i 1964 og kjørte på OS/360, Multics og tidlige versjoner av UNIX.[12][14] Denne parsergeneratoren ble blant annet brukt til å utvikle EPL, som var en tidlig versjon av PL/I.[14] TMG genererte rekursivt descendant parsere som er et særtilfelle av ovenfra-ned-parsere.[12] Yacc på sin side genererte LALR-parsere.

Yacc var en del av den tidlige utviklingen av UNIX,[10] og ble en del av Unix versjon 3 som ble lansert i februar 1973.[15] En full beskrivelse av Yacc ble publisert i juli 1975.[10] Yacc blir noen ganger skrevet YACC (med store bokstaver), men opphavsmannen brukte navneformen Yacc (med små bokstaver), deriblant i beskrivelsen som er gitt i Version 7 Unix Manual i januar 1979.[11]

Et av de første bruksområder til Yacc var utviklingen av Portable C Compiler (pcc) på midten av 1970-tallet. Stephen C. Johnson var opphavsmannen til både Yacc og pcc.[16]

Yacc hadde stor betydning i utbredelsen av Unix, ved at det genererte parsere. Omkring 1990 kom programmet mer eller mindre ut av bruk, fordi andre parsergenerator med mindre restriktive lisenser og flere egenskaper hadde blitt tilgjengelige.

I 2002 gjorde Caldera International kildekoden til Yacc på gamle versjoner av Unix – fra UNIX versjon 7 til UNIX/32V, åpent tilgjengelig. På denne tiden hadde Yacc lenge vært erstattet av GNU Bison selv på Yacc’s egne Unix-varianter.

Prefikset ya- (Yet Another) levde sitt eget liv lenge etter at Yacc kom ut av bruk. Et av de mer kjente eksempler er Yahoo! (Yet Another Hierarchical Officious Oracle),[12] som er navnet på et IT-selskap som ble opprettet i California i 1994. Et annet eksempel er installerings- og konfigureringsverktøyet YaST (Yet another Setup Tool) på SUSE Linux.

yacchack[rediger | rediger kilde]

En av svakhetene ved Yacc var dens manglede evne til å produsere innadgående parsere. Dette ble første gang ordnet ved et sett med modifikasjoner, kalt yacchack, og publisert av Eric S. RaymondUSENET omkring 1983. Denne koden ble snart glemt da parsergeneratorene zoo og Berkeley Yacc ble tilgjengelige noen få år senere.

Berkeley Yacc[rediger | rediger kilde]

Utdypende artikkel: Berkeley Yacc

Berkeley Yacc ble skapt i 1985 av Robert Corbett ved University of California, Berkeley.[17] Parsergeneratoren ble opprinnelig kalt zoo, men den 2. september 1989 skiftet den navn til Berkeley Yacc (byacc).

Berkeley Yacc hadde tre fordeler over den opprinnelige Yacc: Den genererte raskere parsere, den kunne generere innadgående parsere, og kildekoden ble gjort til offentlig eiendom i stedet for å være under en proprietær lisens fra AT&T. Den forbedrede ytelsen oppstod ved å implementere teknikker som Franklin DeRemer og Thomas Penello hadde beskrevet i deres avhandling om LALR-parsere.[18]

Bruken av byacc spredte seg raskt på grunn av dens lisens som offentlig eiendom. Da GNU Bison ble tilgjengelig, gikk likevel byacc ut av offentlig bruk.

GNU Bison[rediger | rediger kilde]

Robert Corbett laget to nært beslektede LALR-parsergeneratorer i 1985, som begge benyttet teknikkene til DeRemer og Penello. Den ene var zoo, den andre var Byson. I 1987 begynte Richard Stallman å arbeide med Byson; navnet ble endret til Bison og grensesnittet ble kompatibelt med Yacc.

Den største forskjellen mellom Yacc og Byson/Bison på den tiden Byson første gangen ble lansert, var at Byson støttet konstruksjonen @n, og ga tilgang til det innledende og det avsluttende linjenummer og videre til antall tegn knyttet til alle symbolene i den gjeldende regel.

Der var også en kommando %expect n som sa at konflikter ikke skulle nevnes hvis der er n skift/reduser konflikter og ingen reduser/reduser konflikter. I nyere versjoner av Bison, kan %expect og varianten %expect-rr anvendes på individuelle regler med reduser-reduser konflikter.

Senere versjoner av Bison tilføyde mange flere nye egenskaper.

Feilrapporteringen på Bison ble forbedret på forskjellige måter. Av disse kan vi merke oss at Yacc og Byson manglet tegnet ^ i feilmeldinger.

Sammenlignet med Yacc benytter Bison en raskere men mindre plass-effektiv koding for parsertabellene.[17] og mer moderne teknikker for generering av mengden av lookahead.[18] Dette har vært standard siden første versjon. Det har vært påstått at disse forskjeller stammer fra den temporære løsning som Johnson måtte benytte for å få den opprinnelige Yacc til å passe på 16-biter minidatamaskinen PDP-11.

Navngitte referanser, semantiske predikater, %locations, %glr-parser, %printer, %destructor, dumping av avfall til DOT, %parse-param, %lex-param, og dumping av avfall til XSLT, LAC og generering av IELR(1)-parsere er nytt i Bison.

Bison har også mange egenskaper for å støtte C++ som ikke var nærværende i Yacc eller Byson.

Alle tidligere Yacc-varianter, og lignende parsergeneratorer som genererte C-kode, ble gjort foreldet av Bison i 1995.

PLY, goyacc og ocamlyacc[rediger | rediger kilde]

Yacc-konseptet har ofte blitt portert til andre programmeringsspråk. Noen av de tidligere porteringer er opphørt å eksistere sammen med språkene som ble brukt på dem; andre har blitt erstattet av parserskjeletter som leveres sammen med Bison.

Det finnes likevel uavhengige implementasjoner. Et av de best kjente er David Beazley’s PLY (Python Lex-Yacc) for Python. Et annet er goyacc, som støtter programmeringsspråket Go. Ocamlyacc blir lansert sammen med språket Objective Caml.

Operativsystemer[rediger | rediger kilde]

GNU Bison har blitt portert til blant annet følgende operativsystemer:

Programvare generert ved hjelp av GNU Bison[rediger | rediger kilde]

Eksempler på programmeringsspråk og annen programvare som er generert ved hjelp av GNU Bison:

Eksempelprogram: Kalkulator[rediger | rediger kilde]

Følgende eksempel viser hvordan GNU Bison og Flex kan brukes til å lage et enkelt kalkulatorprogram (kun addisjon og multiplikasjon) og et program for å skape et abstrakt syntakstre. De to neste filene sørger for definisjoner og implementasjon av syntakstreets funksjoner.

Expression.h[rediger | rediger kilde]

/*
 * Expression.h
 * Definisjon av strukturen brukt til å bygge syntakstreet. */
#ifndef __EXPRESSION_H__
#define __EXPRESSION_H__

/**
 * Operasjonstyper
 */
typedef enum tagEOperationType
{
    eVALUE,
    eMULTIPLY,
    ePLUS
} EOperationType;

/**
 * Uttrykks-struktur
 */
typedef struct tagSExpression
{
    EOperationType type;///< typen av operasjon

    int value;///< gyldig bare hvis typen er eVALUE
    struct tagSExpression *left; ///< venstre side av treet
    struct tagSExpression *right;///< høyre side av treet
} SExpression;

/**
 * Skapelse av en identifikator
 * Parameteren er tallverdien
 * Funksjonen returnerer uttrykket eller NULL hvis det ikke er nok minne
 */
SExpression *createNumber(int value);

/**
 * Skapelse av en operasjon
 * Parameteren "type" definerer operasjonstype
 * Parameteren "left" definerer venstre operand
 * Parameteren "right" definerer høyre operand
 * Funksjonen returnerer uttrykket eller NULL hvis det ikke er nok minne
 */
SExpression *createOperation(EOperationType type, SExpression *left, SExpression *right);

/**
 * Sletter et uttrykk
 * Parameteren b er uttrykket
 */
void deleteExpression(SExpression *b);

#endif // __EXPRESSION_H__

Expression.c[rediger | rediger kilde]

/*
 * Expression.c
 * Implementasjon av funksjoner til å bygge syntakstreet.
 */

#include "Expression.h"

#include <stdlib.h>

/**
 * Allokerer plass for uttrykket
 * Funksjonen returnerer uttrykket eller NULL hvis det ikke er nok minne
 */
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);
}

Lexer.l[rediger | rediger kilde]

Token som behøves av parseren vil bli generert av Flex.

%{
 
/*
 * Lexer.l filen
 * For å generere den leksikalske analysator kjøres "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
 
LPAREN      "("
RPAREN      ")"
PLUS        "+"
MULTIPLY    "*"
 
NUMBER      [0-9]+
WS          [ \r\n\t]*
 
%%
 
{WS}            { /* Fjern blanke tegn. */ }
{NUMBER}        { sscanf(yytext, "%d", &yylval->value); return TOKEN_NUMBER; }
 
{MULTIPLY}      { return TOKEN_MULTIPLY; }
{PLUS}          { return TOKEN_PLUS; }
{LPAREN}        { return TOKEN_LPAREN; }
{RPAREN}        { return TOKEN_RPAREN; }
.               {  }
 
%%
 
int yyerror(const char *msg) {
    fprintf(stderr,"Error:%s\n",msg); return 0;
}

Parser.y[rediger | rediger kilde]

Ettersom de ulike token er produsert av Flex må det være en kommunikasjon mellom parseren og den leksikalske analysatoren.[51] Datatypen som brukes til kommunikasjon, YYSTYPE, er satt til bruke Bisons %union deklarasjon.

Vi må også sørge for parametere til yylex-funksjonen, når den kalles fra yyparse.[51] Dette blir gjort gjennom Bison's %lex-param og %parse-param deklarasjoner.[52]

%{
 
/*
 * Parser.y file
 * For å generere parseren, kjør "bison Parser.y"
 */
 
#include "Expression.h"
#include "Parser.h"
#include "Lexer.h"

int yyerror(SExpression **expression, yyscan_t scanner, const char *msg) {
    // Feilhåndteringsrutiner
}
 
%}

%code requires {

#ifndef YY_TYPEDEF_YY_SCANNER_T
#define YY_TYPEDEF_YY_SCANNER_T
typedef void* yyscan_t;
#endif

}

%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;
}
 
%left '+' TOKEN_PLUS
%left '*' TOKEN_MULTIPLY
 
%token TOKEN_LPAREN
%token TOKEN_RPAREN
%token TOKEN_PLUS
%token TOKEN_MULTIPLY
%token <value> TOKEN_NUMBER

%type <expression> expr
 
%%
 
input
    : expr { *expression = $1; }
    ;
 
expr
    : expr[L] TOKEN_PLUS expr[R] { $$ = createOperation( ePLUS, $L, $R ); }
    | expr[L] TOKEN_MULTIPLY expr[R] { $$ = createOperation( eMULTIPLY, $L, $R ); }
    | TOKEN_LPAREN expr[E] TOKEN_RPAREN { $$ = $E; }
    | TOKEN_NUMBER { $$ = createNumber($1); }
    ;
 
%%

Main.c[rediger | rediger kilde]

Den følgende koden skaper syntakstreet ved å bruke parseren generert av Bison og den leksikalske analysator som er generert av Flex.

/*
 * 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)) {
        // couldn't 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 ePLUS:
            return evaluate(e->left) + evaluate(e->right);
        default:
            // shouldn't be here
            return 0;
    }
}
 
int main(void)
{
    SExpression *e = NULL;
    char test[]=" 4 + 2*10 + 3*( 5 + 1 )";
    int result = 0;
 
    e = getAST(test);
 
    result = evaluate(e);
 
    printf("Result of '%s' is %d\n", test, result);
 
    deleteExpression(e);
 
    return 0;
}

Makefile[rediger | rediger kilde]

Til slutt en makefil som bygger prosjektet.

# 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

Versjonshistorikk[rediger | rediger kilde]

Versjon Lansert Merknader
1.22 7. september 1993
1.23 1993[53]
1.24 30. mai 1995[54]
1.25 11. mai 1996
1.26 11. februar 1999
1.27 16. februar 1999
1.28 6. juli 1999
1.29 7. september 2001
1.30 29. oktober 2001
1.31 14. januar 2002
1.32 23. januar 2002
1.33 7. februar 2002
1.34 12. mars 2002
1.35 25. mars 2002
1.50 5. oktober 2002
1.75 14. oktober 2002
1.875 1. januar 2003
2.0 4. januar 2005
2.1 19. september 2005
2.2 19. mai 2006
2.3 5. juni 2006
2.4.0 2. november 2008
2.4.1 11. desember 2008
2.4.2 20. mars 2010
2.4.3 5. august 2010
2.5.0 14. mai 2012
2.5.1 5. juni 2012
2.6.0 19. juli 2012
2.6.1 30. juli 2012
2.6.2 3. august 2012
2.6.3 22. oktober 2012
2.6.4 23. oktober 2012
2.6.5 7. november 2012
2.7.0 12. desember 2012
2.7.1 15. april 2013
3.0.0 25. juli 2013
3.0.1 12. november 2013
3.0.2 5. desember 2013
3.0.3 15. januar 2015
3.0.4 23. januar 2015
3.0.5 28. mai 2018
3.1 27. august 2018
3.2 29. oktober 2018
3.2.1 9. november 2018
3.2.2 21. november 2018
3.2.3 18. desember 2018
3.2.4 24. desember 2018
3.3 26. januar 2019
3.3.1 27. januar 2019
3.3.2 3. februar 2019
3.4 19. mai 2019
3.4.1 22. mai 2019

Referanser[rediger | rediger kilde]

  1. ^ a b Bison Manual, GNU GENERAL PUBLIC LICENSE
  2. ^ Bison Manual, Introduction
  3. ^ Bison Manual, Conditions for Using Bison
  4. ^ Bison Manual, 10.1 C++ Parsers
  5. ^ Bison Manual, 10.2 Java Parsers
  6. ^ Levine 2009, side 50
  7. ^ Bison Manual, 1.5 Writing GLR Parsers
  8. ^ Brown 1995, Appendix D, side 277
  9. ^ Bison Manual, 9.1 Bison Options
  10. ^ a b c Johnson 1975
  11. ^ a b Unix 1979
  12. ^ a b c d e f Eric S. Raymond: Steve Johnson's reply, lists.gnu.org, 13. februar 2019
  13. ^ a b Ritchie, Dennis M. (april 1993). The Development of the C Language (PDF). Association for Computing Machinery, Inc. 
  14. ^ a b multicians.org - TMG, 2012-12-20
  15. ^ McIlroy, M. D. (1987). «A Research Unix reader: annotated excerpts from the Programmer's Manual, 1971–1986» (PDF). CSTR (139). 
  16. ^ Johnson, S.C. (1978). «A portable compiler: theory and practice». Proceedings of the 5th ACM SIGACT-SIGPLAN symposium on Principles of programming languages. Tucson, Arizona. s. 97–104. 
  17. ^ a b Corbett 1985
  18. ^ a b DeRemer 1982
  19. ^ a b c d e f Compilers available for free via Internet, old.la1k.no, 4. april 1995
  20. ^ Newbie - MVS 3.8j TSO programming information, h390-mvs.yahoogroups.narkive.com, besøkt 1. juli 2017
  21. ^ a b Open Source Software for z/OS and OS/390 UNIX, IBM, 2002
  22. ^ ISL Computing Software - SunOS, 5. mai 1999
  23. ^ OpenCSW: bison Solaris package, 2016
  24. ^ Georg Schwarz: gnu bison 2.2 on IRIX 5.3, lists.gnu.org, 21. mai 2006
  25. ^ a b NCO netCDF Operators, SourceForge.net, NCO on Tru64 UNIX, 1. desember 2003
  26. ^ BISON man page on QNX, Polarhome, 1999
  27. ^ Yacc is Not Dead, research.swtch.com 6. desember 2010
  28. ^ The SCO Group, Inc.: Release Notes GNU Utilities for OpenServer 6.0.0 6.0.0Da Arkivert 27. mars 2009 hos Wayback Machine., 2009
  29. ^ Caldera Skunkware Open Source Software Arkivert 16. mars 2016 hos Wayback Machine., 19. juli 2001
  30. ^ bison. GNU yacc replacement Arkivert 2015-11-29, hos Wayback Machine., Public Domain Software Library for AIX, 10. april 2006
  31. ^ HP-UX Porting and Archiving Centre: GNU Bison parser generator, besøkt 23. februar 2016
  32. ^ What's the deal with bison?, Apple Support Communities, 14. juli 2007
  33. ^ The FreeBSD Ports Archive bison. A parser generator from FSF, (mostly) compatible with Yacc Arkivert 4. juli 2017 hos Wayback Machine., 2007
  34. ^ OpenBSD/OCTEON, OSDN, 16. august 2010
  35. ^ bison-3.0.4nb3. GNU yacc(1) replacement, pkgsrc.se, 9. juli 2016
  36. ^ bison - GNU Project parser generator (yacc replacement), DragonFly On-Line Manual Pages, april 2013
  37. ^ Bison for Windows. Bison: Yacc-compatible parser generator. Version 2.4.1, gnuwin32.sourceforge.net, 4. mai 2009
  38. ^ Pat Shaughnessy: The Start of a Long Journey: How Ruby Parses and Compiles Your Code, 18. juni 2012
  39. ^ Mehdi Achour, Friedhelm Betz, Antony Dovgal, Nuno Lopes, Hannes Magnusson, Georg Richter, Damien Seguy, Jakub Vrana: Build Problems ¶, PHP Manual, 7. august 2016
  40. ^ Bison, libraries.io, 23. mai 2016
  41. ^ http://octave.org/doxygen/4.0/d5/d60/oct-parse_8cc_source.html
  42. ^ 4.3 Compiling GPC, The GNU Pascal Manual,
  43. ^ a b c d GCC 3.4
  44. ^ GCC 4.1
  45. ^ http://perldoc.perl.org/perl5100delta.html
  46. ^ Linux From Scratch: Version 4.0. Bison Official Download Location
  47. ^ LilyPond — Contributor’s Guide v2.19.36-1, 10.2 LilyPond programming languages
  48. ^ PostgreSQL 2015, kapittel 44.3
  49. ^ Levine 2009, kapittel 4
  50. ^ MariaDB Corporation Ab: Build Environment Setup for Linux. Required tools, 2016
  51. ^ a b GNU Bison Manual: C Scanners with Bison Parsers Arkivert 17. desember 2010 hos Wayback Machine.
  52. ^ GNU Bison Manual: Calling Conventions for Pure Parsers
  53. ^ Charles Donnelly, Richard Stallman: Bison. The YACC-compatible Parser Generator, 1993, Bison Version 1.23
  54. ^ Bison. The YACC-compatible Parser Generator, May 1995, Bison Version 1.24

Litteratur[rediger | rediger kilde]

Eksterne lenker[rediger | rediger kilde]