Parser generator
In compiler construction , a parser generator is a computer program that generates a parser based on a specification .
Basics
A parser generator generates subroutines for (programming) languages that enable their grammatical analysis and transformation. The generated subroutines are called parsers . As input, a parser generator receives the syntax of the language for which it is to generate a parser. This language can be e.g. B. be a programming language. The specification of the parser is usually done in Backus-Naur-Form (BNF) or in Extended Backus-Naur-Form (EBNF).
Many parser generators require a scanner for symbol recognition. This scanner is usually generated by an integrated or external scanner generator.
The representation generated by the parser then forms the basis for a compiler or interpreter .
The effort required to create a powerful and correct compiler is significantly reduced by using parser generators.
Algorithms
Efficient parser generators are limited to generating parsers for deterministic context-free grammars . The following algorithms are used by common parser generators:
- LL (k) parsing ( JavaCC , Coco / R )
- LL (*) - Parsing ( ANTLR )
- LALR (1) parsing ( SableCC , yacc , GNU Bison , Lemon)
There are also other paradigms (e.g. GLR parsers ) that cover a larger class of grammars, but are less common.