John Rushby

PhD Thesis, Computing Laboratory, University of Newcastle upon Tyne, UK, September 1977.

I'd like to find a way to get this online (success--see below). It's 400 pages and typewritten, with formulas drawn in by hand with a mapping pen! The gocr OCR program delivered the following interpretation of the first few lines of the abstract

 A_STRACT

A method of syntactic _alygts ta developed whtch
tg beltevea to B_pasg all known competttors in _ll major
reepectg_
Tbe method ta based upon that ageoctatn_d with the
_RCb_ Br_ara but ig f_ter becauBe it bypasseg all
reductton BtepB concerned with lchatnl producttong_ These
_e freely aelected productíons which are congtdered
Bem_ttCally trreleV_t _d whose rieht p_tB consiat of

Abstract

The method is based upon that associated with the LR(k) grammars but is faster because it bypasses all reduction steps concerned with 'chain' productions. These are freely selected productions which are considered semantically irrelevant and whose right parts consist of just a single symbol. The parses produced by the method are 'sparse' in that they contain no references to chain productions - they are termed 'chain-free' parses.

The CFLR(k) grammars are introduced as the largest class which can be Chain-Free parsed from Left to Right while looking k symbols ahead of the current point of the parse. The properties of these grammars are examined in detail and their relationship to the conventional LR(k) grammars is explored. Techniques are presented for testing grammars for the CFLR(k) property and for constructing chain-free parsers for those grammars possessing the property. Methods are also presented for. converting ordinary LR(k) parsers into chain-free parsers.

CFLR(k) parsers are more widely applicable than their LR(k) counterparts, are faster and provide the same excellent detection of syntactic errors. Unfortunately they also tend to be rather larger. A 'simple optimization is presented which completely'overcomes this single disadvantage without sacrificing any of the advantages of the method.

These theoretical techniques are adapted to provide truly practical chain-free parsers based on the conventional SLR and,LALR parsing methods. Detailed consideration is given to use of 'default reductions' and related techniques for achd.evfng compact representations of these parsers. The resulting chain-free parsers are not only faster than their ordinary counterparts, but probably smaller too. We believe their advantages are such that they should substantially replace other parsing methods currently used in programming language compilers.

Files

Well, what do you know...Newcastle University has scanned its old theses and put them online. You can find mine here; beware that it is about 20 MBytes....now that link is broken.

Here's a local copy: PhD Thesis

BibTeX Entry

@phdthesis{Rushby77,
	AUTHOR = {John Rushby},
	SCHOOL = {Computing Laboratory, University of Newcastle upon Tyne},
	TITLE = {{LR}(k) Sparse-Parsers and their Optimisation},
	YEAR = 1977,
	MONTH = sep
}