Syntaxanalyse

Syntaxanalyse, auch Parsing genannt, ist eine Phase der Compilerentwurfs. Sie prüft die syntaktische Korrektheit des von der Lexikalanalyse erzeugten Tokenstroms und konstruiert aus ihm eine Repräsentation der Programmstruktur gemäß einer formalen Grammatik. Ziel ist es, Programmquellen zu validieren und eine Struktur bereitzustellen, die weitere Phasen der Übersetzung unterstützt.

Für die Syntaxanalyse werden kontextfreie Grammatiken verwendet. Diese definieren zulässige Konstrukte der Programmiersprache und geben vor, wie Tokens zu Hierarchien (Parse-Bäume oder abstrakte Syntaxbäume) zusammengefügt werden. Der Parsedatenfluss führt typischerweise von Tokenströmen zu Parsebäumen, aus denen die Semantik später abgeleitet wird.

Es gibt top-down-Parser (z. B. rekursiv absteigend, LL(k)) und bottom-up-Parser (z. B. LR-, LALR-, SLR-Parser). Unterschied: Top-down versucht, die Eingabe von links nach rechts durch schrittweises Erzeugen von Ableitungen zu parsen; Bottom-up baut schrittweise die Ableitung von Blättern zum Startsymbol auf. Viele reale Sprachen verwenden LR-/LALR-Parser, da sie eine größere Klasse kontextfreier Grammatiken effizient handhaben können. Große Grammatikmengen erfordern GLR- oder rein heuristische Ansätze.

Das Endergebnis der Syntaxanalyse ist oft ein Parsebaum oder ein Abstrakter Syntaxbaum (AST). Der AST dient als Eingabe für die semantische Analyse, Optimierung und Codegenerierung. Fehlerberichte der Syntaxanalyse beschränken sich meist auf falsch platzierte Tokens, fehlende Klammern oder falsche Satzbausteine; moderne Parser versuchen, mit Fehlerbehandlung und Wiederherstellungsstrategien den Quelltext weiter zu analysieren.

Zur Generierung von Parsern werden Werkzeuge wie YACC/Bison, ANTLR, JavaCC oder andere eingesetzt. Die Wahl des Parsertyps hängt von der Grammatik, Leistungsanforderungen und Fehlerbehandlung ab.