Re: GLR question (Hans Aberg)
21 Feb 2003 00:44:19 -0500

          From comp.compilers

Related articles
GLR question (Francois Gagnon) (2003-02-13)
Re: GLR question (2003-02-21)
Re: GLR question (Joachim Durchholz) (2003-02-24)
| List of all articles for this month |

From: (Hans Aberg)
Newsgroups: comp.compilers
Date: 21 Feb 2003 00:44:19 -0500
Organization: Mathematics
References: 03-02-088
Keywords: parse
Posted-Date: 21 Feb 2003 00:44:19 EST

Francois Gagnon <> wrote:

> I just came across some comments about GLR grammar... I have heard
>of LL, LR, LARL and SLR grammars, but never GLR... Can anyone point me
>to a good book describing how GLR differs from the others?

Current GNU Bison supports a GLR parser. So you can read about it in
the Bison manual, and as well experimenting with writing some GLR
parsers of your own.

I recall that GLR stands for "Generalized LR" or something. It is a
non-deterministic parser algorithm extending an underlying
deterministic parser method, in this case LR. When the LR method fails
to see a deterministic parse, the GLR method will split into several
parsers to seek out all the cases. Eventually those split parsers will
die, or they need to be combined again to a successful parse.

Since you will have figure out how to at combination time do that
recombination, GLR will not help you with common simple computer parsing
ambiguities like a + b * c, which can be resolved by a priority between
the tokens + and *. A better example is probably the parsing of English,
when detecting ambiguities as in:
        Fruit flies like a banana.
Here there are several token (word) ambiguities and a parsing ambiguity to
keep track of. A successful parse should be able to record all the
possibilities, and none which is incorrect.

I think that GLR should be suitable in situation where the parse for
the most of the time is deterministic, but with a few ambiguities in
the grammar.

    Hans Aberg * Anti-spam: remove "remove." from email address.
                                    * Email: Hans Aberg <>
                                    * Home Page: <>
                                    * AMS member listing: <>

Post a followup to this message

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