Lexikalische und syntaktische Analyse

Lexikalische und syntaktische Analyse bilden das Frontend eines Compilers, indem sie den Quelltext in Tokens zerlegen und seine grammatikalische Struktur als Parse- oder Syntaxbaum erkennen.

Definition

Die lexikalische Analyse ist die Phase, die Eingabezeichen zu Tokens gruppiert, und die syntaktische Analyse (Parsing) ist die Phase, die bestimmt, ob und wie diese Tokens gemäß einer Grammatik ein gültiges Programm bilden, und dabei einen Syntaxbaum erzeugt.

Scope

Dieses Thema behandelt die lexikalische Analyse, die Zeichenströme mithilfe regulärer Sprachen und endlicher Automaten in Tokens umwandelt, sowie die syntaktische Analyse (Parsing), die die Phrasenstruktur eines Programms anhand einer kontextfreien Grammatik erkennt. Es umfasst Top-Down- (LL) und Bottom-Up- (LR) Parsing, Parser-Generatoren, Ambiguität und Fehlerbehandlung sowie die Konstruktion abstrakter Syntaxbäume.

Core questions

• Wie werden reguläre und kontextfreie Sprachen zur Beschreibung der Programmstruktur verwendet?
• Welche Kompromisse gibt es zwischen LL- und LR-Parsing?
• Wie werden Ambiguität und Parsing-Fehler erkannt und behandelt?
• Wie wird ein abstrakter Syntaxbaum aus einem Token-Strom erstellt?

Key theories

LR-Parsing

Knuth führte das LR-Parsing ein, eine Bottom-Up-Technik, die die breite Klasse der LR-Grammatiken in linearer Zeit deterministisch parst und die Grundlage vieler Parser-Generatoren bildet.

Allgemeines kontextfreies Parsing

Earleys Algorithmus parst beliebige kontextfreie Grammatiken, einschließlich ambiger, und bietet eine allgemeine Methode, wenn eingeschränkte deterministische Parser unzureichend sind.

Reguläre und kontextfreie Grundlagen des Frontends

Das Dragon Book systematisiert die Verwendung regulärer Ausdrücke und endlicher Automaten für das Scannen und kontextfreier Grammatiken für das Parsing, einschließlich der Standard-LL- und LR-Konstruktionsalgorithmen.

Clinical relevance

Lexing und Parsing sind nicht nur für Compiler, sondern auch für Interpreter, Linter, Formatierer, IDEs und Datenformatprozessoren von grundlegender Bedeutung. Robustes Parsing mit guter Fehlerbehandlung ist für die Entwicklererfahrung jeder Sprachwerkzeugkette unerlässlich.

History

Chomskys Hierarchie der formalen Sprachen in den späten 1950er Jahren lieferte die Theorie der regulären und kontextfreien Sprachen. Knuth formalisierte das LR-Parsing 1965, und Earley entwickelte 1970 einen allgemeinen kontextfreien Algorithmus. Parser-Generatoren wie yacc machten das LR-Parsing praktikabel, während spätere Arbeiten Parsing Expression Grammars und kombinatorbasierte Parser untersuchten.

Debates

Generierte versus handgeschriebene Parser

Praktiker diskutieren den Einsatz von Parser-Generatoren aus formalen Grammatiken, die prägnant und verifizierbar sind, gegenüber handgeschriebenen rekursiven Abstiegsparsern, die oft bessere Fehlermeldungen und mehr Kontrolle auf Kosten von mehr Code bieten.

Key figures

• Donald Knuth
• Jay Earley
• Alfred Aho
• Noam Chomsky

Seminal works

• knuth1965
• earley1970
• aho2006

Frequently asked questions

Was ist der Unterschied zwischen einem Lexer und einem Parser?

Ein Lexer gruppiert Rohzeichen zu Tokens wie Bezeichnern und Operatoren, während ein Parser diese Tokens gemäß der Grammatik der Sprache zu einem hierarchischen Syntaxbaum anordnet.

Was ist der Unterschied zwischen LL- und LR-Parsing?

LL-Parser arbeiten Top-Down und prognostizieren Produktionen aus dem Eingabepräfix, während LR-Parser Bottom-Up arbeiten und erkannte Teilzeichenketten reduzieren; LR verarbeitet eine streng größere Klasse von Grammatiken, ist aber komplexer zu konstruieren.