University of Birmingham > Talks@bham > Lab Lunch > Functional Semantics of Parsing Actions, and Left Recursion Elimination as Continuation Passing

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

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

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.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.


Talks@bham, University of Birmingham. Contact Us | Help and Documentation | Privacy and Publicity.
talks@bham is based on from the University of Cambridge.