Parser
Ein Parser (englisch to parse = analysieren bzw. von lateinisch pars = Teil; weshalb Parser im Deutschen gelegentlich auch als Zerteiler bezeichnet werden) ist ein Programm, das entscheidet, ob eine Eingabe zur Sprache einer bestimmten Grammatik gehört. Er benutzt dabei in der Regel einen separaten Scanner (auch Lexer genannt), um eine zeichenweise vorliegende Eingabe vorher in Token (zusammengehörende Einheiten, z. B. Schlüsselwörter, Bezeichner usw.) zu konvertieren. Diese Token dienen dann als atomare Eingabezeichen des Parsers.
Parser sind Programme, die eine Grammatik akzeptieren - das heißt, sie sind konkrete Implementierungen von abstrakten Automaten. Für die meisten in der Praxis verwendeten Parser gilt dabei, dass sie als Kellerautomat realisiert sind. Der Scanner dagegen ist meist ein Endlicher Automat, da die Zerlegung in Tokens einer regulären Grammatik folgt.
Während des Parsens erfolgt eine syntaktische Überprüfung der Eingangsdaten. Bei der Überprüfung wird in der Regel aus den Daten ein Ableitungsbaum (in Anlehnung an das Englische gelegentlich auch als Parse-Baum bezeichnet) aufgebaut, um die Daten anschließend weiterverarbeiten zu können (z. B. semantische Analyse, Codegenerierung in einem Compiler oder Ausführung durch einen Interpreter).
Man unterscheidet verschiedene Parse-Verfahren. Dabei wird nach genereller Vorgehensweise (top-down oder bottom-up), spezifischer Vorgehensweise (LL, LR, SLR, LALR, Left-Corner, ...) und Implementierungstechnik (recursive-descent, recursive-ascent, tabellengesteuert) unterschieden. Weiter wird auch nach Grammatikart unterschieden. Hier ein paar auf kontextfreien Grammatiken basierende Verfahren:
- Top-Down-Parser
- LL-Parser
- Recursive-Descent-Parser
- Bottom-Up-Parser
- LR-Parser
- SLR-Parser
- LALR-Parser
- Chart-Parser
- Left-Corner-Parser
Es gibt auch Parse-Verfahren die auf anderen Grammatiken basieren:
- Packrat-Parser (Parsing Expression Grammars)
Das Parsen wohldefinierter künstlicher Sprachen (siehe formale Sprachen, Programmiersprachen) ist weniger komplex als das Parsen frei gewachsener natürlicher Sprachen wie Englisch oder Deutsch, die durch eine Vielzahl von Mehrdeutigkeiten, Irregularitäten und Inkonsistenzen geprägt sind. Siehe hierzu auch Computerlinguistik.
Hinweis: Der Begriff parsen sollte nicht mit dem Begriff kompilieren verwechselt werden. Letzteres erzeugt einen Zielcode aufgrund eines Quellcodes, dabei wird unter anderem auch geparst, darüberhinaus finden aber weitere Aktionen statt.
Siehe auch: Compilerbau, Parser-Generator, Compiler-Compiler.
Kategorie:Programmierung
Kategorie:Compilerbau