A Verifiable, Executable SLR Parser

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

• Aditi Barthwal (The Australian National University)
• Thursday 19 March 2009, 12:30-13:30
• Computer Laboratory, William Gates Building, Room SS03.

If you have a question about this talk, please contact Thomas Tuerk.

This talk is based on one I will be presenting at the ESOP conference. In this talk, I will describe the mechanisation of an SLR parser produced by a parser generator. I will present the main properties proved about the parser, in particular, soundness: if the parser results in a parse tree on a given input, then the parse tree is valid with respect to the grammar, and the leaves of the parse tree match the input; completeness: if the input is in the language of the grammar then the parser constructs the correct parse tree for the input with respect to the grammar; and non-ambiguity: grammars successfully converted to SLR automata are unambiguous. We will also briefly have a look at the complexity introduced when providing executable versions of the algorithms involved.

This talk is part of the Computer Laboratory Automated Reasoning Group Lunches series.

This talk is included in these lists:

• All Talks (aka the CURE list)
• Cambridge talks
• Computer Laboratory Automated Reasoning Group Lunches
• Computer Laboratory, William Gates Building, Room SS03
• Department of Computer Science and Technology talks and seminars
• Interested Talks
• School of Technology
• Trust & Technology Initiative - interesting events
• bld31
• yk373's list

Note that ex-directory lists are not shown.