Ein Parser (englisch to parse = analysieren) 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 Parse-Baum 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 auch verschiedene Parse-Verfahren, unter anderem:
- Recursive-Descent-Parser
- Top-Down-Parser
- Bottom-Up-Parser
- Chart-Parser
- Left-Corner-Parser
- LR-Parser
- SLR-Parser
- LALR-Parser
- LL-Parser
Alle diese Verfahren basieren auf einem Kellerautomaten.
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.