School of Computing

Parsing in ISBES

E.A. Boiten

In D. Bjorner, M. Broy, and I.V. Pottosin, editors, Formal Methods in Programming and Their Applications, volume 735 of Lecture Notes in Computer Science, pages 182-196, Berlin, June 1993. Springer-Verlag.

Abstract

It is shown how parsing can be described as a problem in the class ISBES, Intersections of Sets and Bags of Extended Substructures, defined in an earlier paper, by viewing parsing as a generalization of pattern matching in several ways. The resulting description is shown to be a good starting point for the transformational derivation of the Cocke-Kasami-Younger tabular parsing algorithm that follows. This derivation is carried out at the level of bag comprehensions.



Bibtex Record

@conference{167,
author = {E.A. Boiten},
title = {Parsing in {ISBES}},
month = {June},
year = {1993},
pages = {182-196},
keywords = {determinacy analysis, Craig interpolants},
note = {},
doi = {},
url = {http://www.cs.kent.ac.uk/pubs/1993/167},
    ISBN = {3-540-57316-X},
    address = {Berlin},
    booktitle = {Formal Methods in Programming and Their     Applications},
    editor = {D. Bjorner and M. Broy and I.V. Pottosin},
    publisher = {Springer-Verlag},
    refereed = {yes},
    series = {Lecture Notes in Computer Science},
    volume = {735},
}

School of Computing, University of Kent, Canterbury, Kent, CT2 7NF

Enquiries: +44 (0)1227 824180 or contact us.

Last Updated: 21/03/2014