Home
Schedule
Abstract Template
Masters Attendance
Polish Parsers Step By Step

Stc
ComputingScienceColloquium



Date: September 4

Time: 11am

Room: BBL-505

----+++ Speaker:  Doaitse Swierstra

----+++ Title:  Polish Parsers, Step by Step

----+++ Abstract

  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)