Verder Terug Inhoud

4. YACC

YACC kan invoerstromen parsen die bestaan uit tokens met bepaalde waarden. Dit geeft precies weer hoe YACC zich verhoudt tot LEX, YACC weet niet wat `invoerstromen' zijn, het heeft voorbewerkte tokens nodig. Je kunt je eigen tokenizeerder schrijven, maar we laten dit aan Lex over.

Een opmerking over grammatica's en parsers. Toen YACC het levenslicht zag, werd het gebruikt om invoerbestanden voor compilers te parsen: programma's. Programma's in een computertaal zijn in het algemeen *niet* dubbelzinnig - ze hebben maar een betekenis. YACC kan dus niet met dubbelzinnigheid omgaan en zal klagen over shift/reduce en reduce/reduce conflicten. Meer over dubbelzinnigheid en YACC "problemen" in het hoofdstuk `Conflicten'.

4.1 Een eenvoudige thermostaat beheerser

Laten we zeggen dat we een thermostaat willen beheersen met een eenvoudige taal. Een sessie met de thermostaat kan er als volgt uit zien:

warmte aan
        Verwarming aan!
warmte uit
        Verwarming uit!

De tokens die we moeten herkennen zijn: warmte, aan/uit (TOESTAND), doel, temperatuur, NUMMER

De Lex tokenizeerder (Voorbeeld 4) is:

%{
#include <stdio.h>
#include "y.tab.h"
%}
%%
[0-9]+                  return NUMMER;
warmte                  return TOKWARMTE;
aan|uit                 return TOESTAND;
doel                    return TOKDOEL;
temperatuur             return TOKTEMPERATUUR;
\n                      /* negeer einde regel */;
[ \t]+                  /* negeer whitespace */;
%%

We merken twee belangrijke veranderingen op. Ten eerste includen we het bestand `y.tab.h' en ten tweede printen we niet meer, we returnen namen van tokens. Deze verandering is omdat we het nu allemaal aan YACC toevoeren, die is niet geïnteresseerd in wat we op het scherm uitvoeren. Y.tab.h heeft definities voor deze tokens.

Maar waar komt y.tab.h vandaan? Het wordt gegenereerd door YACC vanuit het Grammatica Bestand dat we gaan creëren. Onze taal is eenvoudig dus de grammatica ook:

commands: /* leeg */
        | commands command
        ;

command:
        heat_switch
        |
        target_set
        ;

heat_switch:
        TOKWARMTE TOESTAND
        {
                printf("\tWarmte aan- of uitgezet\n");
        }
        ;

target_set:
        TOKDOEL TOKTEMPERATUUR NUMMER
        {
                printf("\tTemperatuur ingesteld\n");
        }
        ;

Het eerste gedeelte is wat ik de `wortel' zal noemen. Het vertelt ons dat we `commands' hebben, en dat deze commands bestaan uit individuele `command' delen. Je ziet dat deze regel erg recursief is, want hij bevat weer het woord `commands'. Dit betekent dat het programma nu een reeks commands een voor een kan reduceren. Zie het hoofdstuk `Hoe werken Lex en YACC intern' voor belangrijke details over recursie.

De tweede regel definieert wat een command is. We ondersteunen maar twee soorten commands, de `heat_switch' en de `target_set'. Dat is de betekenis van het |-symbool - `een command bestaat uit ofwel een heat_switch of een target_set'.

Een heat_switch bestaat uit het HEAT token, wat simpelweg het woord `warmte' is gevolgd door een toestand (die we in het Lex bestand gedefinieerd hebben als `aan' of `uit').

Iets ingewikkelder is de target_set, die bestaat uit het TARGET token (het woord `doel'), het TEMPERATURE token (het woord `temperatuur') en een getal.

Een volledig YACC bestand

De vorige paragraaf toonde alleen het grammatica gedeelte van het YACC bestand, maar er is meer. Dit is de header die we hebben weggelaten:

%{
#include <stdio.h>
#include <string.h>
 
void yyerror(const char *str)
{
        fprintf(stderr,"fout: %s\n",str);
}
 
int yywrap()
{
        return 1;
} 
  
main()
{
        yyparse();
} 

%}

%token NUMMER TOKWARMTE TOESTAND TOKDOEL TOKTEMPERATUUR
(Noot van de vertaler: tussen header en grammatica moet nog een %% staan.) De functie yyerror() wordt door YACC aangeroepen als hij een fout tegenkomt. We voeren gewoon de doorgestuurde boodschap uit, maar er zijn slimmere dingen te doen. Zie de paragraaf `Verder lezen' aan het einde.

De functie yywrap() kan gebruikt worden om verder te lezen uit een ander bestand. Het wordt bij EOF aangeroepen en dan kun je een ander bestand openen, en 0 returnen. Of je kunt 1 returnen, om aan te geven dat dit echt het einde is. Zie verder het hoofdstuk `Hoe Lex en YACC intern werken'.

Dan is er nog de functie main(), die niets doet behalve alles in gang zetten.

De laatste regel definieert eenvoudig de tokens die we gaan gebruiken. Die worden uitgevoerd met y.tab.h als YACC is aangeroepen met de `-d' optie.

De thermostaat beheerser compileren & draaien

lex example4.l
yacc -d example4.y
cc lex.yy.c y.tab.c -o example4 
Sommige dingen zijn veranderd. We roepen nu ook YACC aan om onze grammatica te compileren, wat y.tab.c en y.tab.h genereert. Dan roepen we als gewoonlijk Lex aan. Bij het compileren laten we de -ll vlag weg; we hebben nu onze eigen main() en hebben die van libl niet nodig.

OPMERKING: als je een foutmelding krijgt dat je compiler `yylval' niet kan vinden, voeg dan onder #include <y.tab.h> dit toe:
extern YYSSTYOE yylval;
Dit wordt uitgelegd in de paragraaf `Hoe Lex en YACC intern werken'.

Een voorbeeldsessie:

$ ./example4 
warmte aan
        Warmte aan- of uitgezet
warmte uit
        Warmte aan- of uitgezet
doel temperatuur 10
        Temperatuur ingesteld
doel vochtigheid 20
fout: parse error
$

Dit is niet helemaal wat we wilden bereiken, maar om de leercurve behapbaar te houden kunnen we niet alles tegelijk presenteren.

4.2 De thermostaat uitbreiden om parameters te verwerken

Zoals we hebben gezien kunnen we de thermostaat commands nu correct parsen, en zelfs fouten correct opmerken. Maar als je misschien hebt geraden door de dubbelzinnige bewoordingen, heeft het programma geen idee wat het zou moeten doen, de waarden die je invoert worden er niet naar doorgestuurd.

Laten we beginnen met het vermogen om de nieuwe doeltemperatuur te lezen. Hiervoor moeten we de NUMMER match in de Lexer leren zichzelf in een integer waarde om te zetten, die dan ingelezen kan worden in YACC.

Als Lex een doel matcht, stopt het de tekst van de match in de string `yytext'. YACC op zijn beurt verwacht een waarde in `yylval'. In voorbeeld 5 zien we de voor de hand liggende oplossing:

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

Zoals je ziet draaien we atoi() op yytext, en stoppen we de uitkomst in yylval, waar YACC het kan vinden. Net zoiets voor de TOESTAND match, waarbij we yylval op 1 zetten als deze `aan' is. Merk op dat een aparte `aan' en `uit' match in Lex een sneller programma zou genereren, maar ik wilde voor de verandering een ingewikkelder regel en actie laten zien.

Nu moeten we YACC leren hoe hiermee om te gaan. Wat in Lex `yylval' genoemd wordt, heeft in YACC een andere naam. Laten we de regel die het nieuwe temperatuurdoel instelt bekijken:

target_set: 
        TOKDOEL TOKTEMPERATUUR NUMMER
        {
                printf("\tTemperatuur ingesteld op %d\n",$3);
        }
        ;

Om toegang te krijgen tot het derde gedeelte van de regel (NUMMER), moeten we $3 gebruiken. Steeds als yylex() returnt, wordt de waarde van yylval aan de terminal (vertaler: token) toegekend, en kan benaderd worden met de $-constructie.

Om hier verder op in te gaan, beschouw de nieuwe `heat_switch' regel:

heat_switch:
        TOKWARMTE TOESTAND
        {
                if($2)
                        printf("\tWarmte aan\n");
                else
                        printf("\tWarmte uit\n");
        }
        ;

Als je nu example5 draait, voert het netjes uit wat je hebt ingevoerd.

4.3 Een configuratiebestand parsen

Laten we een deel van het eerder genoemde configuratiebestand herhalen:

zone "." {
        type hint;
        file "/etc/bind/db.root";
};

We hebben al een Lexer voor dit bestand. Nu hoeven we alleen nog maar een YACC grammatica te schrijven, en de Lexer aanpassen zodat het waarden teruggeeft in een vorm die YACC kan snappen.

In de lexer van Voorbeeld 6 zien we:

%{
#include <stdio.h>
#include "y.tab.h"
%}

%%

zone                    return ZONETOK;
file                    return FILETOK;
[a-zA-Z][a-zA-Z0-9]*    yylval=strdup(yytext); return WOORD;
[a-zA-Z0-9\/.-]+        yylval=strdup(yytext); return BESTANDSNAAM;
\"                      return QUOTE;
\{                      return OBRACE;
\}                      return EBRACE;
;                       return PUNTKOMMA;
\n                      /* negeer einde regel*/;
[ \t]+                  /* negeer whitespace */;
%%

Als je goed kijkt, zie je dat yylval veranderd is! We verwachten niet meer dat het een integer is, maar nemen aan dat het een char * is. Voor de eenvoud roepen we strdup aan en verspillen een hoop geheugen. Merk op dat dit geen probleem is in veel gevallen als je een bestand maar een keer hoeft te parsen, en dan exit.

We willen strings opslaan omdat we nu voornamelijk met namen te maken hebben: bestandsnamen en zonenamen. In een later hoofdstuk zullen we uitleggen hoe je met verschillende soorten data omgaat.

Om YACC over het nieuwe type van yylval te vertellen, voegen we dit toe aan de header van onze YACC grammatica:

#define YYSTYPE char *

De grammatica zelf is weer ingewikkelder. We hakken het in stukjes om het verteerbaarder te maken.

commands:
        |        
        commands command PUNTKOMMA
        ;


command:
        zone_set 
        ;

zone_set:
        ZONETOK quotedname zonecontent
        {
                printf("Complete zone for '%s' gevonden\n",$2);
        }
        ;

Dit is de intro, inclusief voornoemde recursieve `wortel' Merk op dat we specificeren dat commands worden getermineerd (en gescheiden) door ;'s. We definiëren één soort command, de `zone_set'. Deze bestaat uit het ZONE token (het woord `zone'), gevolgd door een quotedname en de `zonecontent'. De zonecontent begint eenvoudig:

zonecontent:
        OBRACE zonestatements EBRACE 

Hij moet beginnen met een OBRACE, een {. Dan komen de zonestatements, gevolgd door een EBRACE, een }.

quotedname:
        QUOTE BESTANDSNAAM QUOTE
        {
                $$=$2;
        }

Deze sectie definieert een `quotedname': een BESTANDSNAAM tussen QUOTES. Dan iets bijzonders: de waarde van een quotedname token is de waarde van de BESTANDSNAAM. Dit betekent dat de quotedname als waarde de bestandsnaam zonder quotes heeft.

Dat is wat het magische `$$=$2' doet. Het zegt: mijn waarde is de waarde van mijn tweede deel. Als nu naar de quotedname verwezen wordt in andere regels, en je benadert zijn waarde met de $-constructie, zie je de waarde die we hier ingesteld hebben met $$=$2.

OPMERKING: deze grammatica verslikt zich in bestandsnamen zonder een `.' of een `/' erin.

zonestatements:
        |
        zonestatements zonestatement PUNTKOMMA
        ;

zonestatement:
        statements
        |
        FILETOK quotedname 
        {
                printf("Een zonefile naam '%s' tegengekomen\n", $2);
        }
        ;

Dit is een algemeen statement die alle soorten statements binnen het `zone' blok afvangt. We zien opnieuw de recursiviteit.

block: 
        OBRACE zonestatements EBRACE PUNTKOMMA
        ;

statements:
        | statements statement
        ;

statement: WOORD | block | quotedname

Dit definieert een blok, en `statements' die er in gevonden kunnen worden.

Bij uitvoering ziet de uitvoer er zo uit:

$ ./example6
zone "." {
        type hint;
        file "/etc/bind/db.root";
        type hint;
};
Een zonefile naam '/etc/bind/db.root' tegengekomen
Complete zone for '.' gevonden

Verder Terug Inhoud