Re: LR(n) parsers

anw@maths.nott.ac.uk (Dr A. N. Walker) writes:


>In article 91-10-036 Steve Boswell <whatis@ucsd.edu> writes:
>[re hard to parse aspects of Algol68]
> b) Both "BEGIN lots of grunge END" and "IF lots of grunge THEN ...."
> may be abbreviated to "( lots of grunge ..." except that "END"
> will be abbreviated to ")" and "THEN" to "|". This can't be
> disambiguated until you get to the ")" or "|", and "lots of grunge"
> may include arbitrarily many declarations and statements.


> On the other hand, all of these ambiguities are "easily" resolved
>in a multi-pass compiler; which surely is the usual resolution of a need
>for long lookaheads.


(I used to assist a lecturer, Thijs Zoethout, who once worked for CDC. He
once explained the following in great length to me) One of the tricks used
in the CDC Algol 68 compiler was to let the lexical analyzer do some
lookahead for inadequate states. Some ambiguities in the parser grammar
can be resolved this way. One case was to recognise the start of a
'routine text', i.e. a procedure parameter list followed by the procedure
body. The ambiguity arises from the extreme overloading of brackets. A
routine text:


(INT a, b, c)INT: (a + b + c)


A 'serial clause':


(INT a, b, c; read((a,b,c)); print((a+b+c, newline)))


This case could be decided by letting the lexical analyser look for the
semicolon or other features that can't occur in a parameter list.
---
Ge' Weijers Internet/UUCP: ge@sci.kun.nl
LCN tel. +3180238130 (UTC+1,
P.O.Box 1408 UTC+2 march/september
6501 BK Nijmegen, the Netherlands
--

Return to the comp.compilers page.
Search the comp.compilers archives again.