Redigerer GNU Bison (avsnitt)

==Eksempelprogram: Kalkulator==
Følgende eksempel viser hvordan GNU Bison og Flex kan brukes til å lage et enkelt [[kalkulator]]program (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===
<syntaxhighlight lang="c">
/*
 * 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__
</syntaxhighlight>

===Expression.c===
<syntaxhighlight lang="c">
/*
 * 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);
}
</syntaxhighlight>

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

<syntaxhighlight lang="c">
%{
 
/*
 * 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;
}
</syntaxhighlight>

===Parser.y===
Ettersom de ulike token er produsert av Flex må det være en kommunikasjon mellom parseren og [[leksikalsk analyse|den leksikalske analysatoren]].<ref name="flex-bison-bridge">[http://flex.sourceforge.net/manual/Bison-Bridge.html GNU Bison Manual: C Scanners with Bison Parsers]  {{Wayback|url=http://flex.sourceforge.net/manual/Bison-Bridge.html |date=20101217042916 }}</ref> [[Datatype]]n 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''.<ref name="flex-bison-bridge" /> Dette blir gjort gjennom Bison's ''%lex-param'' og ''%parse-param'' deklarasjoner.<ref name="pure-calling-conventions">[https://www.gnu.org/software/bison/manual/html_node/Pure-Calling.html GNU Bison Manual: Calling Conventions for Pure Parsers]</ref>

<syntaxhighlight lang="c">
%{
 
/*
 * 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); }
    ;
 
%%
</syntaxhighlight>

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

<syntaxhighlight lang="c">
/*
 * 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;
}
</syntaxhighlight>

===Makefil===
Til slutt en [[makefil]] som bygger prosjektet.

<syntaxhighlight lang="make">
# 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
</syntaxhighlight>