|GLR question firstname.lastname@example.org (Francois Gagnon) (2003-02-13)|
|Re: GLR question email@example.com (2003-02-21)|
|Re: GLR question firstname.lastname@example.org (Joachim Durchholz) (2003-02-24)|
|From:||email@example.com (Hans Aberg)|
|Date:||21 Feb 2003 00:44:19 -0500|
|Posted-Date:||21 Feb 2003 00:44:19 EST|
Francois Gagnon <firstname.lastname@example.org> 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
Hans Aberg * Anti-spam: remove "remove." from email address.
* Email: Hans Aberg <email@example.com>
* Home Page: <http://www.math.su.se/~haberg/>
* AMS member listing: <http://www.ams.org/cml/>
Return to the
Search the comp.compilers archives again.