Re: A Non-LALR(1) Parser Generator (Andrew Bromage)
Mon, 17 Aug 1992 01:04:02 GMT

          From comp.compilers

Related articles
A Non-LALR(1) Parser Generator dan%npt1@uunet.UU.NET (1992-08-03)
Re: A Non-LALR(1) Parser Generator (1992-08-05)
Re: A Non-LALR(1) Parser Generator (1992-08-17)
Re: A Non-LALR(1) Parser Generator (1992-08-18)
Re: A Non-LALR(1) Parser Generator (1992-08-17)
Re: A Non-LALR(1) Parser Generator (1992-08-20)
Re: A Non-LALR(1) Parser Generator (1992-08-22)
Re: A Non-LALR(1) Parser Generator (1992-08-25)
| List of all articles for this month |

Newsgroups: comp.compilers
From: (Andrew Bromage)
Organization: Computer Science, University of Melbourne, Australia
Date: Mon, 17 Aug 1992 01:04:02 GMT
References: 92-08-016
Keywords: parse, bibliography

dan%npt1@uunet.UU.NET (Dan White) writes:
> Do you know of any parser generators that will generate parsers for
>languages that are not LALR(1)? Specifically, I want to generate a parser
>for a language called CMS-2.

D Pager has produced a few algorithms which may be of some use. They are
designed to handle LR(1) grammars (a proper superset of LALR(1)), but
produce parsers of realistic size. He does this by merging sets (as in the
standard LALR construction algorithm), but using a different criterion
than equality of cores.

The references are:
Pager, "A practical general method for constructing LR(k) parsers", Acta
Informatica, 7, pp 249-268, 1977.

Pager, "The lane tracing algorithm for constructing LR(k) parsers",
Information Science, 12, pp 19-42, 1977.

The first (ie simpler) algorithm was used in a parser compiler called
"LR", the availability of which I know nothing about.

It was reviewed in:
Wetherell and Shannon, "LR - automatic parser generator and LR(1) parser",
IEEE Transactions on Software Engineering, SE-7, pp 274-278, 1981.

>[A common approach is to twist the syntax around until it's LALR, either by
>accepting a superset of the legal language and throwing out the bad cases
>semantically, or else by using lexical feedback kludges to guide the parser,
>typically by passing up special tokens from the lexer. -John]

This is a really bad hack, and should be avoided. I know it's common
practice, but I don't believe that it's particularly marvellous.

A nice approach was used in Gofer, where operator precedences are
redefinable from the source. The way this was fixed was to store
expressions as a linked list and writing another parser to handle these
expressions. It's a bit like the LL and operator precedence parsers of
yesteryear. I think that the moral of the story is to only use other
techniques when the LR approach genuinely fails, and not before.

Post a followup to this message

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