Date: September 4
Speaker: Doaitse Swierstra
Title: Polish Parsers, Step by Step
We present the derivation of a space efficient parser
combinator library: the constructed parsers do not keep
unnecessary references to the input, produce online results
and efficiently handle ambiguous grammars. The underlying
techniques can be applied in many contexts where traditionally
backtracking is used.
We present two data types, one for keeping track of the progress
of the search process, and one for representing the final result
in a linear way. Once these data types are combined into a single
type, we can perform a breadth-first search, while returning parts
of the result as early as possible.
(Based on joint work with John Hughes, Chalmers Uni, Sweden)