Verified, Executable Parsing

Select |




Print


Barthwal, Aditi; Norrish, Michael

Barthwal, Aditi; Norrish, Michael


2009-03-28


Conference Material


ESOP


York


160-174


We describe the mechanisation of SLR parsing, covering background properties of context-free languages and grammars, as well as the construction of an SLR automaton. Among the various properties proved about the parser we show, 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 also develop versions of the algorithms that are executable by automatic translation from HOL to SML. These alternative versions of the algorithms require some interesting termination proofs.


Springer


mechanisation, parsing, slr


http://esop09.pps.jussieu.fr/


nicta:1606


Barthwal, Aditi; Norrish, Michael. Verified, Executable Parsing. In: Giuseppe Castagna Editor, editor/s. ESOP; York. Springer; 2009-03-28. 160-174.



Loading citation data...

Citation counts
(Requires subscription to view)