Author: Lindsay Groves
Source: GZipped PostScript (52kb); Adobe PDF
(253kb)
We show how a predictive parsing algorithm can be derived by first deriving a generic language recognition algorithm, and then specialising this to a class of context-free languages. This strategy allows us to work out the basic structure of the algorithm, based on very general properties of the specification, and then develop more intricate parts of the algorithm and introduce suitable data representations afterwards. The resulting derivation is more intelligible than if we considered all aspects of the specification from the outset, and allows the derivation to be more easily adapted to handle other classes of languages.