Lex

Från Unix.se, den fria unixresursen.

Lex är en flicka i filmen Jurassic Park.

Lex är även ett programmeringsverktyg som genererar C-kod som analyserar textmassor givet en formell beskrivning av formatet. Grundläggande förståelse av reguljära uttryck är nödvändig för att förstå det nedanstående. Viss förståelse av programmeringsspråket C är också bra.

Lex skapar en ändlig automat (eng. finite state machine, en ofta använd programmeringsteknik och ett fundament inom datalogin), som analyserar en textmassa med reguljära uttryck (att dessa används såväl här som i exempelvis grep och sed är naturligtvis ingen slump; att bemästra dem kan i många sammanhang vara nyttigt) och utför handlingar enligt de regler som ställs upp av lex-programmet. Det kanske främsta användningsområdet för lex är tillsammans med yacc, men här kommer bara ett par enkla exempel där lex i kombination med minimala snuttar C-kod behandlas.

En lex-fil (traditionellt med ändelsen .l) består av tre delar separerade med "%%":

C-deklarationer som används i aktionerna samt lex-definitioner
mönster som ska matchas i indatan, och aktionerna som ska utföras när dessa påträffas
C-kod som anropar mönstermatcharen

my_wc.l

        int rader=0, tecken=0;
%%

\n      rader++; tecken++;
.       tecken++;


%%

main()
{
        yylex();
        printf("%d rader, %d tecken.\n", rader, tecken);
}
static int yywrap (void) {return 1;}

Först deklarerar vi alltså två variabler som vi använder under analysen av textmassan: rader och tecken.

Nästa del innehåller två olika regular expressions som lex letar efter i texten. '\n' känner ni igen som betydande radbrytning, och punkten matchas av vilket tecken som helst. Till höger om dessa ser vi de korresponderande aktionerna som ska vidtas när text-regexpen matchas. I detta fall ska helt enkelt räknarna ökas.

Slutligen har vi själva programmet, som simpelt nog bara anropar den lex-genererade funktionen (som får namnet yylex()) och skriver ut resultatet. Den sista raden kan te sig lite mystisk. yylex() anropar yywrap() vid EOF, för att avgöra hurvida den ska avbryta eller inte (de fall då man inte vill det är exempelvis då det finns inkluderade filer). Vi kompilerar och kör detta:

$ lex my_wc.l
$ gcc -o my_wc lex.yy.c
$ ./my_wc </etc/passwd
33 rader, 2011 tecken.

..och noterar att det fungerar utmärkt. Den äventyrslystne kan dessutom dyka in i den genererade lex.yy.c och kolla lite innan vi fortsätter.

I nästa exempel skriver vi ett program som räknar hur vanligt förekommande ord med ett visst antal bokstäver är i en text. För detta använder vi en array som vi sparar antalet ord av en viss längd i. Vi använder den speciella variabeln yyleng, som innehåller längden på textsträngen som matchar regexpet (som i det här fallet blir [a-z]+). Resultatet skriver vi den här gången ut i yywrap, funktionen som anropas när EOF påträffas. Ett välplacerat '|' i handlingskolumnen gör så att de delar av indatan vi inte är intresserade av ignoreras. Det ensamstående semikolonet är ett giltigt c-uttryck (som inte gör någonting).

ordl.l

        int l[100];
%%
[a-z]+  l[yyleng]++;
.       |
\n      ;
%%
yywrap()
{
        int i;
        printf("Längd Antal ord\n");
        for(i=0; i<100; i++)
                if (l[i] > 0) printf("%4d%10d\n",i,l[i]);
        return(1);
}
main() {yylex();return 0;}

Vi kompilerar och kör:

$ '''lex ordl.l
$ '''gcc -o ordl lex.yy.c
$ '''./ordl < "The Cure - Friday I'm In Love.txt"

Längd Antal ord
   1        31
   2        26
   3        34
   4        31
   5        25
   6        21
   7         9
   8        11
   9         5
  10         1

..samt noterar att det återigen ser underbart ut.

Nu ska vi göra något mer avancerat, nämligen en postfix-räknare. Detta borde kännas igen för de av er som använt miniräknare från HP (även om de senaste modellerna kan göra samma sak med infix-notationen) eller programmeringsspråk som Forth. Det är alltså tänkt att indata ska ha formen "3 4 + 2 *", och att detta ska tolkas som (3+4)*2. För att göra detta skapar vi en stack, ytterligare en programmeringsteknik som faller utanför ramarna för denna artikel. Lägg märke till hur vi undviker att tecken som '+' ska tolkas som "ett eller flera" (se regexp-artikeln) genom att omge dem med citattecken.

calc.l

%{
static int sp, stack [50];
static void push (int i) { stack[++sp]=i; }
static int pop (void) { return stack[sp--]; }
%}
%%
[0-9]+  {push (atoi(yytext));}
"+"     {push (pop() + pop());}
"*"     {push (pop() * pop());}
-       {int HL= pop(); push (pop() - HL);}
"/"     {int HL= pop(); push (pop() / HL);}
=       {printf ("%d\n", pop());}
[\n]    ;
%%
int main(void) {sp= -1; yylex(); return 0;}
static int yywrap(void) {return 1;}

Hur som helst, när ni greppat det ovanstående exemplet (samt kompilerat och testkört) kommer ni inse att det faktum att det var en postfixräknare gjorde det hela mycket enklare. Allt vi behöver göra är tolka ett deluttryck i taget och antingen slänga upp det på stacken eller göra en uträkning och slänga upp resultaten av den på stacken. Om vi nu skulle vilja skriva en räknare som accepterar infix-uttryck istället så ser vi att det kan innebära en del krångel, förutsatt att vi begränsar oss till de verktyg vi hittills använt. Det vi skulle behöva är något som låter oss rekursivt definiera uttryck som uppbyggda av olika sorters deluttryck med mer komplicerad grammatik än den lex tillåter (bortsett från medelst de monstruöst stora regexps vissa har en tendens att skapa). Det vi behöver är ett verktyg så kraftfullt att man kan uttrycka hela programmeringsspråk med dess syntax. Det vi behöver är yacc.

För mer dokumentation, se även mansidan lex(1).

[edit]