Vorlesung

Parser-Generator bison

$$Id: taschenrechner.tex,v 1.1 2003/12/17 12:34:10 joe Exp $$

typischen Kombination:

• lexikalische Analyse (Scanner) mit lex (flex)
• syntaktische Analyse (Parser) mit yacc (bison)

parser.y enthält erweiterte Grammatik (Regeln mit semantischen Aktionen).

bison -d erzeugt daraus:

• parser.tab.c (Parser)
• parser.tab.h (Token-Definitionen, für scanner.l)

Beispiel: http://www.imn.htwk-leipzig.de/~waldmann/ws03/compilerbau/programme/taschenrechner/

Flex-Bison-Beispiel

parser.y:

%token NUM
%left '-' '+'
%%
input : | input line ;
line  : exp '\n' 
  { printf ("%d\n", $1); }
exp   : NUM  { $$ = $1; }
   | exp '+' exp   
       { $$ = $1 + $3; }
   | exp '-' exp   
       { $$ = $1 - $3; }
   ;
%%

scanner.l:

%{
#include "parser.tab.h"
%}
%%
[0-9]+ { 
  yylval = atoi (yytext); 
  return NUM; }
[-+*/^()] { 
  return yytext[0]; }

interpreter.c:

int main (int argc, char ** argv) { yyparse (); }

Yacc-Grammatiken

$$Id: bison.tex,v 1.1 2003/12/17 12:34:10 joe Exp $$

Definitionen %% Regeln %% Hilfs-Funktionen

Definitionen: Namen von Token (auch Präzedenz, Assoziativität)

Regeln: Variable : (Variable)$^*$ Aktion | ...;

zu jeder Variablen gibt es semantischen Wert,

Bezeichnung $$ (links), $1, $2, .. (rechts).

Fehlerbehandlung

Fehler: keine action$(s_m, a_i)$ anwendbar.

Ausgabe:

%%
int yyerror (char * s) {
        fprintf (stderr, "%s\n", s);
        return 0;
}

Reparatur: Regeln mit eingebautem Token error

 stmnts:  /* empty string */
             | stmnts '\n'
             | stmnts exp '\n'
             | stmnts error '\n'

Symbole und -Tabellen

$$Id: symbol.tex,v 1.2 2003/12/17 12:34:10 joe Exp $$

typedef double (*func_t) (double);
typedef struct {
  char *name;  /* name of symbol */
  int type;    /* type: either VAR or FNCT */
  union
  { double var;       /* value of a VAR   */
    func_t fnctptr;   /* value of a FNCT  */
  } value;
  struct symrec *next;    /* link field */
} symrec;
extern symrec * sym_table;

Scanner muß neue Symbole eintragen und alte wiederfinden (getsym/putsym).

Bessere Implementierung durch Hashing.

Unions in semantischen Werten

$$Id: union.tex,v 1.1 2003/12/17 12:34:10 joe Exp $$

%union {
double     val;  /* Zahlen */
symrec  *tptr;   /* Symboltabellen-Eintrag */
}
%token <val>  NUM 
%token <tptr> VAR FNCT
%type  <val>  exp
%%
exp: NUM         { $$ = $1; }
 | VAR         { $$ = $1->value.var; }
 | VAR '=' exp { $$ = $3; $1->value.var = $3;}
 | FNCT '(' exp ')' 
        { $$ = (*($1->value.fnctptr))($3); }
 | exp '+' exp { $$ = $1 + $3; }