@book{Ljunglöf-Peter2002-10783,
title = {Pure Functional Parsing - an advanced tutorial},
abstract = {Parsing is the problem of deciding whether a sequence of tokens is recognized
by a given grammar, and in that case returning the grammatical structure of
the sequence.
This thesis investigates di erent aspects of the parsing problem from the viewpoint
of a functional programmer. It is conceptually divided into two parts,
discussing the parsing problem from di erent perspectives; rst as a comprehensive
survey of possible implementations of combinator parsers; and second
as pure functional implementations of standard context-free parsing algorithms.
The rst part of the thesis is a survey of the possible implementations of combinator
parsers that have previously been suggested in the litterature, relating
their dirrefent usages. A number of previously unknown parser implementations
are also given, especially e cient for small and medium-sized natural language
applications.
The second part of the thesis de ne elegant and declarative, pure functional versions
of some standard parsing algorithms for context-free grammars. The goal
has been to implement the algorithms in a way that is close to their intuitive formulations,
not sacri cing computational e ciency. The implementations only
use simple data structures not relying on a global updateable state, thus opening
the way for nice functional implementations.
Finally the thesis implements parser combinators that can collect the grammatical
structure in the program, to be able to use any suitable parsing algorithm
and not just recursive descent. However, this requires an mildly impure extension
of the host language Haskell.},
author = {Ljunglöf, Peter},
year = {2002},
publisher = {Chalmers University of Technology},
adress = {Göteborg},
}