Bas van Gijzel - Comparing Parser Construction Techniques

author:Bas van Gijzel
title:Comparing Parser Construction Techniques
keywords:parser generators, parser combinators, novel parsing technique
graduation date:June 2009


Today most recursive descent parsers are generated by providing grammars and generating parsers according to these grammars. An alternative approach to constructing parsers consists of parser combinators, which do not need a separate step to generate the parser, and furthermore claim to be clear and simple in use. Despite these claimed advantages, parser combinators have not been widely adopted and are rarely actually compared to parser generators.

This paper introduces two of the contemporary implementations, ANTLR and Parsec, along with a novel implementation, called Tinadic Parsing, based on the combination of the techniques used in parser generators and parser combinators. The three implementations are compared and evaluated by the implementation of increasingly extended examples.