direkt codierten vs Tabellen-lexer?

Question

Ich bin neu in Compilerbau Welt, möchte ich wissen, was sind die Unterschiede zwischen Direct-coded vs Tabellen-Lexer Analysator?

Verwenden Sie bitte einen einfachen Quellcode, wenn es möglich ist.

Danke.

Edit:

in Engineering a Compiler Buch, der Autor geteilt lexers in drei (3) Arten: tabellengesteuerte, direkt codiert und Hand codiert.

Answer 1

Ich nehme an, dass Sie mit "direkt codiert" einen handschriftlichen Lexer meinen und nicht einen, der als Ausgabe eines Lexergenerators erzeugt wird. In diesem Fall ... (siehe unten).

... ein tabellengesteuerte Lexer ist ein (in der Regel automatisch generierte) Programm, das eine Art von Lookup-Tabelle verwendet, um zu bestimmen, welche Maßnahmen zu ergreifen. Betrachten wir die finite automaton, die dem regulären Ausdruck entspricht ab*a (absichtlich nicht minimiert):

Wenn wir uns darauf beschränkt nur Zeichen ‚a‘ und ‚b‘ unter Berücksichtigung, wir es in einer Lookup-Tabelle kodieren könnten wie so:

#define REJECT -1 

/* This table encodes the transitions for a given state and character. */ 
const int transitions[][] = { 
    /* In state 0, if we see an a then go to state 1 (the 1). 
    * Otherwise, reject input. 
    */ 
    { /*a*/ 1, /*b*/ REJECT }, 
    { /*a*/ 2, /*b*/ 3  }, 
    { /*a*/ -1, /*b*/ -1  }, /* Could put anything here. */ 
    { /*a*/ 2, /*b*/ 3  } 
}; 

/* This table determines, for each state, whether it is an accepting state. */ 
const int accept[] = { 0, 0, 1, 0 }; 

Jetzt brauchen wir nur einen Treiber, der tatsächlich die Tabelle verwendet:

int scan(void) { 
    char ch; 
    int state = 0; 

    while (!accept[state]) { 
     ch = getchar() - 'a'; /* Adjust so that a => 0, b => 1. */ 
     if (transitions[state][ch] == REJECT) { 
      fprintf(stderr, "invalid token!\n"); 
      return 0; /* Fail. */ 
     } else { 
      state = transitions[state][ch]; 
     } 
    } 
    return 1; /* Success! */ 
} 

Natürlich würde in einem echten Lexer jedes Token einen entsprechenden akzeptierenden Zustand haben, und Sie müssten irgendwie die Accept-Tabelle modifizieren, um die Token-Kennung zu enthalten. Ich möchte jedoch zwei Dinge betonen:

1. Ein Tabellen-gesteuerter Lexer funktioniert nicht unbedingt auf der Ebene der DFA-Staaten.
2. Ich empfehle nicht, Tabellen-lexers von Hand zu schreiben, wie es ein langwieriger und fehleranfälliger Prozess ist.

A handschriftliche (mangels eines besseren Namens) Lexer in der Regel keine Lookup-Tabelle verwenden. Angenommen, wir eine Lexer für eine einfache Lisp-ähnliche Sprache möchten, die Klammern, Identifikatoren und Dezimalzahlen hat:

enum token { 
    ERROR, 
    LPAREN, 
    RPAREN, 
    IDENT, 
    NUMBER 
}; 

enum token scan(void) { 
    /* Consume all leading whitespace. */ 
    char ch = first_nonblank(); 
    if (ch == '(') return LPAREN; 
    else if (ch == ')') return RPAREN; 
    else if (isalpha(ch)) return ident(); 
    else if (isdigit(ch)) return number(); 
    else { 
     printf("invalid token!\n"); 
     return ERROR; 
    } 
} 

char first_nonblank(void) { 
    char ch; 
    do { 
     ch = getchar(); 
    } while (isspace(ch)); 
    return ch; 
} 

enum token ident(void) { 
    char ch; 
    do { 
     ch = getchar(); 
    } while (isalpha(ch)); 
    ungetc(ch, stdin); /* Put back the first non-alphabetic character. */ 
    return IDENT; 
} 

enum token number(void) { 
    char ch; 
    do { 
     ch = getchar(); 
    } while (isdigit(ch)); 
    ungetc(ch, stdin); /* Put back the first non-digit. */ 
    return NUMBER; 
} 

Wie das tabellengesteuerte Lexer Beispiel diesen nicht abgeschlossen ist. Zum einen braucht es eine Art Pufferung, um die Zeichen zu speichern, die Teil eines Tokens wie IDENT und NUMBER sind. Zum anderen wird EOF nicht besonders elegant gehandhabt. Aber hoffentlich bekommst du das Wesentliche davon.

---

bearbeiten: in Engineering a Compiler auf der Definition zugrunde, ein direkter codierten LEXER im Grunde eine Mischung aus beiden ist. Anstatt eine Tabelle zu verwenden, verwenden wir Codeetiketten, um Zustände darzustellen. Mal sehen, wie das mit dem gleichen DFA aussehen würde wie zuvor.

int scan(void) { 
    char ch; 

state0: 
    ch = getchar(); 
    if (ch == 'a') goto state1; 
    else { error(); return 0; } 

state1: 
    ch = getchar(); 
    if (ch == 'a') goto state2; 
    else if (ch == 'b') goto state3; 
    else { error(); return 0; } 

state2: 
    return 1; /* Accept! */ 

state3: 
    ch = getchar(); 
    if (ch == 'a') goto state2; 
    else if (ch == 'b') goto state3; /* Loop. */ 
    else { error(); return 0; } 
} 

---

In meiner persönlichen Erfahrung das „beste“ Konzept für das Schreiben lexers ist der handgeschriebene Ansatz, den ich oben beschrieben. Es funktioniert auf jeder Plattform, in jeder Sprache, Sie müssen keine alten Werkzeuge wie Lex lernen und, vielleicht am wichtigsten, haben Sie die Flexibilität, den Lexer mit Funktionen zu erweitern, die mit einem Werkzeug schwer oder unmöglich zu implementieren sind. Zum Beispiel möchten Sie vielleicht, dass Ihr Lexikon Python-ähnliche Blockeindrücke versteht, oder vielleicht müssen Sie bestimmte Tokenklassen dynamisch erweitern.