Re: GLR question

Francois Gagnon <fgagnon@inouii.com> 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 <remove.haberg@member.ams.org>
                                    * Home Page: <http://www.math.su.se/~haberg/>
                                    * AMS member listing: <http://www.ams.org/cml/>

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