Lexikalanalysator – del 2

Förra lektionen tittade vi på hur ett flex-program kunde se ut. Den här gången bygger vi ut nyckelordsprogrammet med en symboltabell. Istället för att statiskt hårdkoda in spökorden som ska generera en träff så byggs en dynamisk lista med ord upp under programmets gång. I programmet finns fyra typer av nyckelord. När ett nytt ord läggs till i listan anges också vilken av typerna ordet tillhör.

Definitionsdel

%{
#include <glib.h>

enum states {
   LOOKUP = 0,
   /* Typer av nyckelord */
   TERROR,
   KONSP,
   LEFT,
   RIGHT,
   /* N_TYPES = antal "states" */
   N_TYPES
};

/* Nuvarande state */
int state = LOOKUP;

int add_word(int type, const char *word);
int lookup_word(const char *word);

GHashTable *table = NULL;
%}
%option yylineno nounput
%%

Som synes inkluderas glib.h. Glib är ett plattformsoberoende bibliotek med användbara lågnivårutiner. I programmet används en hashtabell från glib. Att implementera en hashtabell eller länkad lista själv är fullt möjligt men skulle ta för stor plats och dra fokus bort från flex och symboltabellen. Om symboltabellen innehåller många ord är en hashtabell mycket effektivare än en länkad lista.

Sen kommer en enum med tillstånd programmet kan befinna sig i. I LOOKUP kommer programmet leta efter ord i symboltabellen. Ord som läggs till i tabellen tillhör antingen TERROR, KONSP, LEFT eller RIGHT. Ett riktigt system för att scanna e-post och annan datatrafik skulle antagligen ha många fler typer av ord (och dessutom analysera grammatiken), det här är bara ett exempel.

Nuvarande tillstånd lagras i den globala variabeln state. Funktionen add_word() lägger till ett nytt ord i listan och anger vilken typ ordet tillhör. Funktionen lookup_word() kontrollerar om ett ord finns med i listan och returnerar i så fall typen. Finns ordet inte med i listan returneras 0 (LOOKUP). Variabeln table är själva symboltabellen, en GHashTable* från glib. Slutligen anges att flex automatiskt ska hålla reda på radnumret i variabeln yylineno och att funktionen unput() inte kommer att användas (undviker en kompileringsvarning).

Regeldel

\n             state = LOOKUP; /* Ny rad, sätt state = LOOKUP.   */

^"def TERROR:" state = TERROR; /* Definiera nytt nyckelord genom */
^"def KONSP:"  state = KONSP;  /* att börja en rad med           */
^"def LEFT:"   state = LEFT;   /* "def TERROR:", "def KONSP:",   */
^"def RIGHT:"  state = RIGHT;  /* "def LEFT:" eller "def RIGHT:" */

[a-zA-Z0-9]+  {
   /* Nytt ord, kontrollera tillståndet */
   if (state != LOOKUP) {
      /* Inte LOOKUP, lägg till ord i symboltabell */
      add_word(state, yytext);
   } else {
      /* LOOKUP, kontrollera om ordet finns i symboltabellen */
      switch (lookup_word(yytext)) {

      case TERROR:
         printf("VARNING: rad %d, terrorord: \"%s\"\n",
                yylineno, yytext);
         break;

      case KONSP:
         printf("VARNING: rad %d, konspirationsord: \"%s\"\n",
                yylineno, yytext);
         break;

      case LEFT:
         printf("VARNING: rad %d, vänsterord: \"%s\"\n",
                yylineno, yytext);
         break;

      case RIGHT:
         printf("VARNING: rad %d, högerord: \"%s\"\n",
                yylineno, yytext);
         break;

      default:
         /* Ordet fanns inte med */
         break;
      }
   }
 }

. /* Ät upp alla andra tecken */
%%

När state är LOOKUP så slås inkommande ord upp i symboltabellen med lookup_word(). Om en rad börjar med ”def TERROR:” läggs resten av orden på raden till i symboltabellen med add_word() och typ satt till TERROR. Motsvarande gäller för KONSP, LEFT och RIGHT. Varje gång ny rad påträffas återgår tillståndet till LOOKUP. Tecknet ‘^’ i ett mönster betyder början av en rad. Se här för mer info om reguljära uttryck. [a-zA-Z0-9]+ matchar alla ord bestående av en eller flera bokstäver och siffror, inga andra tecken. ”Bin-Laden” skulle t ex bli två separata ord. Allt som inte matchas (t ex bindestrecket i föregående ord) kastas bort genom att ha en regel med mönstret ”.” som matchar alla tecken men inte har någon aktion. Om två mönster matchar samma ord väljer flex den längsta matchningen. Därför matchar inte ”.” något av tecknen som matchas av de övriga reglerna. Men ”\n” då? den matchar ju ny rad som bara är ett tecken. Jo, om två matchningar har samma längd väljer flex den regel som angetts först. Därför anges ”.” sist.

Användarkod

I användarkoden implementeras add_word(), lookup_word() och main() med hjälp av hashtabellen från glib. Kommentarerna i koden räcker för att förstå vad som händer. Se dokumentationen för glib för mer info om de specifika funktionsanropen till glib, de som börjar med g_ tillhör glib.

/* Lägg till ord och tillhörande
 * typ i symboltabellen.
 */
int add_word(int type, const char *word)
{
   char *w;

   if (lookup_word(word) != LOOKUP) {
      fprintf(stderr, "Ordet \"%s\" redan definierat\n", word);
      return 0;
   }

   if (type  < N_TYPES) {
      /* Allokera minne för nyckelordet */
      w = g_strdup(word);
      /* Och lägg in i tabellen */
      g_hash_table_insert(table, w, GINT_TO_POINTER(type));
      return 1;
   }

   fprintf(stderr, "Du angav type = %d, giltiga värden är 1-%d\n",
           type, N_TYPES - 1);
   return 0;
}

/* Slå upp ord i symboltabellen.
 * Returnera associerad typ om ordet hittas.
 * Returnera 0 (LOOKUP) om ordet inte hittas.
 */
int lookup_word(const char *word)
{
   gpointer p = g_hash_table_lookup(table, (gconstpointer)word);
   if (p) {
      return GPOINTER_TO_INT(p);
   }
   return LOOKUP;
}

/* Funktion för att frigöra minne för tabellens nycklar. */
void free_str(gpointer str)
{
   if (str) {
      g_free(str);
      str = NULL;
   }
}

int main(void)
{
   /* Skapa ny hashtabell. Ange att free_str()
    * ska användas för att frigöra minne för
    * nycklarna när programmet avslutas.
    */
   table = g_hash_table_new_full(g_str_hash, g_str_equal,
                                 free_str, NULL);
   if (!table) {
      fprintf(stderr, "g_hash_table_new failed\n");
      return 1;
   }

   /* Kör lexern */
   yylex();

   /* Klart, frigör allokerat minne */
   g_hash_table_destroy(table);

   return 0;
}

Hela flexkoden för exemplet kan laddas hem här. Under Debian GNU/Linux och derivat (som Ubuntu) kan allt som behövs för att kompilera exemplet installeras med följande kommando:

$ sudo apt-get install flex libglib2.0-dev gcc make

Packa upp källkoden, bygg och testkör med kommandona:


$ tar zxvf lex2.tgz
$ cd lexluthor
$ make
$ cat definitioner.txt mystiskt_brev.txt | ./symbolt

Om allt fungerar ska programmet svara – VARNING: rad 11, konspirationsord: ”bilderbergare”.

Bra jobbat. Nästa gång blir det riktigt intressant, då tänkte jag gå igenom hur flex kan samarbeta med programmet bison.

Advertisements

Om albertveli

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

En kommentar till Lexikalanalysator – del 2

  1. acecyArreve skriver:

    Very useful and informative blog. Recommended for all to see.
    http://medsdrugs.blogspot.com/

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