In welchem ​​Prozess tritt ein Syntaxfehler auf? (Tokenisieren oder Parsen)

23

Ich versuche, Zusammenstellung und Interpretation Schritt für Schritt zu verstehen und ein Gesamtbild zu finden. Ich bin also auf eine Frage gekommen, als ich diesen Artikel gelesen habe: http://www.cs.man.ac.uk/~pjj/farrell/comp3.html

Es sagt :

Die nächste Stufe des Compilers heißt Parser. Dieser Teil des Compilers versteht die Grammatik der Sprache. Es ist dafür verantwortlich, Syntaxfehler zu identifizieren und ein fehlerfreies Programm in interne Datenstrukturen zu übersetzen, die in einer anderen Sprache interpretiert oder ausgeschrieben werden können.

Ich konnte jedoch nicht herausfinden, wie Tokenizer den angegebenen Stream, der den Syntaxfehler enthält, ordnungsgemäß token kann.

Es sollte dort hängen bleiben oder dem Parser falsche Informationen geben. Ich meine, ist das Tokenizing nicht auch eine Art Übersetzer?

So, wie es nur die lexikalisch beschädigten Codezeilen beim Tokenisieren überwindet.

Ein Beispiel für ein Token finden Sie oben im Link unter der Überschrift " The Tokenizer" .

Soweit ich weiß, scheint die Form des Tokens so zu sein, dass auch der Code-Token beschädigt wird, wenn etwas nicht stimmt.

Könnten Sie bitte mein Missverständnis klären?

compiler parsing interpreters FZE
quelle

Antworten:

32

Ein Tokenizer ist nur eine Parser-Optimierung. Es ist durchaus möglich, einen Parser ohne Tokenizer zu implementieren.

Ein Tokenizer (oder Lexer oder Scanner) zerlegt die Eingabe in eine Liste von Token. Einige Teile der Zeichenfolge (Kommentare, Leerzeichen) werden normalerweise ignoriert. Jedes Token hat einen Typ (die Bedeutung dieser Zeichenfolge in der Sprache) und einen Wert (die Zeichenfolge, aus der das Token besteht). Zum Beispiel das PHP-Quelltext-Snippet

$a + $b

könnte durch die Token dargestellt werden

Variable('$a'),
Plus('+'),
Variable('$b')

Der Tokenizer prüft nicht, ob in diesem Zusammenhang ein Token möglich ist. Zum Beispiel die Eingabe

$a $b + +

würde gerne den Token Stream produzieren

Variable('$a'),
Variable('$b'),
Plus('+'),
Plus('+')

Wenn der Parser diese Token dann verbraucht, stellt er fest, dass zwei Variablen nicht aufeinander folgen können und auch nicht zwei Infix-Operatoren. (Beachten Sie, dass andere Sprachen andere Syntaxen haben, wenn ein solcher Token-Stream legal ist, aber nicht in PHP).

Ein Parser kann in der Tokenizer-Phase immer noch fehlschlagen. Zum Beispiel könnte es ein unzulässiges Zeichen geben:

$a × ½ — 3

Ein PHP-Tokenizer könnte diese Eingabe nicht an seine Regeln anpassen und würde einen Fehler erzeugen, bevor das Haupt-Parsing beginnt.

Genauer gesagt werden Tokenizer verwendet, wenn jedes Token als reguläre Sprache beschrieben werden kann . Die Token können dann äußerst effizient angepasst und möglicherweise als DFA implementiert werden. Im Gegensatz dazu ist die Hauptgrammatik normalerweise kontextfrei und erfordert einen komplizierteren, weniger performanten Parsing-Algorithmus wie LALR.

amon
quelle
Wir könnten also annehmen, dass Tokenizer ein Teil des Parsers ist und der Syntaxfehler je nach Syntaxfehlerform entweder im Token-Schritt oder im Parsing-Schritt auftreten kann. Danke für die Klarstellung.
FZE
4
@FZE: Sie könnten so denken, aber es ist irreführend. Lexing ist nicht "nur eine Parser-Optimierung". Vielmehr ordnet Lexing eine physische Darstellung (eine Folge von Zeichen) einer logischen Darstellung (den durch diese Zeichen dargestellten Token) zu. Dadurch wird der Parser von Kleinigkeiten isoliert, z. B. davon, wie das Ende einer Zeile dargestellt wird oder ob Sie sich für die Darstellung eines logischen und als andoder entscheiden&& oder etwas anderes. Es ist (meistens) getrennt und unterscheidet sich vom Parsen. Eine Optimierung (falls vorhanden) ist eine fast zufällige Nebenwirkung.
Jerry Coffin
@ JerryCoffin danke für die weitere Erklärung es macht jetzt mehr Sinn.
FZE
2
@ JerryCoffin, amon ist richtig, dass der Unterschied nicht grundlegend ist. Sie können eine zusammenhängende BNF-Grammatik erstellen, die sowohl die Teile "Lexer" als auch "Parser" abdeckt. Wir kategorisieren die Regeln normalerweise in eine niedrige Ebene (z. B. Zahl, Additionsoperator) und eine hohe Ebene (Summation), aber die Grammatik selbst macht keine solche Unterscheidung.
Paul Draper
1
@PaulDraper Ich bin mir nicht sicher, ob die Trennung einer regulären Sprache als erste Phase die richtige Wahl ist. Beispielsweise sind möglicherweise übereinstimmende Paare (nicht regulär) erforderlich, um Zeichenfolgenliterale in einigen Sprachen zu beschreiben. Es ist jedoch sinnvoll, sie in der ersten Phase zu behandeln. Das Vermeiden / Minimieren der Rückverfolgung scheint eine bessere Richtlinie zu sein.
CodesInChaos
16

Sie würden in der Regel die meisten Syntaxfehler von dem Parser, nicht die Lexer kommen erwarten.

Der Lexer würde einen Fehler erzeugen, wenn (und meistens nur, wenn) die Eingabe etwas enthält, das nicht als Token gekennzeichnet werden kann. In vielen Sprachen kann jedoch fast jede Zeichenfolge in Token verwandelt werden, sodass Fehler hier eher ungewöhnlich sind.

Der Parser generiert einen Fehler, wenn die Eingabe gültige Token enthält, diese Token jedoch nicht angeordnet sind, sodass sie gültige Anweisungen / Ausdrücke in der Zielsprache bilden. Dies ist in der Regel viel häufiger.

Jerry Sarg
quelle
11

Tokenizer teilt den Zeichenstrom nur in Token auf. Vom Tokenizer POV ist dies vollständig gültig:

1 * * 1

und übersetzt in etwas wie: ["1", MULTIPLY, MULTIPLY, "1"] Nur der Parser kann solche Ausdrücke ablehnen - er weiß, dass der Multiplikationsoperator keinem anderen Multiplikationsoperator folgen kann. Zum Beispiel in JavaScript erzeugt dies:

Uncaught SyntaxError: Unexpected token *(…)

Es gibt Fehler, die vom Tokenizer erkannt werden können. Zum Beispiel unvollendete String-Literale: "abcoder ungültige Zahlen:0x0abcdefg . Sie können jedoch weiterhin als Syntaxfehler gemeldet werden:

Uncaught SyntaxError: Unexpected token ILLEGAL

Beachten Sie jedoch, dass das Token nicht erkannt wurde und als gemeldet wird ILLEGAL.

Banthar
quelle