1979 | OriginalPaper | Chapter
LR(1) Syntax Analysis
Author : Richard Bornat
Published in: Understanding and Writing Compilers
Publisher: Macmillan Education UK
Included in: Professional Book Archive
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Theoretical studies of the properties of programming language grammars and of algorithms for syntax analysis have always been partly motivated by the search for a truly automatic means of constructing a syntax analyser. In the early 1960s so called ‘compiler-compilers’ were popular. One of the earliest was developed at the University of Manchester (Brooker et al., 1963): it included a parser-transcriber which took a syntax description and without alteration transcribed it into a top-down syntax analyser1. Foster’s SID (Foster,1968) was the first of many parser-generator programs which went further so far as syntax analysis was concerned: its input was a type 2 grammar, on which it performed most of the operations discussed in chapter 16 to produce a one-symbol-look-ahead grammar, which it finally transcribed into an ALGOL 60 program. The transformations required to make a grammar one-track or one-symbol-look-ahead aren’t always simply mechanical, however, and in practice a top-down parser-generator like SID often fails to complete its task. Parser-generators for top-down analysers were little used, therefore, and most syntax analysers were written by hand using the techniques discussed in earlier chapters.