Functional Semantics of Parsing Actions, and Left Recursion Elimination as Continuation Passing

Add to your list(s) Download to your calendar using vCal

• Dr Hayo Thielecke (Computer Science)
• Monday 17 September 2012, 11:00-12:00
• CS 217.

If you have a question about this talk, please contact Dan Ghica.

Parsers, whether constructed by hand or automatically via a parser generator tool, typically need to compute some useful semantic in- formation in addition to the purely syntactic analysis of their input. Semantic actions may be added to parsing code by hand, or the parser generator may have its own syntax for annotating grammar rules with semantic actions. In this paper, we take a functional programming view of such actions. We use concepts from the semantics of mostly functional programming languages and adapt them to give meaning to the actions of the parser. Specifically, the semantics is inspired by the categorical semantics of lambda calculi and the use of premonoidal categories for the semantics of effects in programming languages. This framework is then applied to our leading example, the transformation of grammars to eliminate left recursion. The syntactic transformation of left-recursion elimination leads to a corresponding semantic transformation of the actions for the grammar. We prove the semantic transformation correct and relate it to continuation passing style, a widely studied transformation in lambda calculi and functional programming.

This talk is part of the Lab Lunch series.

This talk is included in these lists:

• CS 217
• Lab Lunch

Note that ex-directory lists are not shown.