Was sollte der Datentyp der Token sein, die ein Lexer an seinen Parser zurückgibt?

21

Welchen Datentyp soll ein Lexer, wie im Titel erwähnt, zurückgeben / dem Parser geben? Beim Lesen des Artikels zur lexikalischen Analyse , den Wikipedia verfasst hat, wurde Folgendes festgestellt:

In der Informatik ist die lexikalische Analyse das Umwandeln einer Folge von Zeichen (wie in einem Computerprogramm oder einer Webseite) in eine Folge von Token ( Zeichenfolgen mit einer identifizierten "Bedeutung").

Im völligen Widerspruch zu der obigen Aussage, als eine andere Frage, die ich auf einer anderen Site gestellt habe ( Code Review, wenn Sie neugierig sind), beantwortet wurde, erklärte die antwortende Person:

Der Lexer liest normalerweise die Zeichenkette und wandelt sie in einen Strom von Lexemen um. Die Lexeme müssen nur ein Strom von Zahlen sein .

und er gab dieses Bild:

nl_output => 256
output    => 257
<string>  => 258

Später in dem Artikel erwähnte er Flexeinen bereits existierenden Lexer und sagte, das Schreiben von "Regeln" damit sei einfacher als das Schreiben eines Lexers von Hand. Er fuhr fort, mir dieses Beispiel zu geben:

Space              [ \r\n\t]
QuotedString       "[^"]*"
%%
nl_output          {return 256;}
output             {return 257;}
{QuotedString}     {return 258;}
{Space}            {/* Ignore */}
.                  {error("Unmatched character");}
%%

Um meinen Einblick zu erweitern und mehr Informationen zu erhalten, habe ich den Wikipedia-Artikel über Flex gelesen . Der Flex-Artikel zeigte, dass Sie mit Token auf folgende Weise einen Satz von Syntaxregeln definieren können:

digit         [0-9]
letter        [a-zA-Z]

%%
"+"                  { return PLUS;       }
"-"                  { return MINUS;      }
"*"                  { return TIMES;      }
"/"                  { return SLASH;      }
"("                  { return LPAREN;     }
")"                  { return RPAREN;     }
";"                  { return SEMICOLON;  }
","                  { return COMMA;      }
"."                  { return PERIOD;     }
":="                 { return BECOMES;    }
"="                  { return EQL;        }
"<>"                 { return NEQ;        }
"<"                  { return LSS;        }
">"                  { return GTR;        }
"<="                 { return LEQ;        }
">="                 { return GEQ;        }
"begin"              { return BEGINSYM;   }
"call"               { return CALLSYM;    }
"const"              { return CONSTSYM;   }
"do"                 { return DOSYM;      }
"end"                { return ENDSYM;     }
"if"                 { return IFSYM;      }
"odd"                { return ODDSYM;     }
"procedure"          { return PROCSYM;    }
"then"               { return THENSYM;    }
"var"                { return VARSYM;     }
"while"              { return WHILESYM;   }

Es scheint mir, dass der Flex-Lexer Zeichenfolgen von Keywords \ Token zurückgibt. Es können jedoch Konstanten zurückgegeben werden, die bestimmten Zahlen entsprechen.

Wenn der Lexer Zahlen zurückgeben würde, wie würde er String-Literale lesen? Die Rückgabe einer Zahl ist für einzelne Stichwörter in Ordnung. Aber wie würden Sie mit einer Zeichenfolge umgehen? Müsste der Lexer die Zeichenfolge nicht in Binärzahlen konvertieren, und der Parser würde die Zahlen dann wieder in eine Zeichenfolge konvertieren. Es erscheint dem Lexer viel logischer (und einfacher), Zeichenfolgen zurückzugeben und den Parser dann beliebige Zahlenzeichenfolgenliterale in tatsächliche Zahlen umwandeln zu lassen.

Oder könnte der Lexer beides zurückgeben? Ich habe versucht, einen einfachen Lexer in c ++ zu schreiben, mit dem Sie nur einen Rückgabetyp für Ihre Funktionen haben. Das veranlasste mich, meine Frage zu stellen.

Um meine Frage in einem Absatz zusammenzufassen: Wenn Sie ein Lexer schreiben und davon ausgehen, dass es nur einen Datentyp (Zeichenfolgen oder Zahlen) zurückgeben könnte, was wäre die logischere Wahl?

Christian Dean
quelle
Der Lexer gibt das zurück, was Sie ihm sagen. Wenn in Ihrem Design Nummern erforderlich sind, werden Nummern zurückgegeben. Für die Darstellung von String-Literalen ist natürlich etwas mehr erforderlich. Siehe auch Ist es eine Aufgabe von Lexer, Zahlen und Zeichenfolgen zu analysieren? Beachten Sie, dass Zeichenfolgenliterale im Allgemeinen nicht als "Sprachelemente" betrachtet werden.
Robert Harvey
@RobertHarvey Würden Sie also das String-Literal in Binärzahlen konvertieren?
Christian Dean
Nach meinem Verständnis besteht der Zweck des Lexers darin, die Sprachelemente (wie Schlüsselwörter, Operatoren usw.) in Token umzuwandeln. Zitierte Zeichenfolgen sind daher für den Lexer nicht von Interesse, da sie keine Sprachelemente sind. Obwohl ich selbst noch nie ein Lexer geschrieben habe, würde ich mir vorstellen, dass die zitierte Zeichenfolge einfach unverändert (einschließlich der Anführungszeichen) durchgereicht wird.
Robert Harvey
Sie sagen also, dass der Lexer keine String-Literale liest oder sich darum kümmert. Und so muss der Parser nach diesen String-Literalen suchen? Das ist sehr verwirrend.
Christian Dean
Vielleicht möchten Sie ein paar Minuten damit verbringen, dies zu lesen: en.wikipedia.org/wiki/Lexical_analysis
Robert Harvey

Antworten:

10

Wenn Sie eine Sprache durch Lexing und Parsing verarbeiten, haben Sie im Allgemeinen eine Definition Ihrer lexikalischen Token, z.

NUMBER ::= [0-9]+
ID     ::= [a-Z]+, except for keywords
IF     ::= 'if'
LPAREN ::= '('
RPAREN ::= ')'
COMMA  ::= ','
LBRACE ::= '{'
RBRACE ::= '}'
SEMICOLON ::= ';'
...

und Sie haben eine Grammatik für den Parser:

STATEMENT ::= IF LPAREN EXPR RPAREN STATEMENT
            | LBRACE STATEMENT BRACE
            | EXPR SEMICOLON
EXPR      ::= ID
            | NUMBER
            | ID LPAREN EXPRS RPAREN
...

Ihr Lexer nimmt den Eingabestream und erzeugt einen Stream von Tokens. Der Token-Stream wird vom Parser verbraucht, um einen Analysebaum zu erstellen. In einigen Fällen reicht es aus, nur den Typ des Tokens zu kennen (z. B. LPAREN, RBRACE, FOR), in einigen Fällen benötigen Sie jedoch den tatsächlichen Wert , der dem Token zugeordnet ist. Wenn Sie beispielsweise auf ein ID-Token stoßen, möchten Sie die tatsächlichen Zeichen, aus denen sich die ID zusammensetzt, später herausfinden, auf welche ID Sie verweisen möchten.

Normalerweise haben Sie also ungefähr Folgendes:

enum TokenType {
  NUMBER, ID, IF, LPAREN, RPAREN, ...;
}

class Token {
  TokenType type;
  String value;
}

Wenn der Lexer ein Token zurückgibt, wissen Sie, um welchen Typ es sich handelt (den Sie zum Analysieren benötigen) und aus welcher Zeichenfolge es generiert wurde (den Sie später zum Interpretieren von Zeichenfolgen und numerischen Literalen sowie Bezeichnern benötigen, etc.). Es könnte sich so anfühlen, als würden Sie zwei Werte zurückgeben, da Sie einen sehr einfachen Aggregattyp zurückgeben, aber Sie brauchen wirklich beide Teile. Schließlich möchten Sie die folgenden Programme anders behandeln:

if (2 > 0) {
  print("2 > 0");
}
if (0 > 2) {
  print("0 > 2");
}

Diese produzieren die gleiche Folge von Token - Typen : IF, LPAREN, NUMBER, GREATER_THAN, NUMBER, RPAREN, lbrace, ID, LPAREN, STRING, RPAREN, SEMIKOLON, RBRACE. Das heißt, sie analysieren auch das Gleiche. Wenn Sie jedoch tatsächlich etwas mit dem Analysebaum tun, ist es Ihnen wichtig, dass der Wert der ersten Zahl "2" (oder "0") und der Wert der zweiten Zahl "0" (oder "2") ist ') und dass der Wert der Zeichenfolge' 2> 0 '(oder' 0> 2 ') ist.

Joshua Taylor
quelle
Ich verstehe das meiste, was du sagst, aber wie wird String valuesich das füllen? Wird es mit einer Zeichenfolge oder einer Zahl gefüllt? Und wie würde ich den StringTyp definieren ?
Christian Dean
1
@ Mr.Python Im einfachsten Fall ist es nur die Zeichenfolge, die zur lexikalischen Produktion passt. Wenn Sie also foo (23, "bar") sehen , erhalten Sie die Token [ID, "foo"], [LPAREN, "("), [NUMMER, "23"], [COMMA, "," ], [STRING, 23], [RPAREN,)] . Der Erhalt dieser Informationen könnte wichtig sein. Sie können auch einen anderen Ansatz wählen und den Wert einen Vereinigungstyp haben, der eine Zeichenfolge oder eine Zahl usw. sein kann, und den richtigen Wertetyp auswählen, basierend auf der Art Ihres Tokentyps (z. B. wenn der Tokentyp NUMBER ist) , benutze value.num und wenn es STRING ist, benutze value.str).
Joshua Taylor
@ MrPython "Und wie würde ich den String-Typ definieren?" Ich habe aus einer Java-artigen Denkweise heraus geschrieben. Wenn Sie in C ++ arbeiten, können Sie den Zeichenfolgentyp von C ++ verwenden, oder wenn Sie in C arbeiten, können Sie ein Zeichen * verwenden. Der Punkt ist derjenige, der einem Token zugeordnet ist. Sie haben den entsprechenden Wert oder den Text, den Sie interpretieren können, um den Wert zu erzeugen.
Joshua Taylor
1
@ ollydbg23 Das ist eine Option und keine unzumutbare, aber es macht das System intern weniger konsistent. Wenn Sie beispielsweise den Zeichenfolgenwert der zuletzt analysierten Stadt möchten, müssen Sie jetzt explizit nach einem Nullwert suchen und dann mithilfe eines Reverse-Token-to-String-Lookups herausfinden, wie die Zeichenfolge lauten würde. Plus, es ist engere Kopplung zwischen dem Lexer und dem Parser; Es muss mehr Code aktualisiert werden, wenn LPAREN jemals mit verschiedenen oder mehreren Zeichenfolgen übereinstimmen könnte.
Joshua Taylor
2
@ ollydbg23 Ein Fall wäre ein einfacher Pseudo-Minifier. Dies ist einfach genug parse(inputStream).forEach(token -> print(token.string); print(' '))(dh Sie müssen nur die Zeichenfolgenwerte der Token drucken, die durch ein Leerzeichen voneinander getrennt sind). Das geht ziemlich schnell. Und selbst wenn LPAREN nur aus "(" hervorgeht, kann dies eine konstante Zeichenfolge im Speicher sein, sodass das Einfügen eines Verweises darauf in das Token möglicherweise nicht teurer ist als das Einfügen des Nullverweises. Im Allgemeinen würde ich lieber schreiben Code, der mich nicht zu einem Sonderfall macht Code
Joshua Taylor
6

Welchen Datentyp soll ein Lexer, wie im Titel erwähnt, zurückgeben / dem Parser geben?

"Token" natürlich. Ein Lexer erzeugt einen Strom von Token, daher sollte er einen Strom von Token zurückgeben .

Er erwähnte Flex, einen bereits existierenden Lexer, und sagte, das Schreiben von "Regeln" wäre einfacher als das Schreiben eines Lexers von Hand.

Maschinengenerierte Lexer haben den Vorteil, dass Sie sie schnell generieren können. Dies ist besonders praktisch, wenn Sie glauben, dass sich Ihre lexikalische Grammatik stark ändern wird. Sie haben den Nachteil, dass Sie bei Ihren Implementierungsentscheidungen oft nicht viel Flexibilität haben.

Das heißt, wen interessiert es, wenn es "einfacher" ist? Das Lexer zu schreiben ist normalerweise nicht der schwierige Teil!

Wenn Sie ein Lexer schreiben und davon ausgehen, dass es nur einen Datentyp (Zeichenfolgen oder Zahlen) zurückgeben kann, welche Option ist die logischere?

Weder. Ein Lexer hat normalerweise eine "next" -Operation, die ein Token zurückgibt, also sollte es ein Token zurückgeben . Ein Token ist keine Zeichenfolge oder Zahl. Es ist ein Zeichen.

Das letzte Lexer, das ich geschrieben habe, war ein "Full Fidelity" -Lexer, dh, es gab ein Token zurück, das die Position aller Whitespaces und Kommentare - die wir "Trivia" nennen - im Programm sowie das Token verfolgte. In meinem Lexer wurde ein Token definiert als:

  • Eine Reihe führender Trivia
  • Eine Art Token
  • Eine Tokenbreite in Zeichen
  • Eine Reihe von nachgestellten Kleinigkeiten

Trivia wurde definiert als:

  • Eine Kleinigkeit - Leerzeichen, Zeilenumbruch, Kommentar und so weiter
  • Eine Quizbreite in Zeichen

Also wenn wir so etwas hätten

    foo + /* comment */
/* another comment */ bar;

die mit Token - Arten , wie vier Token würde lex Identifier, Plus, Identifier, Semicolon, und Breite 3, 1, 3, 1. Die erste Kennung hat führendes Haupt , bestehend aus Whitespacemit einer Breite von 4 und Hinterhaupt Whitespacemit einer Breite von 1. Das Plushat keine führende Haupt und abschließende Trivia bestehend aus einem Whitespace, einem Kommentar und einer Newline. Der endgültige Bezeichner besteht aus einem Kommentar, einem Leerzeichen usw.

Mit diesem Schema wird jedes Zeichen in der Datei in der Ausgabe des Lexers berücksichtigt. Dies ist eine praktische Eigenschaft, die Sie beispielsweise für die Syntaxfärbung benötigen.

Wenn Sie diese Kleinigkeiten nicht benötigen, können Sie einfach zwei Dinge anfertigen: die Art und die Breite.

Möglicherweise stellen Sie fest, dass das Token und die Trivia nur ihre Breite und nicht ihre absolute Position im Quellcode enthalten. Das ist absichtlich. Ein solches Schema hat Vorteile:

  • Es ist kompakt im Speicher- und Drahtformat
  • Es ermöglicht das Nachlesen von Bearbeitungen. Dies ist nützlich, wenn der Lexer in einer IDE ausgeführt wird. Das heißt, wenn Sie eine Bearbeitung in einem Token erkennen, sichern Sie Ihren Lexer vor der Bearbeitung auf ein paar Token und beginnen erneut mit dem Lexen, bis Sie mit dem vorherigen Token-Stream synchronisiert sind. Wenn Sie ein Zeichen eingeben, ändert sich die Position jedes Tokens nach diesem Zeichen, aber normalerweise ändern sich nur ein oder zwei Token in der Breite, sodass Sie den gesamten Status wiederverwenden können.
  • Die genauen Zeichenversätze jedes Tokens können leicht abgeleitet werden, indem über den Token-Stream iteriert wird und der aktuelle Versatz verfolgt wird. Sobald Sie die genauen Zeichenversätze haben, ist es einfach, den Text bei Bedarf zu extrahieren.

Wenn Sie sich nicht für eines dieser Szenarien interessieren, kann ein Token als eine Art und ein Offset dargestellt werden, anstatt als eine Art und eine Breite.

Aber das Wichtigste dabei ist: Programmieren ist die Kunst, nützliche Abstraktionen zu machen . Sie manipulieren Token, machen also eine nützliche Abstraktion über Token, und dann können Sie selbst entscheiden, welche Implementierungsdetails dahinterstehen.

Eric Lippert
quelle
3

Im Allgemeinen geben Sie eine kleine Struktur mit einer Zahl zurück, die das Token (oder den Enum-Wert zur Vereinfachung der Verwendung) und einen optionalen Wert (Zeichenfolge oder möglicherweise generischer Wert / Vorlagenwert) angibt. Ein anderer Ansatz wäre, einen abgeleiteten Typ für Elemente zurückzugeben, die zusätzliche Daten enthalten müssen. Beide sind leicht unangenehm, aber gut genug, um ein praktisches Problem zu lösen.

Telastyn
quelle
Was meinst du mit milde widerlich ? Sind sie ineffiziente Methoden zum Abrufen von Zeichenfolgenwerten?
Christian Dean
@ Mr.Python - sie werden vor der Verwendung in Code zu vielen Überprüfungen führen, was ineffizient ist, aber mehr macht den Code ein wenig komplexer / zerbrechlicher.
Telastyn
Ich habe eine ähnliche Frage beim Entwerfen eines Lexers in C ++. Ich könnte ein Token *oder einfach ein Tokenoder ein zurückgeben, TokenPtrdas ein gemeinsamer Zeiger der TokenKlasse ist. Ich sehe aber auch, dass einige Lexer nur einen TokenType zurückgeben und die Zeichenfolge oder den Zahlenwert in anderen globalen oder statischen Variablen speichern. Eine andere Frage ist, wie wir die Standortinformationen speichern können. Benötige ich eine Token-Struktur mit den Feldern TokenType, String und Location? Vielen Dank.
Ollydbg23
@ ollydbg23 - all diese Dinge können funktionieren. Ich würde eine Struktur verwenden. Und für nicht lernende Sprachen verwenden Sie sowieso einen Parser-Generator.
Telastyn
@Telastyn danke für die Antwort. Du meinst, eine Token-Struktur könnte so etwas wie sein struct Token {TokenType id; std::string lexeme; int line; int column;}, oder? Für eine öffentliche Funktion von Lexer wie PeekToken()könnte die Funktion ein Token *oder zurückgeben TokenPtr. Ich denke es für eine Weile, wenn die Funktion nur den TokenType zurückgibt, wie versucht der Parser, die anderen Informationen über das Token zu erhalten? Daher wird ein Zeiger wie ein Datentyp für die Rückgabe von einer solchen Funktion bevorzugt. Irgendwelche Kommentare zu meiner Idee? Danke
ollydbg23