Was ist der Unterschied zwischen einem Token und einem Lexem?

In Compiler Construction von Aho Ullman und Sethi wird angegeben, dass die Eingabezeichenfolge des Quellprogramms in eine Folge von Zeichen unterteilt ist, die eine logische Bedeutung haben und als Token bezeichnet werden. Lexeme sind Sequenzen, aus denen das Token besteht ist der grundlegende Unterschied?

Unter Verwendung von " Compilers Principles, Techniques & Tools, 2nd Ed. " (WorldCat) von Aho, Lam, Sethi und Ullman, AKA the Purple Dragon Book ,

Lexeme pg. 111

Ein Lexem ist eine Folge von Zeichen im Quellprogramm, die dem Muster für ein Token entspricht und vom lexikalischen Analysator als Instanz dieses Tokens identifiziert wird.

Token pg. 111

Ein Token ist ein Paar, das aus einem Token-Namen und einem optionalen Attributwert besteht. Der Token-Name ist ein abstraktes Symbol, das eine Art lexikalische Einheit darstellt, z. B. ein bestimmtes Schlüsselwort oder eine Folge von Eingabezeichen, die einen Bezeichner bezeichnen. Die Token-Namen sind die Eingabesymbole, die der Parser verarbeitet.

Muster pg. 111

Ein Muster ist eine Beschreibung der Form, die die Lexeme eines Tokens annehmen können. Im Fall eines Schlüsselworts als Token ist das Muster nur die Folge von Zeichen, die das Schlüsselwort bilden. Bei Bezeichnern und einigen anderen Token ist das Muster eine komplexere Struktur, der viele Zeichenfolgen entsprechen.

Abbildung 3.2: Beispiele für Token S.112

[Token]       [Informal Description]                  [Sample Lexemes]
if            characters i, f                         if
else          characters e, l, s, e                   else
comparison    < or > or <= or >= or == or !=          <=, !=
id            letter followed by letters and digits   pi, score, D2
number        any numeric constant                    3.14159, 0, 6.02e23
literal       anything but ", surrounded by "'s       "core dumped"

Um diese Beziehung zu einem Lexer und Parser besser zu verstehen, beginnen wir mit dem Parser und arbeiten rückwärts zur Eingabe.

Um das Entwerfen eines Parsers zu vereinfachen, arbeitet ein Parser nicht direkt mit der Eingabe, sondern nimmt eine Liste der von einem Lexer generierten Token auf. Mit Blick auf die Token - Spalte in Abbildung 3.2 sehen wir Token wie if, else, comparison, id, numberund literal; Dies sind Namen von Token. In der Regel ist ein Token bei einem Lexer / Parser eine Struktur, die nicht nur den Namen des Tokens enthält, sondern auch die Zeichen / Symbole, aus denen das Token besteht, sowie die Start- und Endposition der Zeichenfolge, aus der das Token besteht Start- und Endposition werden für die Fehlerberichterstattung, Hervorhebung usw. verwendet.

Jetzt übernimmt der Lexer die Eingabe von Zeichen / Symbolen und wandelt die eingegebenen Zeichen / Symbole nach den Regeln des Lexers in Token um. Jetzt haben Leute, die mit Lexer / Parser arbeiten, ihre eigenen Wörter für Dinge, die sie oft benutzen. Was Sie als eine Folge von Zeichen / Symbolen betrachten, aus denen ein Token besteht, nennen Menschen, die Lexer / Parser verwenden, Lexem. Wenn Sie also Lexem sehen, denken Sie einfach an eine Folge von Zeichen / Symbolen, die ein Token darstellen. Im Vergleichsbeispiel kann die Folge von Zeichen / Symbolen unterschiedliche Muster wie <oder >oder elseoder 3.14usw. sein.

Eine andere Möglichkeit, sich die Beziehung zwischen den beiden vorzustellen, besteht darin, dass ein Token eine vom Parser verwendete Programmierstruktur ist, die eine Eigenschaft namens Lexem hat, die die Zeichen / Symbole aus der Eingabe enthält. Wenn Sie sich nun die meisten Definitionen von Token im Code ansehen, sehen Sie Lexem möglicherweise nicht als eine der Eigenschaften des Tokens. Dies liegt daran, dass ein Token mit größerer Wahrscheinlichkeit die Start- und Endposition der Zeichen / Symbole enthält, die das Token und das Lexem darstellen. Die Folge von Zeichen / Symbolen kann nach Bedarf von der Start- und Endposition abgeleitet werden, da die Eingabe statisch ist.

Wenn ein Quellprogramm in den lexikalischen Analysator eingespeist wird, beginnt es damit, die Zeichen in Sequenzen von Lexemen aufzuteilen. Die Lexeme werden dann bei der Konstruktion von Token verwendet, bei denen die Lexeme in Token abgebildet werden. Eine Variable mit dem Namen myVar wird einem Token zugeordnet, das < id , "num"> angibt , wobei "num" auf die Position der Variablen in der Symboltabelle verweisen soll.

Kurz gesagt:

• Lexeme sind die Wörter, die aus dem Zeicheneingabestream abgeleitet werden.
• Token sind Lexeme, die einem Token-Namen und einem Attributwert zugeordnet sind.

Ein Beispiel beinhaltet:
x = a + b * 2,
was die Lexeme ergibt: {x, =, a, +, b, *, 2}
Mit entsprechenden Token: {< id , 0>, <=>, < id , 1 >, <+>, < id , 2>, <*>, < id , 3>}

a) Token sind symbolische Namen für die Entitäten, aus denen der Programmtext besteht. zB if für das Schlüsselwort if und id für einen Bezeichner. Diese bilden die Ausgabe des lexikalischen Analysators. 5

(b) Ein Muster ist eine Regel, die angibt, wann eine Folge von Zeichen aus der Eingabe ein Token darstellt; zB die Folge i, f für das Token if und eine beliebige Folge von alphanumerischen Zeichen, die mit einem Buchstaben für die Token-ID beginnt.

(c) Ein Lexem ist eine Folge von Zeichen aus der Eingabe, die einem Muster entsprechen (und daher eine Instanz eines Tokens darstellen); Beispiel: Wenn if mit dem Muster für if übereinstimmt und foo123bar mit dem Muster für id übereinstimmt.

LEXEME - Folge von Zeichen, die mit PATTERN übereinstimmen und den TOKEN bilden

MUSTER - Der Regelsatz, der ein TOKEN definiert

TOKEN - Die aussagekräftige Sammlung von Zeichen über den Zeichensatz der Programmiersprache, z. B .: ID, Konstante, Schlüsselwörter, Operatoren, Interpunktion, Literalzeichenfolge

Lexem - Ein Lexem ist eine Folge von Zeichen im Quellprogramm, die dem Muster für ein Token entspricht und vom lexikalischen Analysator als Instanz dieses Tokens identifiziert wird.

Token - Token ist ein Paar, das aus einem Token-Namen und einem optionalen Token-Wert besteht. Der Token-Name ist eine Kategorie einer lexikalischen Einheit. Übliche Token-Namen sind

• Bezeichner: Namen, die der Programmierer auswählt
• Schlüsselwörter: Namen bereits in der Programmiersprache
• Trennzeichen (auch als Interpunktionszeichen bezeichnet): Interpunktionszeichen und Trennzeichenpaare
• Operatoren: Symbole, die mit Argumenten arbeiten und Ergebnisse liefern
• Literale: numerische, logische, textuelle, Referenzliterale

Betrachten Sie diesen Ausdruck in der Programmiersprache C:

Summe = 3 + 2;

Tokenisiert und dargestellt durch die folgende Tabelle:

 Lexeme        Token category
------------------------------
sum      |    Identifier
 =       |    Assignment operator
 3       |    Integer literal
 +       |    Addition operator
 2       |    Integer literal
 ;       |    End of statement

Lassen Sie uns die Funktionsweise eines lexikalischen Analysators (auch Scanner genannt) sehen.

Nehmen wir einen Beispielausdruck:

INPUT : cout << 3+2+3;

FORMATTING PERFORMED BY SCANNER :  {cout}|space|{<<}|space|{3}{+}{2}{+}{3}{;} 

nicht die tatsächliche Ausgabe.

Der Scanner sucht einfach wiederholt nach einem Lexem im Quellprogrammtext, bis der Eingang erschöpft ist

Lexem ist eine Teilzeichenfolge der Eingabe, die eine gültige Folge von Terminals bildet, die in der Grammatik vorhanden sind. Jedes Lexem folgt einem Muster, das am Ende erklärt wird (der Teil, den der Leser zuletzt überspringen darf).

(Wichtige Regel ist, nach dem längstmöglichen Präfix zu suchen, das eine gültige Folge von Terminals bildet, bis das nächste Leerzeichen angetroffen wird ... siehe unten)

LEXEME:

1. cout
2. <<

(Obwohl "<" auch eine gültige Terminalzeichenfolge ist, muss die oben genannte Regel das Muster für das Lexem "<<" auswählen, um ein vom Scanner zurückgegebenes Token zu generieren.)

3. 3
4. +
5. 2
6. ;;

Token: Token werden jedes Mal einzeln zurückgegeben (vom Scanner, wenn dies vom Parser angefordert wird), wenn der Scanner ein (gültiges) Lexem findet. Der Scanner erstellt, falls noch nicht vorhanden, einen Symboltabelleneintrag (mit Attributen: hauptsächlich Token-Kategorie und wenige andere) , wenn er ein Lexem findet, um dessen Token zu generieren

'#' bezeichnet einen Symboltabelleneintrag. Ich habe zum besseren Verständnis auf die Lexemnummer in der obigen Liste hingewiesen, aber es sollte technisch gesehen der tatsächliche Index der Aufzeichnung in der Symboltabelle sein.

Die folgenden Token werden vom Scanner in der angegebenen Reihenfolge für das obige Beispiel an den Parser zurückgegeben.

1. <Kennung, # 1>

2. <Operator, # 2>

3. <Literal, # 3>

4. <Operator, # 4>

5. <Literal, # 5>

6. <Operator, # 4>

7. <Literal, # 3>

8. <Interpunktionszeichen, # 6>

Wie Sie den Unterschied sehen können, ist ein Token ein Paar im Gegensatz zu Lexem, das eine Teilzeichenfolge der Eingabe ist.

Und das erste Element des Paares ist die Token-Klasse / Kategorie

Token-Klassen sind unten aufgeführt:

Und noch etwas: Der Scanner erkennt Leerzeichen, ignoriert sie und bildet überhaupt kein Token für ein Leerzeichen. Nicht alle Trennzeichen sind Leerzeichen. Ein Leerzeichen ist eine Form von Trennzeichen, die von Scannern für diesen Zweck verwendet wird. Tabulatoren, Zeilenumbrüche, Leerzeichen und Escapezeichen in der Eingabe werden zusammen als Leerzeichen-Trennzeichen bezeichnet. Nur wenige andere Trennzeichen sind ';' ',' ':' usw., die allgemein als Lexeme anerkannt sind, die Token bilden.

Die Gesamtzahl der zurückgegebenen Token beträgt hier 8, es werden jedoch nur 6 Symboltabelleneinträge für Lexeme vorgenommen. Lexeme sind auch insgesamt 8 (siehe Definition des Lexems)

--- Sie können diesen Teil überspringen

A ***pattern*** is a rule ( say, a regular expression ) that is used to check if a string-of-terminals is valid or not.

If a substring of input composed only of grammar terminals is following the rule specified by any of the listed patterns , it is validated as a lexeme and selected pattern will identify the category of lexeme, else a lexical error is reported due to either (i) not following any of the rules or (ii) input consists of a bad terminal-character not present in grammar itself.

for example :

1. No Pattern Exists : In C++ , "99Id_Var" is grammar-supported string-of-terminals but is not recognised by any of patterns hence lexical error is reported .

2. Bad Input Character : $,@,unicode characters may not be supported as a valid character in few programming languages.`

Lexem - Ein Lexem ist eine Zeichenfolge, die die niedrigste syntaktische Einheit in der Programmiersprache darstellt.

Token - Das Token ist eine syntaktische Kategorie, die eine Klasse von Lexemen bildet. Dies bedeutet, zu welcher Klasse das Lexem gehört, ob es sich um ein Schlüsselwort oder einen Bezeichner oder etwas anderes handelt. Eine der Hauptaufgaben des lexikalischen Analysators besteht darin, ein Paar Lexeme und Token zu erstellen, dh alle Zeichen zu sammeln.

Nehmen wir ein Beispiel: -

if (y <= t)

y = y-3;

Lexeme Token

wenn KEYWORD

(LINKE PARENTHESE

y IDENTIFIER

<= VERGLEICH

t IDENTIFIER

) RECHTE PARENTHESE

y IDENTIFIER

= ASSGNMENT

y IDENTIFIER

_ ARITHMATIK

3 INTEGER

;;                                    SEMIKOLON

Beziehung zwischen Lexem und Token

Token: Die Art für (Schlüsselwörter, Bezeichner, Satzzeichen, Operatoren mit mehreren Zeichen) ist einfach ein Token.

Muster: Eine Regel für die Bildung von Token aus Eingabezeichen.

Lexem: Es ist eine Folge von Zeichen im QUELLENPROGRAMM, die mit einem Muster für einen Token übereinstimmen. Grundsätzlich ist es ein Element von Token.

Token: Token ist eine Folge von Zeichen, die als einzelne logische Einheit behandelt werden können. Typische Token sind:
1) Bezeichner
2) Schlüsselwörter
3) Operatoren
4) spezielle Symbole
5) Konstanten

Muster: Eine Reihe von Zeichenfolgen in der Eingabe, für die dasselbe Token als Ausgabe erzeugt wird. Dieser Satz von Zeichenfolgen wird durch eine Regel beschrieben, die als dem Token zugeordnetes Muster bezeichnet wird.
Lexem: Ein Lexem ist eine Folge von Zeichen im Quellprogramm, die mit dem Muster für ein Token übereinstimmt.

Lexem Lexeme sollen eine Folge von Zeichen (alphanumerisch) in einem Token sein.

Token Ein Token ist eine Folge von Zeichen, die als einzelne logische Entität identifiziert werden können. Typischerweise sind Token Schlüsselwörter, Bezeichner, Konstanten, Zeichenfolgen, Interpunktionssymbole und Operatoren. Zahlen.

Muster Eine Reihe von Zeichenfolgen, die durch eine Regel namens Muster beschrieben werden. Ein Muster erklärt, was ein Token sein kann, und diese Muster werden durch reguläre Ausdrücke definiert, die dem Token zugeordnet sind.

CS-Forscher wie die aus der Mathematik kreieren gern "neue" Begriffe. Die obigen Antworten sind alle nett, aber anscheinend gibt es meiner Meinung nach keine so große Notwendigkeit, Token und Lexeme zu unterscheiden. Sie sind wie zwei Möglichkeiten, dasselbe darzustellen. Ein Lexem ist konkret - hier eine Reihe von Zeichen; Ein Token hingegen ist abstrakt - bezieht sich normalerweise auf den Typ eines Lexems zusammen mit seinem semantischen Wert, wenn dies sinnvoll ist. Nur meine zwei Cent.

Lexical Analyzer verwendet eine Folge von Zeichen, um ein Lexem zu identifizieren, das dem regulären Ausdruck entspricht, und es weiter in Token zu kategorisieren. Somit ist ein Lexem eine übereinstimmende Zeichenfolge und ein Token-Name ist die Kategorie dieses Lexems.

Betrachten Sie beispielsweise den folgenden regulären Ausdruck für einen Bezeichner mit der Eingabe "int foo, bar;"

Buchstabe (Buchstabe | Ziffer | _) *

Hier foound barÜbereinstimmung mit dem regulären Ausdruck sind somit beide Lexeme, werden jedoch als ein Token, IDdh als Bezeichner, kategorisiert .

Beachten Sie auch, dass die nächste Phase, dh der Syntaxanalysator, nicht über Lexem, sondern über ein Token Bescheid wissen muss.

Lexem ist im Grunde die Einheit eines Tokens und es ist im Grunde eine Folge von Zeichen, die mit dem Token übereinstimmt und dabei hilft, den Quellcode in Token zu zerlegen.

Zum Beispiel: Wenn die Quelle x=b, dann würden die Lexeme sein x, =, bund die Token wären <id, 0>, <=>, <id, 1>.