Compilerbau: Automat

Willemers Informatik-Ecke

Ein Automat ist eine virtuelles Maschine, das aufgrund externer Ereignisse ihren Zustand ändert. Ein deterministischer (endlicher) Automat ist ein Automat, dessen Übergang von einem Zustand in den anderen eindeutig durch das Ereignis gesteuert wird. Es ist einleuchtend, dass ein deterministischer Automat für die Programmierung bevorzugt wird.

Das folgende Beispiel ist ein Automat, der C-Kommentare aus einem Zeichenstrom ausfiltert. Ein C-Kommentar beginnt mit /* und endet mit */. Der Automat kennt vier Zustände: Start, Slash, InComment und Asterix.

Zustand Zeichen nächster Zustand Aktion
Start alle, außer '/' Start Drucke Zeichen
Start '/' Slash
Slash '/' Slash Drucke '/'
Slash '*' InComment
Slash alle, außer '*' und '/' Start Drucke '/', Drucke Zeichen
InComment '*' Asterix
InComment alle, außer '*' InComment
Asterix '/' Start
Asterix '*' Asterix
Asterix alle außer '/' oder '*' InComment

Die Umsetzung in Programm-Code ist einigermassen trivial.

enum tStatus = {START, SLASH, INCOMMENT, ASTERIX};
tStatus Status = START;

void DeleteComment()
{
char c;

  c = getchar();
  while (c!=0 && c!=EOF) {
    switch(Status) {
    case START:
      if (c=='/') Status = SLASH;
      else putchar(c);
      break;
    case SLASH:
      if (c=='*') Status = INCOMMENT;
      else if (c=='/') putchar(c);
      else { putchar('/'); putchar(c); Status = START; }
      break;
    case INCOMMENT:
      if (c=='*') Status = ASTERIX;
      break;
    case ASTERIX:
      if (c=='/') Status = START;
      else if (c!='*') Status = INCOMMENT;
      break;
    }
    c = getchar();
  }
}


Homepage (C) Copyright 2000 Arnold Willemer