# Re: GLR question

## haberg@math.su.se (Hans Aberg)21 Feb 2003 00:44:19 -0500

From comp.compilers

Related articles
GLR question fgagnon@inouii.com (Francois Gagnon) (2003-02-13)
Re: GLR question haberg@math.su.se (2003-02-21)
Re: GLR question joachim_d@gmx.de (Joachim Durchholz) (2003-02-24)
| List of all articles for this month |

 From: haberg@math.su.se (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 <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

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
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>