Lex en YACC inleiding/HOWTO
v0.8 $Date: 2003/07/07 18:37:39 $Dit document dient om je op weg te helpen met het gebruik van Lex en YACC
InleidingWelkom beste lezer.Als je enige tijd in een Unix omgeving hebt geprogrammeerd, ben je
vast de mystieke programma's Lex & YACC, of Flex & Bison,
zoals ze wereldwijd genoemd worden door GNU/Linux gebruikers,
tegengekomen, Flex zijnde een implementatie van Lex door Vern Paxon en
Bison zijnde de GNU versie van YACC. We zullen deze programma's verder
Lex en YACC noemen - de nieuwere versies zijn opwaarts compatible, dus
je kunt Flex en Bison gebruiken bij het proberen van onze programma's.Deze programma's zijn waanzinnig nuttig, maar net als bij je C
compiler legt de manpage de taal die ze verstaan niet uit, noch hoe ze
te gebruiken. YACC is echt fantastisch wanneer gebruikt met Lex,
echter, de Bison manpage beschrijft niet hoe je door Lex gegenereerde
code integreert met je Bison programma.
Wat dit document NIET isEr zijn geweldige boeken over Lex & YACC. Lees in ieder geval deze
boeken als je meer wilt weten. Ze geven veel meer informatie dan wij
ooit kunnen. Zie de sectie "Lees Verder" aan het eind. Dit document is
bedoeld om je op weg te helpen bij het gebruik van Lex & YACC, om
je in staat te stellen je eerste programma's te maken.De documentatie die bij Flex en Bison hoort is ook uitstekend, maar
geen leerboek. Maar ze vormen een aardige aanvulling op mijn HOWTO. Zie
de verwijzingen aan het einde.Ik ben zeker geen YACC/Lex expert. Toen ik begon dit document te
schrijven, had ik precies twee dagen ervaring. Mijn enige doel is die
twee dagen makkelijker voor je te maken.Verwacht niet de juiste YACC en Lex stijl in deze HOWTO aan te
treffen. Voorbeelden zijn uiterst eenvoudig gehouden en er zijn
misschien betere manieren om ze te schrijven. Als je weet hoe, laat
het me dan weten. Wat Lex & YACC voor je kunnen doenBij juist gebruik maken deze programma's het mogelijk met gemak
complexe talen te scannen. Dit is een groot voordeel als je een
configuratiebestand wilt lezen, of een compiler wilt schrijven voor
welke taal dan ook die je (of iemand anders) misschien hebt
uitgevonden.Met een beetje hulp, die dit document hopelijk biedt, zul je nooit
meer met de hand een parser hoeven te schrijven - Lex & YACC zijn
de gereedschappen om dit te doen.
Wat ieder programma op zichzelf doetHoewel deze programma's uitblinken wanneer ze samen gebruikt worden,
hebben ze ieder een eigen doel. Het volgende hoofdstuk legt uit wat
ieder onderdeel doet. LexHet programma Lex genereert een zogenaamde `Lexer'. Dit is een functie
die een stroom karakters als input neemt, en steeds als het een groep
karakters ziet die met een sleutelwaarde overeenkomen, een bepaalde
actie onderneemt. Een heel eenvoudig voorbeeld:%{
#include <stdio.h>
%}
%%
stop printf("Stop commando ontvangen\n");
start printf("Start commando ontvangen\n");
%%
De eerste sectie, tussen de %{ en %} wordt direct overgenomen in het
gegenereerde programma. Dit is nodig omdat we later printf gebruiken,
wat gedefinieerd is in stdio.h.Secties worden gescheiden door `%%', dus de eerste regel van de tweede
sectie start met de `stop' sleutel. Iedere keer dat de `stop' sleutel
tegengekomen wordt in de input, wordt de rest van de regel (een
print() call) uitgevoerd.Behalve `stop' hebben we ook een `start' gedefinieerd, die verder
grotendeels hetzelfde doet.We beëindigen de code weer met `%%'.Doe dit om Voorbeeld 1 te compileren:
lex example1.l
cc lex.yy.c -o example1 -ll
OPMERKING:Als je flex gebruikt ipv lex, moet je misschien `-ll'
vervangen door `-lfl' in de compilatiescripts. Redhat 6.x en SuSE
vereisen dit, zelfs als je `flex' aanroept als `lex'!Dit genereert het programma `example1'. Als je het draait, wacht het
tot je iets intikt. Als je iets typt dat niet overeenkomt met een
gedefinieerde sleutel (`stop' en `start') wordt het weer geoutput. Als
je `stop' intikt geeft het `stop commando ontvangen';Sluit af met een EOF (ˆD).Je vraagt je misschien af hoe het programma draait, daar we geen
main() gedefinieerd hebben. Die functie is voor je gedefinieerd in
libl (liblex) die we ingecompileerd hebben met het -ll commando.
Reguliere expressies in matchesDit voorbeeld was op zichzelf niet erg nuttig, en dat is het volgende
ook niet. Het laat echter wel zien hoe je reguliere expressies
gebruikt in Lex, wat later superhandig zal zijn.Voorbeeld 2:
%{
#include <stdio.h>
%}
%%
[0123456789]+ printf("NUMMER\n");
[a-zA-Z][a-zA-Z0-9]* printf("WOORD\n");
%%
Dit Lex bestand beschrijft twee soorten matches (tokens): WOORDen en
NUMMERs. Reguliere expressies kunnen behoorlijk intimiderend zijn maar
met een beetje werk zijn ze makkelijk te begrijpen. Laten we de NUMMER
match bekijken:[0123456789]+Dit betekent: een reeks van een of meer karakters uit de groep
0123456789. We hadden het ook kunnen afkorten tot:[0-9]+De WOORD match is iets ingewikkelder:[a-zA-Z][a-zA-Z0-9]*Het eerste deel matcht 1 en slechts 1 karakter tussen `a' en `z', of
tussen `A' en `Z'. Met andere woorden, een letter. Deze beginletter
moet gevolgd worden door nul of meer karakters die ofwel een letter of
een cijfer zijn. Waarom hier een asterisk gebruiken? De `+' betekent 1
of meer matches, maar een WOORD kan heel goed uit slechts 1 karakter
bestaan, dat we al gematcht hebben. Dus het tweede deel heeft
misschien nul matches, dus schrijven we een `*'.Op deze manier hebben we het gedrag van veel programmeertalen
geïmiteerd die vereisen dat een variabelenaam met een letter
*moet* beginnen maar daarna cijfers mag bevatten. Met andere woorden,
`temperature1' is een geldige naam, maar `1temperature' niet.Probeer voorbeeld 2 te compileren, net zoals voorbeeld 1, en voer wat
tekst in. Een voorbeeldsessie:<tscreen><verb>
$ ./example2
foo
WOORD
bar
WOORD
123
NUMMER
bar123
WOORD
123bar
NUMMER
WOORDJe vraagt je misschien ook af waar al die witregels in de uitvoer
vandaan komen. De reden is eenvoudig: het was in de invoer, en het
wordt nergens gematcht, dus wordt het weer uitgevoerd.De Flex manpage beschrijft de reguliere expressies in detail. Velen
vinden de perl reguliere expressies manpage (perlre) ook nuttig, al
kan Flex niet alles dat perl kan.Zorg dat je geen matches met een lengte van nul zoals `[0-9]*' maakt -
je lexer kan in de war raken en lege strings herhaaldelijk matchen. YACCYACC 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'.
Een eenvoudige thermostaat beheerserLaten 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, NUMMERDe 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 bestandDe 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 & draaienlex 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. Een Parser in C++ makenHoewel Lex en YACC ouder zijn dan C++, is het mogelijk een C++ parser te
maken. Flex heeft een optie om een C++ lexer te genereren, maar die zullen
we niet gebruiken, want YACC kan er direct mee omgaan.Ik geef er de voorkeur aan Lex een gewoon C bestand te laten genereren, en
YACC C++ code te laten genereren. Als je dan je toepassing linkt, kom je
misschien problemen tegen omdat de C++ code standaard geen C functies kan
vinden, tenzij je het verteld hebt dat de functies extern "C" zijn.Maak hiervoor een C header in YACC:extern "C"
{
int yyparse(void);
int yylex(void);
int yywrap()
{
return 1;
}
}Als je yydebug wilt declareren of veranderen, moet dat nu zo:extern int yydebug;
main()
{
yydebug=1;
yyparse();
}Dit is vanwege de Een Definitie Regel van C++, die geen meervoudige
definities van yydebug toestaat.Je zult misschien ook de #define van YYSTYPE in je Lex bestand moeten
herhalen, vanwege C++ z'n strengere type checking.Compileren gaat ongeveer zo:
lex bindconfig2.l
yacc --verbose --debug -d bindconfig2.y -o bindconfig2.cc
cc -c lex.yy.c -o lex.yy.o
c++ lex.yy.o bindconfig2.cc -o bindconfig2 Vanwege het -o statement heet y.tab.h nu bindconfig2.cc.h, dus hou daar
rekening mee.Samengevat: doe geen moeite om een Lexer in C++ te compileren, hou het in C.
Maak je parser in C++ en leg je compiler uit dat sommige functies C functies
zijn met extern "C" statements.Hoe werken Lex en YACC internIn 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.
TokenwaardenZoals 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 expDit 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 '*' expDit 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. DebuggenHet is belangrijk om debuggingsfaciliteiten te hebben, vooral als je aan het
leren bent. Gelukkig kan YACC een hoop feedback geven. Deze feedback komt
tegen de prijs van enige overhead, dus je moet enige switches geven om het
aan te zetten.Voeg als je je grammatica compileert, --debug en --verbose toe aan de YACC
opdrachtregel. Voeg dit toe aan de C heading van je grammatica:int yydebug = 1;Dit zal het bestand `y.output' genereren die de gemaakte toestandsmachine
uitlegt.Als je nu de gegenereerde binary draait, zal het een *hoop* uitvoer geven
over wat er gebeurt, inclusief in welke toestand de toestandsmachine op dit
moment is, en welke tokens er worden gelezen.Peter Jinks schreef een pagina op
die
vaak voorkomende fouten en hun oplossingen bevat.
De toestandsmachineIntern draait je YACC parser een zogenaamde `toestandsmachine'. Zoals de
naam zegt, is dit een machine die in verschillende toestanden kan verkeren.
Dan zijn er regels die overgangen van de ene toestand naar de andere
bepalen. Alles begint met de zogenaamde `root' regel die ik eerder vermeld
heb.Citaat uit de uitvoer van y.output van Voorbeeld 7:
state 0
ZONETOK , and go to state 1
$default reduce using rule 1 (commands)
commands go to state 29
command go to state 2
zone_set go to state 3Standaard reduceert deze toestand met de `commands' regel. Dit is de
voornoemde recursieve regel die `commands' definieert als zijnde opgebouwd
uit individuele command statements, gevolgd door een puntkomma, gevolgd door
mogelijk meer commands.Deze toestand reduceert tot het iets tegenkomt dat het begrijpt, in dit
geval een ZONETOK, d.i. het woord `zone'. Dan gaat het naar toestand 1, die
het zone command verder afhandelt:state 1
zone_set -> ZONETOK . quotedname zonecontent (rule 4)
QUOTE , and go to state 4
quotedname go to state 5De eerste regel heeft een `.' om aan te geven waar we zijn: we hebben net
een ZONETOK gezien en zoeken nu naar een `quotedname'. Blijkbaar begint een
quotedname met een QUOTE, die ons naar toestand 4 stuurt.Compileer om dit verder te volgen Voorbeeld 7 met de vlaggen uit de
paragraaf Debuggen. Verder lezenGNU YACC (Bison) komt met een heel aardig info-bestand (.info) dat de YACC
syntax heel goed documenteert. Het vermeldt Lex maar één keer,
maar verder is het heel goed. Je kunt .info-bestanden lezen met Emacs of met
het heel aardige hulpmiddel `pinfo'. Het is ook beschikbaar op de GNU site:
Flex komt met een goede manpage die erg nuttig is als je al een ruw begrip
hebt van wat Flex doet. Het
is ook online.Na deze inleiding tot Lex en YACC kom je er misschien achter dat je meer
informatie nodig hebt. Ik heb deze boeken nog niet gelezen, maar ze klinken
goed:
Bison-The Yacc-Compatible Parser Generatorvan Charles Donnelly and Richard Stallman. Een
gebruiker vond het nuttig.Lex & YACCVan John R. Levine, Tony Mason and Doug Brown. Wordt beschouwd als het
standaardwerk over dit onderwerp, maar is een beetje gedateerd. Besprekingen
op Compilers : Principles, Techniques, and ToolsVan Alfred V. Aho, Ravi Sethi, Jeffrey D. Ullman. Het 'Dragon Book'. Uit
1985 en ze blijven het maar herdrukken. Beschouwd als het standaardwerk over
compiler constructie.
Thomas Niemann schreef een document over het schrijven van compilers en
calculators met Lex & YACC. Je vindt het De gemodereerde usenet nieuwsgroep comp.compilers kan ook helpen maar hou in
gedachten dat de mensen daar geen toegewijde parser helpdesk zijn! Lees voor
je post hun interessante en vooral de
Lex - A Lexical Analyzer Generator van M. E. Lesk and E. Schmidt is een van
de originele naslagwerken. Je vindt het
YACC: Yet Another Compiler-Compiler door Stephen C. Johnson is een van de
originele naslagwerken. Je vindt het
Het bevat nuttige wenken over stijl.Dank aanPete Jinks <pjj%cs.man.ac.uk>Chris Lattner <sabre%nondot.org>John W. Millaway <johnmillaway%yahoo.com>Martin Neitzel <neitzel%gaertner.de>Esmond Pitt <esmond.pitt%bigpond.com>Eric S. Raymond Bob Schmertz <schmertz%wam.umd.edu>Adam Sulmicki <adam%cfar.umd.edu>Markus Triska <triska%gmx.at>Erik Verbruggen <erik%road-warrior.cs.kun.nl>Gary V. Vaughan <gary%gnu.org> (lees zijn uitstekende ) (
)