Verder Terug Inhoud

6. Hoe werken Lex en YACC intern

In het YACC bestand schrijf je je eigen main() functie, die op een gegeven moment yyparse() aanroept. De functie yyparse() is voor je aangemaakt door YACC, en komt in y.tab.c terecht.

yyparse() leest een stroom token/waarde paren van yylex(), welke beschikbaar gesteld moet worden. Je kunt deze functie zelf schrijven, of Lex dit laten doen. In onze voorbeelden hebben we dit aan Lex overgelaten.

De yylex() zoals geschreven door Lex leest karakters van een FILE * bestandspointer, yyin genaamd. Als je yyin niet instelt, is het de standard input. Hij voert uit naar yyout, als niet ingesteld is dat stdout. Je kunt yyin ook veranderen in de yywrap() functie die bij einde van een bestand wordt aangeroepen. Daarmee kun je een ander bestand openen, en verder parsen.

Als dat het geval is, moet hij 0 returnen. Als je na dit bestand wilt stoppen met parsen, moet hij 1 returnen.

Iedere aanroep van yylex() returnt een integer waarde die een token type voorstelt. Dit vertelt YACC wat voor token hij gelezen heeft. Optioneel mag het token een waarde hebben, die in de variabele yylval geplaatst moet worden.

Standaard is yylval van het type int, maar je kunt dit in het YACC bestand overriden door YYSTYPE te her#definen.

De Lexer moet toegang hebben tot yylval. Hiervoor moet deze gedeclareerd worden in de scope van de lexer als een externe variabele. De originele YACC doet dit niet voor je, dus moet je het volgende aan je lexer toevoegen, net onder de #include <y.tab.h>:

extern YYSTYPE yylval;

Bison, welke de meeste mensen tegenwoordig gebruiken, doet dit automatisch voor je.

6.1 Tokenwaarden

Zoals opgemerkt moet yylex() returnen wat voor soort token het is tegengekomen, en zijn waarde in yylval stoppen. Als deze tokens gedefinieerd zijn met het %token commando, worden er numerieke id's aan toegekend, beginnend bij 256.

Hierdoor is het mogelijk alle ascii karakters als token te gebruiken. Laten we zeggen dat je een rekenmachine aan het schrijven bent, tot nu toe zouden we de lexer als volgt hebben geschreven:

[0-9]+          yylval=atoi(yytext); return NUMMER;
[ \n]+          /* eet whitespace */;
-               return MINUS;
\*              return MULT; 
\+              return PLUS;
...

Onze YACC grammatica zou dan het volgende bevatten:

        exp:    NUMMER 
                |
                exp PLUS exp
                |
                exp MINUS exp
                |
                exp MULT exp

Dit is onnodig ingewikkeld. Door karakters te gebruiken als afkortingen voor numerieke token id's kunnen we onze lexer herschrijven:

[0-9]+          yylval=atoi(yytext); return NUMMER;
[ \n]+          /* eet whitespace */;
.               return (int) yytext[0];

De laatste punt matcht alle verder niet gematchte karakters.

De YACC grammatica wordt dan:

        exp:    NUMMER 
                |
                exp '+' exp
                |
                exp '-' exp
                |
                exp '*' exp

Dit is veel korter en ook duidelijker. Je hoeft de ascii tokens nu niet met %token in de header te declareren, ze werken zo uit de doos.

Een ander goed ding van deze constructie is dat Lex nu alles zal matchen dat we het geven - wat het standaard gedrag om niet gematchte invoer naar stdout te echo'en vermijdt. Als een gebruiker van deze rekenmachine een ^ gebruikt, geeft het nu een parse error, in plaats van op stdout ge-echoot te worden.

6.2 Recursie: `rechts is fout'

Recursie is een vitaal aspect van YACC. Zonder recursie kun je niet specificeren dat een bestand bestaat uit een reeks onafhankelijke commando's of statements. Van zichzelf is YACC alleen geïnteresseerd in de eerste regel, of de regel die je aanwijst als de startregel, met het `%start' symbool.

Recursie in YACC komt in twee smaken: rechts en links. Linker recursie, die je meestal moet gebruiken, ziet er zo uit:

commands: /* leeg */
        |
        commands command
Dit betekent: een commando is ofwel leeg, of het bestaat uit een of meer commando's, gevolgd door een commando. De manier waarop YACC werkt betekent dat je nu gemakkelijk individuele commando groepen kunt afhakken (aan de voorkant) en reduceren.

Vergelijk dit met rechter recursie, die er verwarrend genoeg voor velen beter uitziet:

commands: /* leeg */
        |
        command commands
Maar dit is kostbaar. Gebruikt als de %start regel, vereist het dat YACC alle commando's in je bestand op de stack houdt, wat een hoop geheugen kan gebruiken. Dus gebruik in ieder geval linker recursie voor het parsen van lange statements. Soms is het moeilijk rechter recursie te vermijden maar als je statements niet te lang zijn, hoef je je niet in bochten te wringen om linker recursie te gebruiken.

Als iets je commando's beëindigt (en dus scheidt), lijkt rechter recursie erg natuurlijk, maar is het nog steeds kostbaar:

commands: /* leeg */
        |
        command PUNTKOMMA commands

De juiste manier om dit te coderen is met linker recursie (ik heb het ook niet uitgevonden):

commands: /* leeg */
        |
        commands command PUNTKOMMA

Eerdere versies van deze HOWTO gebruikten abusievelijk rechter recursie. Met dank aan Markus Triska.

6.3 yylval voor gevorderden: %union

Momenteel moeten we *het* type van yylval definiëren. Dit is echter niet altijd toepasselijk. Er zijn tijden dat we meerdere datatypen moeten kunnen verwerken. Terugkerend naar onze hypothetische thermostaat, willen we misschien een verwarming die we willen beheersen uitkiezen, als volgt:

Verwarming hoofdgebouw
        `hoofdgebouw' verwarming geselecteerd
doel temperatuur 23
        `hoofdgebouw' verwarming doel temperatuur nu 23

Hiervoor moet yylval een union wezen, die zowel strings als integers kan bevatten - maar niet tegelijk.

Bedenk dat we YACC eerder verteld hebben welk type yylval was door YYSTYPE te definiëren. We zouden YYSTYPE op deze manier als union kunnen definiëren, maar YACC heeft hier een gemakkelijker methode voor: het %union statement.

Gebaseerd op Voorbeeld 4, schrijven we nu de YACC grammatica van Voorbeeld 7. Eerst de intro:

%token TOKVERWARMING TOKWARMTE TOKDOEL TOKTEMPERATUUR

%union 
{
        int number;
        char *string;
}

%token <number> TOESTAND
%token <number> NUMMER
%token <string> WOORD

We definiëren onze union, die alleen een nummer en een string bevat. Dan leggen we YACC met een uitgebreide %token syntax uit welk deel van de union ieder token moet benaderen.

In dit geval laten we het TOESTAND token een integer gebruiken, net als zonet. Hetzelfde geldt voor het NUMMER token, dat we gebruiken om temperaturen te lezen.

Nieuw is het WOORD token, dat gedeclareerd is om een string te gebruiken.

Het lexerbestand verandert ook een beetje:

%{
#include <stdio.h>
#include <string.h>
#include "y.tab.h"
%}
%%
[0-9]+                  yylval.number=atoi(yytext); return NUMMER;
verwarming              return TOKVERWARMING;
warmte                  return TOKWARMTE;
aan|uit                 yylval.number=!strcmp(yytext,"aan"); return TOESTAND;
doel                    return TOKDOEL;
temperatuur             return TOKTEMPERATUUR;
[a-z0-9]+               yylval.string=strdup(yytext);return WOORD;
\n                      /* negeer einde regel */;
[ \t]+                  /* negeer whitespace  */;
%%

Zoals je ziet benaderen we de yylval niet meer direct, we voegen een suffix toe om aan te geven welk deel we willen benaderen. In de YACC grammatica hoeft dat echter niet, want YACC doet het voor ons:

heater_select:
        TOKVERWARMING WOORD
        {
                printf("\tVerwarming '%s' geselecteerd\n",$2);
                heater=$2;
        }
        ;

Vanwege de %token declaratie hierboven kiest YACC automatisch het `string' lid uit onze union. Merk ook op dat we een kopie van $2 opslaan, die later gebruikt wordt om de gebruiker te vertellen naar welke verwarming hij commando's stuurt:

target_set:
        TOKDOEL TOKTEMPERATUUR NUMMER
        {
                printf("\tTemperatuur van verwarming '%s' ingesteld op %d\n",heater,$3);
        }
        ;
Lees voor meer details example7.y.
Verder Terug Inhoud