Lex (datorprogram)

Från Rilpedia

Hoppa till: navigering, sök
Wikipedia_letter_w.pngTexten från svenska WikipediaWikipedialogo_12pt.gif
rpsv.header.diskuteraikon2.gif

Lex är inom datalogi ett datorprogram som genererar programkod för lexikalisering, en s.k. scanner eller lexer. Lex används ofta i samband med yacc, ett program som genererar programkod för en parser. Lex skrevs ursprungligen av Eric Schmidt och Mike Lesk, och är standardverktyget för lexikalisering på många Unix-system. Lex ingår i POSIX-standarden.

Programmet läser en textfil (eller eg. en indataström via stdin) som innehåller en specifikation av vilka lexikala element som ska identifieras under analysen. Det genererade programmet är en implementation av denna lexikalisering i programspråket C. Analysen bygger på att mönster i indata identifieras med hjälp av reguljära uttryck, varpå användardefinierade funktioner eller programkodavsnitt körs för varje identifierat mönster. Den genererade funktion som utför analysen är yylex().

Vid publiceringen var programmet upphovsrättsskyddat, men idag finns versioner av lex som är baserade på den ursprungliga AT&T-koden tillgängliga som fri programvara, till exempel som del i OpenSolaris och Plan 9. En vanlig variant av lex är flex (fast lexical analyzer).


Innehåll

Lex-filer

Uppbyggnaden av lex-filer liknar yacc-filer på många sätt: filerna består av tre avsnitt avgränsade med rader som endast består av två procenttecken:

definitioner
%%
regler
%%
C-kod
  • Avsnittet definitioner används för att definiera makron och importera header-filer i programspråket C. Det går också att skriva C-kod i detta avsnitt, som då kopieras i oförändrat skick till den genererade källkodsfilen.
  • I avsnittet regler finns beskrivningar av hur reguljära uttryck (mönster) ska kopplas till C-uttryck. När ett mönster identifieras under analysen körs motsvarande C-kod.
  • Avsnittet C-kod innehåller uttryck i C och funktioner som kopieras direkt till den genererade källkodsfilen. Uttrycken innehåller den programkod som anropas av reglerna i regelavsnittet. För stora program är det oftast mer praktiskt att lägga källkoden i en separat fil och länka in den vid kompileringen.

Exempel

Följande exempel är en indatafil för flex (en variant av lex). Det genererade programmet känner igen siffersträngar i programmets indata, och skriver ut siffrorna.

/*** Definitioner ***/

%{
/* C-kod som kopieras direkt */
#include <stdio.h>
%}

/* Alternativ som anger att flex bara ska läsa en indatafil  */
%option noyywrap

%%
    /*** Regler ***/

    /* Uttrycket [0-9]+ matchar en sträng med en eller flera siffror */
[0-9]+  {
            /* yytext är en sträng som innehåller den matchade texten. */
            printf("Hittade ett heltal: %s\n", yytext);
        }

.       {   /* Hoppa över alla andra tecken. */   }

%%
/*** C-kod ***/

int main(void)
{
    /* Kör analysen och avsluta */
    yylex();
    return 0;
}

Om denna indatafil skickas till flex genereras en C-källkodsfil med namnet lex.yy.c. Denna fil kan kompileras till körbar kod som söker efter och skriver ut siffror. Om det genererade programmet körs med argumentet abc123z.!&*2ghj6 ger programmet följande resultat:

Hittade ett heltal: 123
Hittade ett heltal: 2
Hittade ett heltal: 6

Lex och Yacc

Lex används ofta tillsammans med Yacc (en parsergenerator). Yacc använder formell grammatik för att parsa en indataström, vilket Lex inte kan göra med enbart reguljära uttryck (Lex är en enkel ändlig automat). Å andra sidan kan inte Yacc läsa direkt från en indataström, utan måste ges en serie lexikala element (tokens) som indata. Lex används ofta för att skapa denna tokensekvens.

Källor

Denna artikel är helt eller delvis baserad på material från engelskspråkiga Wikipedia

Se även

Personliga verktyg