Erstellen eines Lexers in C

Question

Ich möchte einen Lexer in C und ich folge dem dragon book, kann ich die Zustandsübergänge verstehen, aber wie Sie sie implementieren?

Gibt es ein besseres Buch?

Die Tatsache, dass ich eine Zeichenfolge durch eine Reihe von Zuständen analysieren muss, damit ich feststellen kann, ob die Zeichenfolge akzeptabel ist oder nicht!

Answer 1

G'day,

Unter der Annahme, meinen Sie das Drache-Buch über Compiler Design, würde ich empfehlen, um this page auf Compiler-Tools zu sehen.

Die Seite selbst ist ziemlich klein, hat aber Links zu verschiedenen hervorragenden Ressourcen für lexikalische Analysatoren.

HTH

prost,

Answer 2

Sie können einfache Zustandsübergänge mit einer einzelnen Zustandsvariablen implementieren, zum Beispiel, wenn Sie die Zustände start-> part1-> part2-> end durchlaufen möchten, können Sie eine Enumeration verwenden, um den aktuellen Zustand zu verfolgen und Verwenden Sie eine switch-Anweisung für den Code, den Sie in jedem Status ausführen möchten.

enum state { start=1, part1, part2, end} mystate; 

// ... 
mystate = start; 
do { 
    switch (mystate) { 
    case start: 
     // ... 
    case part1: 
     // ... 
    case part2: 
     // ... 
     if (part2_end_condition) mystate = end; // state++ will also work 
     // Note you could also set the state back to part1 on some condition here 
     // which creates a loop 
     break; 
    } 
} while (mystate != end); 

Für komplexere Zustandsübergänge, die von verschiedenen Variablen abhängen, sollten Sie Tabellen/Arrays wie folgt verwenden:

var1 var2 var_end next_state 
0  0  0   state1 
0  1  0   state2 
1  0  0   state3 
1  1  0   state4 
-1  -1  1   state_end // -1 represents "doesn't matter" here 

Answer 3

Wenn Sie sich für eine modernere Behandlung als die Drachen Buch (n) sucht: Andrew W. Appel und Maia Ginsburg, Modern Compiler Implementation in C, Cambridge University Press, 2008.

Kapitel 2 konzentriert sich auf Lexikalische Analyse: Lexikalische Tokens, Reguläre Ausdrücke, Finite Automaten; Nichtdeterministische endliche Automaten; Lexer Generatoren

Blick auf die Table of Contents

Answer 4

Es gibt mehr als einen Weg, es zu tun. Jeder reguläre Ausdruck entspricht direkt einem einfach strukturierten Programm. Zum Beispiel könnte ein Ausdruck für Zahlen dies:

// regular expression 
digit* [.digit*] 

und die entsprechenden C-Code wäre:

// corresponding code 
while(DIGIT(*pc)) pc++; 
if (*pc=='.'){ 
    pc++; 
    while(DIGIT(*pc)) pc++; 
} 

Der Übergang Tisch Art des Bauens lexers ist, meiner Meinung nach, unnötig kompliziert, und läuft natürlich langsamer.

Answer 5

Das Programm flex (ein Klon von Lex) wird einen Lexer für Sie erstellen.

Wenn eine Eingabedatei mit den Lexerregeln angegeben wird, wird eine C-Datei mit einer Implementierung eines Lexers für diese Regeln erstellt.

Sie können somit die Ausgabe von flex prüfen, wie eine Lexer in C zu schreiben, das heißt, wenn Sie nicht nur tun wollen flex Lexer verwenden ...