[ Inhalt ] [ Index ]

Endliche Automaten als Scanner

Der Aufbau der Tokens wird durch reguläre Ausdrücke   beschrieben, die einen endlichen Automaten (DEA)       definieren, der die zugehörige Sprache akzeptiert.

Prinzipiell kann man folgendermaßen vorgehen:

1. Reguläre Ausdrücke erstellen
2. Systematisch den zugehörigen NEA   konstruieren
3. Minimalen DEA ableiten (Verfahren von Thompson  )
4. DEA in einer Programmiersprache implementieren.

Beispiel:

Wir wollen eine Sprache akzeptieren, die alle Zeichenketten über enthält, die mindesten drei b hintereinander enthalten.

Der zugehörige reguläre Ausdruck ist schnell gefunden:

Die Zustandstabelle:

a b

0 0 01

1 - 2

2 - 3

3 3 3

Der zugehörige DEA:

a b

0 0 01

01 0 012

012 0 0123

0123 03 0123

03 03 013

013 03 0123

Minimaler DEA:

Den DEA können wir nun ganz simpel in C++ implementieren:

#include <iostream.h>
#include <string.h>

int main()
{
 cout << "Ein Scanner für (a+b)*bbb(a+b)*" << endl;
 
 short delta[4][2]; // Zustandsübergangsfunktion 

 const short a = 0; // token a
 const short b = 1; // token b
 
 short token;

 char buffer[256];
 int pos;
 
 const short final = 3;
 const short start = 0;
 
 short state = start;

 delta[0][a] = 0;
 delta[0][b] = 1;
 delta[1][a] = 0;
 delta[1][b] = 2;
 delta[2][a] = 0;
 delta[2][b] = 3;
 delta[3][a] = 3;
 delta[3][b] = 3;
 
 cout << "Eingabe: "; cin >> buffer; cout << endl;

 for (pos = 0; pos < strlen(buffer); pos++)
 {
  token = buffer[pos] -'a';
  state = delta[state][token];
 }
 if (state != final)
  cout << "Nicht ";
 cout << "akzeptiert" << endl;
 return 0;
}

Vom Prinzip her kann man das auch für eine ''richtige'' Programmiersprache so machen. Betrachten wir eine Sprache die

• Identifikatoren
• Integerkonstanten
• Gleikommakonstanten
• Kommandos (if, then, else)
• und einige arithmetische Operatoren besitzt:

Die regulären Ausdrücke für die Tokens sind dann:

• Identifikator: (a+b+ ...+z)(a+b+ ... +z+0+ ...+9)*
• Integer: (0+ ... +9)*
• Float: (0+ ... +9)(0+ ... +9)*.(0+ ... +9)*
• Kommando: if + then + else + ...
• Operator: ('+' + '-' + '*' + ...)

Mit dem Verfahren von Thompson können wir dann wieder einen DEA bauen, der diese Sprache akzeptiert.

Aber so ganz kann man sich mit diesem Vorgehen nicht anfreunden. Das folgende Beispiel zeigt ein (eher intuitiv entwickeltes) C-Programm, das eine Sprache ähnlich wie die eben beschriebene scannt.

#include <stdio.h>
#include <ctype.h>
#define NUMBER 400
#define COMMENT 401
#define TEXT 402
#define COMMAND 403
int lexer()
{int c, index;
 while ((c = getchar()) == ' ' || c == '\t');
 if (c == EOF) return 0;
 if (c == '.' || isdigit(c)) // number
  {while ((c = getchar()) != EOF && isdigit(c));
   if (c =='.')
    while ((c = getchar()) != EOF && isdigit(c));
   ungetc(c, stdin);
   return NUMBER;} 
 if (c == '#')    // Kommentar
 {while((c = getchar()) != EOF && c != '\n');
  ungetc(c, stdin);
  return COMMENT;}
 if (c == '"')    // Stringkonstante 
 {while((c = getchar()) != EOF && c != '"' && c != '\n');
  if (c == '\n') ungetc(c, stdin);
  return TEXT;}
 if (isalpha(c))  // Kommando
 {while((c = getchar()) != EOF && isalnum(c));
  ungetc(c, stdin);
  return COMMAND;}
 return c;}
int main()
{int val;
 while (val = lexer()) printf("value is %d\n", val);  return 0;}