Lexikalanalysator – del 1

En lexikalanalysator är ett program som känner igen mönster i en text. Det finns många användningsområden, t ex som hjälpprogram för att bygga en kompilator. Programmet lex är ett gammalt verktyg för att skapa en lexikalanalysator. En modernare utveckling av lex är programmet flex. Flex matchar mönster i text med hjälp av reguljära uttryck (kallas ofta regex efter engelskans regular expressions).

Ett flexprogram är uppbygt av tre delar och delarna avskiljs med två procenttecken %%.

  1. Definitionsdel
  2. Regeldel
  3. Användarkod

Nedan är ett exempel på ett flexprogram som räknar antalet rader och antalet tecken i en textfil:

%{
   /* Globala variabler */
   int rader = 0;
   int tecken = 0;
%}

%%
\n      rader++; tecken++; /* Ny rad */
.       tecken++;          /* Nytt tecken */

%%
int main(void)
{
   /* Kör reglerna på inkommande text */
   yylex();
   printf("Antal rader: %d, antal tecken: %d\n", rader, tecken);

   return 0;
}

För att skapa programmet krävs att flex är installerat och att en c-kompilator är installerad. I exemplen använder jag kompilatorn gcc. Spara flex-programmet ovan i en textfil med namnet wc.lex. Kompilera sedan med följande kommandon:

flex -o wc.c wc.lex
gcc -o wc wc.c -ll

Första raden kompilerar filen wc.lex till filen wc.c och den andra raden kompilerar wc.c till det körbara programmet wc. Argumentet -o används för att döpa utfilen och argumentet -ll betyder att gcc ska länka mot biblioteket libl (som följer med flex). Pröva programmet genom att skicka en textfil, vilken som helst, genom det nya programmet:

cat /etc/passwd | ./wc

./ före wc betyder att programmet ligger i aktuell katalog. Under unix finns även ett standardprogram som heter wc. Om inte ./ hade angivits så hade antagligen standardprogrammet körts istället för det egna programmet.

Låt oss gå igenom flex-programmet. I första stycket (definitionsdelen) deklareras variablerna rader och tecken av typen int (heltal) och initieras samtidigt till värdet 0. Deklarationen ligger i ett block som startar med %{ och avslutas med %}. All text inuti sådana block klistras in omodifierat i c-filen som skapas av flex.

I nästa stycke (regeldelen) anges reglerna. Varje regel består av ett mönster (blå färg) och en aktion (svart färg). Första regeln består av mönstret \n (som betyder ny rad) och aktionen är c-kod för att räkna upp värdet hos variablerna rader och tecken med 1. Den andra och sista regeln består av mönstret . (en punkt) som matchar alla tecken utom ny rad (newline). Aktionen räknar upp variabeln tecken (men inte variabeln rader).

Det sista stycket (användarkod) består av c-funktioner som klistras in rakt in i den genererade c-koden. Funktionen main() finns i alla c-program och yylex() skapas automatiskt av flex. Det är den som gör jobbet och kör reglerna på den inkommande texten. Efter yylex() skrivs resultatet ut på skärmen med hjälp av c-funktionen printf(). Klart.

Låt oss titta på ett program till. Följande program letar efter nyckelord i en text och skriver ut en varning om ett nyckelord hittas. I varningen anges också radnumret där nyckelordet hittades.

%{
   int rad = 1;
%}
%%

bomb |
plantera |
attack       printf("VARNING: Ordet %s hittades på rad %d\n", yytext, rad);

\n           rad++;
.            /* Ät upp alla andra tecken (så de inte skrivs ut) */

Först kan vi notera att sista stycket (användarkod) utelämnats. Flex använder en defaultfunktion för main() som endast kör yylex() och avslutar programmet om ingen main() anges i lex-filen.

I definitionsdelen finns variabeln rad som initieras till 1. Regeldelen innehåller en regel som matchar nyckelord. Tecknet | (AltGR + knappen bredvid vänstra shift) betyder eller och det kan användas för att koppla ihop flera mönster med en aktion. I aktionen används variabeln yytext, som är en specialvariabel som flex sparar den matchade texten i. Sedan finns en regel som räknar upp antalet rader när tecknet \n påträffas samt en regel som ”äter upp” alla omatchade tecken så att de inte skrivs ut på skärmen.

Pröva att kompilera och skicka en text genom programmet. Om texten innehåller ett av nyckelorden ska programmet skriva ut en varning. Det går också att köra programmet ”interaktivt” genom att bara starta programmet utan att skicka någon fil:

./nyckelord
Hej!
Pjäsen är planterad.
VARNING: Ordet plantera hittades på rad 2

Avsluta texten genom att trycka på Ctrl+D.

Till sist kan vi titta på ett program som använder en ny finess, startvillkor:

%x comment
%%

"/*"                   BEGIN(comment);  /* Start på C-kommentar, byt state till "comment" */
<comment>[^*\n]*       /* Ät upp allt utom '*' */
<comment>"*"+[^*/\n]*  /* Ät upp en eller flera '*' som _inte_ följs av '/' */
<comment>\n            /* Ät upp newline inne i kommentar */
<comment>"*"+"/"       BEGIN(INITIAL);  /* Slut på kommentar, byt tillbaka till "INITIAL" */

"//".*                 /* Ät upp C++-kommentarer, // */

När ovanstående kod kompileras så fås ett program som tar bort alla C och C++ kommentarer från C/C++ kod. Pröva att skicka en C-fil genom programmet så får du se (cat test.c | ./strip_comments).

Definitionsdelen innehåller %x comment som anger att det finns ett startvillkor med namnet comment längre ned i regeldelen. Startvillkor innebär att vissa regler bara körs när flex befinner sig i ett visst tillstånd. När programmet startas befinner sig flex i tillståndet INITIAL. I regeldelen ser vi att tillståndet ändras till comment när strängen ”/*” hittas i texten. Regler som markerats med <comment> körs alltså endast när programmet befinner sig i detta tillstånd. Regler där inget startvillkor anges körs i tillståndet INITIAL.

Det var allt för denna gång. Nästa gång tänkte jag titta på hur man kan lägga till en symboltabell till ett flex-program.

Advertisements

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