ParsingVerfahren

ParsingVerfahren bezeichnet in der Informatik die Methoden zur syntaktischen Analyse von Tokenfolgen gemäß einer formalen Grammatik, üblicherweise einer kontextfreien Grammatik. Ziel ist zu prüfen, ob die Eingabe zur Grammatik gehört, und Strukturinformationen in Form eines Parsebaums oder eines abstrakten Syntaxbaums zu erzeugen, der anschließend semantisch ausgewertet werden kann.

Man unterscheidet grob zwei Haupttypen: top-down und bottom-up. Beim top-down Parsing (zum Beispiel LL-Verfahren) wird von der Startregel aus schrittweise die Eingabe aufgebaut; typisch sind LL(1) beziehungsweise rekursiv-abstiegsparsing. Diese Verfahren sind oft einfach zu implementieren, stoßen aber bei linken Rekursionen oder bestimmten Grammatikstrukturen an Grenzen.

Bottom-up Parsing (LR-Verfahren) arbeitet von der Eingabe rückwärts und baut den Parsebaum durch Reduktionen auf. Wichtige Varianten sind LR(1), SLR und LALR, die in der Praxis die meisten Programmiersprachen zuverlässig parsen. Bottom-up-Parser verwenden typischerweise einen Stack und eine Parse-Tabelle und liefern effiziente, deterministische Analyse mit linearer Laufzeit.

Es gibt außerdem Chart- bzw. Generalkennlinien-Verfahren wie der Earley-Parser, der jedes kontextfreie Grammatiktyp unterstützen kann und insbesondere bei mehrdeutigen oder komplexen Grammatiken flexibel ist. CYK ist ein dynamischer Programmieransatz, der in der Chomsky-Normalform arbeitet und ebenfalls kontextfreie Grammatiken verarbeitet, jedoch in der Praxis oft weniger effizient ist.

Anwendungsgebiete sind Compilerfrontends, Parsergeneratoren (zum Beispiel für C, Java, SQL) sowie Werkzeuge zur Texterkennung, Datenextraktion und natürliche Sprachverarbeitung. Die Wahl des Parsers hängt von Grammatik, Ambiguität, Effizienzanforderungen und Wartbarkeit ab.

---