4. Flex a bison: propojení

V závěrečné kapitole zodpovím otázky, které jistě vyvstaly v hlavě pozorných čtenářů. Proč vrací int funkce yylex ()? Odkud bere parser tokeny a jejich hodnoty? Jak v programu propojím scanner vygenerovaný flexem s parserem, který jsem obdržel od programu bison?

Parser předpokládá, že existuje funkce int yylex (), která postupně vrací čísla tokenů a pokud je s tokenem asociována i hodnota, nastaví ji do proměnné yylval, která je typu YYSTYPE. Akce vašich pravidel pro scanner tedy nastaví tuto proměnnou a vrátí hodnotu rozpoznaného tokenu. V praxi bude spolupráce přibližně následující:

my-language.l - fragmenty
%{
%include <my-language.tab.h>
%}

DIGIT   [0-9]

%%

\/\/.*\n        /* ignoruj c++ komentáře */
[ \t]+          /* ignoruj mezery */

if              return IF;
then            return THEN;
else            return ELSE;

{DIGIT}+        {
                  yylval.ivalue = strtol (yytext,NULL, 10); 
                  return NUMBER;
                }

              /* jednoznakové tokeny - například '+' */
.               return (int) *yytext;  
my-language.y - fragmenty
%union {
  int            ivalue;
  char          *svalue;
}

%token IF THEN ELSE
%token <ivalue> NUMBER

%type <ivalue> expr

%%

statement:
            IF '(' expr ')' 
            THEN 
              statement 
            ELSE 
              statement 
            { akce (); }
;

expr:
          NUMBER
        | expr '+' expr  { $$ = $1 + $3; }
;

Scanner vygenerovaný flexem vrací postupně jednotlivé tokeny (a v případě čísel též jejich hodnotu). Soubor my-language.tab.h vygeneruje bison, pokud jej spustíme s parametrem -d. Obsahuje definice jednotlivých tokenů - v případě my-language.y to se jedná o definice tokenů IF, THEN a ELSE.

5. Oblíbený příklad: jednoduchá kalkulačka

Následuje slíbený příklad použití nástrojů flex a bison - jednoduchá kalkulačka. Mimo technik popsaných v tomto referátu demonstruje též použití postupů, které již šly nad jeho rámec - funkce, pomocí kterých se parser může vzpamatovat z chyb ve vstupu (vstupní soubor neodpovídá gramatice jazyka - například (1+*)3 není platný matematický výraz).

0rfelyus@hobitin:~ $ flex -ocalc.yy.c calc.l
0rfelyus@hobitin:~ $ bison -d calc.y
0rfelyus@hobitin:~ $ gcc calc.yy.c calc.tab.c -o calc -lfl
0rfelyus@hobitin:~ $ ./calc
2 + 3 * (10 - 3)
        23
(1 + 4 - )
parse error
(1 - (4)  * 3) / (3 * (1+2))
        -1
calc.l
%{
#include <stdlib.h>
#include "calc.tab.h"
%}

DIGIT  [0-9]

%%
{DIGIT}+       {
                 yylval = strtol(yytext, NULL, 10); 
                 return NUM;
               }

" "+		/* ignored */
\t+		/* ignored */

\n             return '\n';
.              return (int) (yytext[0]);

%%
calc.y
%{
int yylex(void);
int yyerror(char *);
%}

%token          NUM
%left           '+' '-'
%left           '*' '/'

%%

input:          /* empty */
        | lines
;

lines:  line            
        | lines line
;

line:   '\n'    
        | expr '\n'     { printf("\t%d\n", $1); }
        | error '\n'    { yyerrok; }
;

expr:     NUM           { $$ = $1; }
        | expr '+' expr { $$ = $1 + $3; }
        | expr '-' expr { $$ = $1 - $3; }
        | expr '*' expr { $$ = $1 * $3; }
        | expr '/' expr { $$ = $1 / $3; }
        | '(' expr ')'  { $$ = $2; }
;

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

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

6. Závěr

Tento referát jsem zamýšlel pouze jako inspiraci a letmé seznámení se základními myšlenkami nástrojů pro lexikální a syntaktickou analýzu. Přestože je velmi vzdálen kompletnímu a podrobnému manuálu, doufám, že jste dočetli až na toto místo, během četby jste se nenudili a brzy ve svých programech využijete nově nabyté poznatky .

[Obsah] [Předchozí kapitola: Bison]


© 1999 0rfelyus Emacs