Compiler-compiler

In a compiler parser is a computer program that generated based on a specification of a parser.

Basics

A parser generator generates subroutines for (programming ) languages ​​which facilitate its grammatical analysis and transformation. The subroutines are called generated parser. As input, a parser generator receives the syntax of the language for which it is to produce a parser. This language can be eg a programming language. The specification of the parser is generally in Backus -Naur Form (BNF ) or Extended in Backus -Naur Form ( EBNF ).

Many parser generators need 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 to produce an efficient and correct compiler is significantly reduced by parser generators.

Algorithms

Efficient parser generators restrict itself to generate 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 )

In addition, there are other paradigms (e.g. GLR parser ) which cover a larger class of grammars, but are less common.

Compiler construction Backus–Naur Form Interpreter (computing) Context-free grammar LL-Parser Coco/R
634675
de