[net.lang] correction to LL

mauney@ncsu.UUCP (Jon Mauney) (05/16/84)

In general, I agree with Binayak Banerjee's comments on parsing,
but I must correct one minor point, concerning as it does my
specialty: syntax errors (making and correcting them).

LL and LR parsers, including SLR and LALR, all have the prefix property:
the parser will halt when the string of symbols read does not form the
prefix of any sentence in the language.  I.e.,  the parser will never
accept an erroneous symbol.

However,  full-blown LR and LL parsers have another property not shared
by SLR, LALR, and Strong LL (the usual implementation) parsers: Immediate
Error Detection.  An LR(1) parser will halt as soon as the offending token
appears in the lookahead; an LALR parser may make several reductions before
noticing the error, and the usual LL parser may pop several symbols off the
stack.  Lack of immediate detection can restrict the choices in error
handling, but it is not the same as the lack of the prefix property.
(Precedence parsers, by the way, often lack the prefix property.)

Anyone genuinely interested in long lectures on syntax errors 
is invited to correspond directly by mail.
-- 

_Doctor_                           Jon Mauney,    mcnc!ncsu!mauney
\__Mu__/                           North Carolina State University