Scannerloses Parsen

In der Informatik bezeichnet man als scannerloses Parsing (auch lexerloses Parsing genannt ) die Kombination aus Tokenisierung (Aufteilung eines Zeichenstroms in Wörter) und Parsing (Anordnung der Wörter zu Phrasen) in einem einzigen Schritt, anstatt den Vorgang in eine Pipeline aus Lexer und Parser aufzuteilen , die parallel ausgeführt werden . Eine Sprachgrammatik ist scannerlos, wenn sie einen einzigen Formalismus verwendet, um sowohl die lexikalische (Wortebene) als auch die Phrasenebene der Sprache auszudrücken .

Die Aufteilung der Verarbeitung in einen Lexer und anschließend einen Parser ist modularer; scannerloses Parsen wird hauptsächlich dann eingesetzt, wenn eine klare Unterscheidung zwischen Lexer und Parser nicht erforderlich oder unerwünscht ist. Beispiele hierfür sind TeX , die meisten Wiki- Grammatiken, Makefiles , einfache anwendungsspezifische Skriptsprachen und Raku .

• Es wird nur eine Metasprache benötigt.
• Nicht-reguläre lexikalische Strukturen lassen sich problemlos handhaben.
• Eine "Token-Klassifizierung" ist nicht erforderlich, wodurch die Notwendigkeit von Designanpassungen wie dem "Lexer-Hack " und reservierten Wörtern der Sprache (wie z. B. "while" in C ) entfällt.
• Grammatiken können kompositionell sein (ohne menschliches Eingreifen zusammengeführt werden können) ^[a]

• Da lexikalische Suche und syntaktische Analyse kombiniert werden, ist der resultierende Parser tendenziell komplexer und daher schwieriger zu verstehen und zu debuggen. Dasselbe gilt für die zugehörige Grammatik, falls eine Grammatik zur Generierung des Parsers verwendet wird.
• Der resultierende Parser ist in der Regel deutlich weniger effizient als eine Lexer-Parser-Pipeline, sowohl hinsichtlich der Zeit als auch des Speichers. ^{[ 1 ]}

• SGLR ist ein Parser für den modularen Syntax Definition Formalism (SDF) und ist Teil der ASF+SDF Meta-Umgebung und des Stratego/XT Programmtransformationssystems.
• JSGLR, eine reine Java-Implementierung von SGLR, basiert ebenfalls auf SDF.
• TXL unterstützt die Analyse auf Zeichenebene.
• dparser generiert ANSI-C-Code für scannerlose GLR-Parser .
• Spirit ermöglicht sowohl scannerloses als auch scannerbasiertes Parsen.
• SBP ist ein scannerloser Parser für Boolesche Grammatiken (eine Obermenge der kontextfreien Grammatiken), geschrieben in Java.
• Laja ist ein zweiphasiger, scannerloser Parsergenerator mit Unterstützung für die Abbildung der Grammatikregeln auf Objekte, geschrieben in Java.
• Die Raku-Grammatiken -Funktion der universellen Programmiersprache Raku .
• PyParsing ist ein scannerloser Parser, der in reinem Python geschrieben ist.
• META II verfügt über integrierte Token-Parser-Funktionen.
• TREE-META ist wie META II ebenfalls scannerlos und verfügt über integrierte Lexerfunktionen.
• Der CWIC -Compiler dient zum Schreiben und Implementieren von Compilern. Er verwendet Token-Regeln als Teil seiner Sprache. Die Regeln in CWIC wurden in boolesche Funktionen kompiliert, die Erfolg oder Misserfolg zurückgeben.

• ^a) Dies liegt daran, dass die Analyse auf Zeichenebene die vom Parser erkannte Sprache zu einer einzigen, auf Zeichen definierten , kontextfreien Sprache macht , im Gegensatz zu einer kontextfreien Sprache aus Zeichenkettenfolgen in regulären Sprachen . Einige lexerlose Parser verarbeiten die gesamte Klasse der kontextfreien Sprachen, die unter Komposition abgeschlossen ist.

• Visser, E. (August 1997). Scannerloses generalisiertes LR-Parsing . Niederlande: Universität Amsterdam. CiteSeerX  10.1.1.37.7828 .