Lexikalanalysator – del 3

I de två första lektionerna undersöktes programmet flex. Nu ska vi koppla ihop flex med bison för att skapa en enkel kalkylator som körs från kommandoraden. Bison analyserar grammatiken hos intexten. Samspelet mellan flex och bison sker via tokens, grundläggande element i texten. En token kan vara t ex ett nummer eller ett plustecken. Flex delar upp intexten i tokens och bison analyserar grammatiken med hjälp av regler som angetts på Backus-Naur Form (BNF). Själva huvudprogrammet ligger i bison. Varje gång bison vill ha ett nytt token anropas flex-funktionen yylex() som returnerar nästa token från intexten.

Grammatik

En enkel BNF grammatik för att definiera ett aritmetiskt uttryck (expression) kan se ut så här:

exp -> NUM        /* regel 1 */
   | exp '+' exp  /* regel 2 */
   | exp '-' exp  /* regel 3 */
   | exp '*' exp  /* regel 4 */
   | exp '/' exp  /* regel 5 */

I grammatiken ovan står exp på vänstra sidan om pilen och kallas lvalue. På höger sida finns i första regeln token NUM. De fyra operatorerna i efterföljande regler är också tokens. Pipetecknet ‘|’ betyder eller och anger att regeln ”kopplas ihop” (gäller samma lvalue) som föregående regel. Eftersom exp förekommer på även på höger sida om pilen säger man att grammatiken är rekursiv. NUM är en terminal och exp är en icke-terminal. Terminaler kallas de tokens som förekommer längst ut i parseträden, mer om detta längre ned.

I praktiken shiftas allt som kommer från flex upp på en intern stack hos bison. När innehållet på stacken passar en regel så reduceras stacken enligt regeln. Det här arbetssättet kallas shift reduce och bison är en shift reduce parser. Arbetssättet kan illustrerat med intexten ”3 + 5” på ovanstående grammatik:

shift         NUM(3)
reduce exp -> NUM(3)      /* regel 1 */
shift         '+'
shift         NUM(5)
reduce exp -> NUM(5)      /* regel 1 */
reduce exp -> exp '+' exp /* regel 2 */

Först ser flex numret 3 och returnerar token NUM med tillhörande värde 3. Bison ser att NUM kan reduceras till exp enligt regel 1. Sen kommer ‘+’ som gör att stacken innehåller ”exp +”. Detta kan inte reduceras av någon regel. Sen kommer ett NUM till som reduceras till ett exp enligt regel 1. Nu innehåller stacken ”exp + exp” vilket kan reduceras till exp enligt regel 2.

För att illustrera hur ett uttryck parsas av grammatiken brukar man rita ut ett parseträd (kallas även syntaxträd). Trädet för uttrycket ”3 + 5” ser ut så här:

          8
         exp
        / | \
       /  |  \
   3 exp '+' exp 5
      |       |
     NUM(5)  NUM(5)

Tvetydighet

Om det går att rita två olika parsträd för samma intext så är grammatiken tvetydig (ambiguous). Just den här grammatiken är faktiskt tvetydig vilket visas av följande två parsträd för intexten ”3 + 5 * 2”:

Tvetydighet


 Träd 1 => 16
           exp
          / | \
         /  |  \
    8 exp  '*'  exp 2
     / | \       |
    /  |  \     NUM(2)
3 exp '+' exp 5
   |       |
  NUM(3)  NUM(5)

 Träd 2 => 13
           exp
          / | \
         /  |  \
    3 exp  '+'  exp 10
       |       / | \
    NUM(3)    /  |  \
          5 exp '*' exp 2
             |       |
            NUM(5)  NUM(2)

Trädens olika betydelser är lätta att förstå. Det första trädet illustrerar (3 + 5) * 2 medan det andra trädet illustrerar 3 + (5 * 2). I träden har jag även ritat ut värdet av exp i grönt. Värdet av ett uttryck anges som en aktion vid reduktionen av regeln (exempel kommer längre ned).

Bison kan faktiskt hantera ovanstående grammatik genom att ange för bison att token ‘*’ ska ha högre precedens (förtur) än token ‘+’. Nu kan bison tjuvkika ett token fram (lookahead) efter att ha shiftat upp ”3 + 5” och se att nästa token är ‘*’. Sen kan bison ta beslutet att shifta istället för att reducera eftersom ‘*’ har högre precedens än ‘+’, vilket leder till träd 2. En grundregel är att inte använda tvetydig grammatik förutom i två specialfall, aritmetiska uttryck och if-then-else konstruktioner. Grammatiken bison hanterar kallas LALR(1) vilket innebär att all intext måste kunna bearbetas med endast ett tokens lookahead.

Flexfilen

Inga konstigheter, därför visas endast regeldelen här. Ladda hem källkoden för att se resten.

        /* Nummer bestående av en eller flera siffror */
        /* Sätt yylval till värdet och returnera NUM. */
[0-9]+  yylval = atoi(yytext); return NUM;

[ \t]   ; /* Ignorera whitespace */

        /* För alla andra tecken, returnera tecknet. */
        /* Låt bison hantera ev. felaktigheter.      */
.|\n    return yytext[0];

Grammatiken i bisonfilen (nästa stycke) har endast ett token som behöver hanteras av flex, NUM. När ett token har ett tillhörande värde ska det tilldelas specialvariabeln yylval. Typen på yylval bestäms av makrot YYSTYPE i bisonfilen (nästa stycke). I det här fallet är typen int.

Nästa regel ignorerar whitespace och den sista regeln returnerar alla omatchade tecken, t ex ‘+’, ‘-‘, ‘*’ och ‘/’. Om bison får ett tecken som inte matchar någon regel så skrivs det klassiska felmeddelandet syntax error ut.

Bisonfilen

En bisonfil har traditionellt filändelsen .y (efter föregångaren yacc) och består av tre delar:

  1. Definionsdel
  2. Regeldel
  3. Användarkod

Ja det stämmer, samma delar som en flexfil. Vi tittar på en del i taget.

Definitionsdel

%{
#define YYSTYPE int
#include <stdio.h>
/* Externa funktioner (genererade av flex) */
int yylex(void);
void yyerror(char const *);
/* Externa variabler (från flex) */
extern int yylineno;
%}
%token NUM    /* Tokens */
%left '-' '+' /* Låg precedens */
%left '*' '/' /* Mellan precedens */
%left UMINUS  /* Hög precedens */
%%

Nu blev det lite nytt. Först kommer YYSTYPE som definierar datatypen (int) för yylval, som innehåller värden för de tokens som har ett associerat värde. Sedan kommer deklarationer av externa funktioner och variabler som definieras av lex. %token listar alla tokens som ska returneras av flex, i detta fall bara NUM.

Sedan följer precedensreglerna för operatorerna. Det är dessa som gör att bison kan använda grammatiken fast den är tvetydig. Precedens kan anges med antingen %left eller %right. Varje rad listar tokens med samma precedens. Två tokens med samma precedens parsas från vänster till höger för %left (och från höger till vänster för %right).

Regeldel

                    /* Resultatet, line -> exp */
line: exp '\n'      { printf("= %d\n", $1); return 0; }
    ;

exp: NUM            { $$ = $1;      }
   | exp '+' exp    { $$ = $1 + $3; }
   | exp '-' exp    { $$ = $1 - $3; }
   | exp '*' exp    { $$ = $1 * $3; }
   | exp '/' exp    {
        /* Tillåt inte division med 0 */
        if ($3 == 0) {
           fprintf(stderr, "line %d: error: divide by zero\n",
                   yylineno);
           return 0;
        } else {
           $$ = $1 / $3;
        }
     }
   | '-' exp %prec UMINUS { $$ = -$2; }
   | '(' exp ')'          { $$ =  $2; }
   ;
%%

Varje regel motsvarar en reduktion och tillhörande aktion anges höger om regeln.
Den första regeln kallas startsymbol, i det här fallet line som går till ett exp följt av en newline. Aktionen skriver ut resultatet (värdet av exp) och returnerar 0 (avslutar programmet). När ett newline kommer som input så måste alltså bisons stack innehålla exakt ett exp, allting annat resulterar i syntax error. Värdet av exp ligger i specialvariabeln $1 som innehåller värdet av den första symbolen på högersidan. Den andra symbolen är $2 osv. Om vänstersidan (lvalue) ska tilldelas ett värde i aktionen så används specialvariabeln $$ (och datatypen för värdet angavs i YYSTYPE i första sektionen).

Sen kommer själva exp som kan gå till antingen terminalen NUM eller någon av de sex rekursiva reglerna. Om exp -> NUM så tilldelas $$ värdet av $1 (NUM). Det är detta värde som flex sparar i yylval när token NUM träffas på. När istället exp -> exp ‘+’ exp så tilldelas $$ värdet av $1 + $3. $2 är plustecknet som inte har något associerat värde. Reglerna för ‘-‘ och ‘*’ är snarlika. Vid division kontrolleras först att $3 inte är 0 eftersom division med 0 inte är tillåtet.

Den näst sista regeln är exp -> -exp. Token ‘-‘ har ju samma låga precedens som ‘+’, men det fungerar inte i det här fallet eftersom ett unärt minus ska ha hög precedens och gå före alla andra operatorer. Därför anges %prec UMINUS i regeln vilket innebär att terminalen i regeln ska ha samma precedens som UMINUS. Terminalen är ‘-‘ och precedensen för UMINUS angavs som hög i första sektionen. På det här sättet kan vi ge token ‘-‘ olika precedens beroende på vilket sammanhang det uppträder i.

Användarkod

Användarkoden består i vårt fall endast av ett anrop till yyparse().

int main(void)
{
   return yyparse();
}

Om inte flex hade använts så hade även funktionen yylex() implementerats här.

För hela exemplet, ladda hem källkoden. Källkoden innehåller även några printf-satser som skriver ut vad som shiftas och reduceras när ett uttryck ”äts upp” samt en extraregel för operatorn ‘%’ (mod). Installera paketen som behövs för att kompilera med:

$ sudo apt-get install gcc make flex bison

Packa upp källkoden och bygg med följande kommandon:

$ tar jxvf lex3.tar.bz2
$ cd bislex_calc
$ make
$ ./calc

Pröva att skriv in olika uttryck, som ”1+1”, ”1+2*3” eller varför inte ”2–1.”

Det här var det enklaste exemplet på vad som går att göra med flex och bison. Exemplet är för övrigt snarlikt exemplet infix notation calculator i dokumentationen för bison, med skillnad att bisonexemplet använder flyttal samt att de inte använder flex för lexern. Pröva att ändra programmet så att det använder flyttal istället. Tips, det räcker att ändra YYSTYPE samt en enda rad i calc.lex. Ett reguljärt uttryck för att matcha flyttal kan t ex se ut så här:

[0-9]+"."[0-9]*

Pröva också att lägga till matematiska operationer från math.h som t ex sin() och cos().

Eventuellt kommer en lektion till med ett mer avancerat exempel i framtiden, vi får se.

Annonser

Om albertveli

Grävande programmerare.
Det här inlägget postades i Programmering. Bokmärk permalänken.

Kommentera

Fyll i dina uppgifter nedan eller klicka på en ikon för att logga in:

WordPress.com Logo

Du kommenterar med ditt WordPress.com-konto. Logga ut / Ändra )

Twitter-bild

Du kommenterar med ditt Twitter-konto. Logga ut / Ändra )

Facebook-foto

Du kommenterar med ditt Facebook-konto. Logga ut / Ändra )

Google+ photo

Du kommenterar med ditt Google+-konto. Logga ut / Ändra )

Ansluter till %s