Parsergenerator

Een parsergenerator, ook wel compiler compiler genoemd, is een programma dat helpt bij het implementeren van een compiler (of interpreter).

Op basis van een specificatie van een formele grammatica (vaak in BNF of EBNF) creëert een parsergenerator een complete parser voor de gespecificeerde grammatica. Daarnaast bieden veel parsergenerators ook de mogelijkheid om, behalve een parser, nog andere functionaliteit te genereren die gebruikt wordt in compilers. Denk hierbij bijvoorbeeld aan een lexer of een vertaler die een concrete syntaxisboom naar een abstracte syntaxisboom vertaald.

Eigenschappen

Hoewel de werking en de functionaliteit van parsergenerators onderling enorm kan verschillen, hebben ze allemaal een aantal eigenschappen gemeen:

Specificatie: Ze werken op basis van een specificatie van een context-vrije grammatica. Deze wordt gespecificeerd door middel van een of andere variant van de EBNF-notatie.
Parser: Ze genereren broncode voor een werkende parser voor de gespecificeerde grammatica.
Syntaxisboom: De gegenereerde parser levert de resultaten van een parse op in de vorm van een syntaxisboom.

Acties

In het algemeen zijn parsergenerators onder te verdelen in twee soorten: generators die zogenaamde acties in de specificatie toestaan en generators waarbij dat niet toegestaan is.

Acties zijn fragmenten programmacode die aan een bepaalde productieregel gekoppeld worden. Als de parser een productieregel gebruikt om een fragment van de invoer te herkennen, wordt de gespecificeerde programmacode uitgevoerd.

Als een parsergenerator acties ondersteunt is het mogelijk om extra functionaliteit (bijvoorbeeld het bouwen van een syntaxisboom, typechecking of zelfs codegeneratie) in de specificatie op te nemen.

Enkele parsergenerators

In de onderstaande tabel worden enkele van de meer bekende parsergenerators vergeleken:

Naam	Soort parser	Uitvoertaal	Acties	Aanvullende functionaliteit	Website
ANTLR	LL(*)	C, C , C sharp, Java, Python	ja, Java	lexer	antlr.org
Bison	LALR, GLR	C, C	ja, C/C	-	bison op www.gnu.org
Coco/R	LL(k)	C, C , C sharp, Java en andere	ja, divers	lexer, ondersteuning voor attribuut-evaluatie	Coco/R op ssw.uni-linz.ac.at
GOLD	LALR	C, C , C sharp, Java, Assembler en andere	nee	-	gold op www.devincook.com
Happy	LALR, GLR	Haskell	ja, Haskell	-	Happy op haskell.org
JavaCC	LL(k)	Java	ja, Java	lexer, aanvullende treebuilder	javacc.org
SableCC	LALR	Java, C, C , C sharp, OCaml, Python	nee	Lexer, CST->AST vertaler, treewalkers	sablecc.org
Yacc	LALR	C	ja, C	-	-

Zie ook