21 Feb 1999 21:41:10 -0500

Related articles |
---|

What IS an LL/LR/SLR/LALR etc. grammar? joe.hotchkiss@gecm.com (Joe Hotchkiss) (1999-02-18) |

Re: What IS an LL/LR/SLR/LALR etc. grammar? dwight@pentasoft.com (1999-02-21) |

Re: What IS an LL/LR/SLR/LALR etc. grammar? paul.janssens@skynet.be.NOSPAM (JPA) (1999-02-21) |

Re: What IS an LL/LR/SLR/LALR etc. grammar? bromage@cs.mu.OZ.AU (1999-02-21) |

Re: What IS an LL/LR/SLR/LALR etc. grammar? jamz@my-dejanews.com (1999-02-24) |

Re: What IS an LL/LR/SLR/LALR etc. grammar? mslamm@mscc.huji.ac.il (Ehud Lamm) (1999-02-24) |

From: | bromage@cs.mu.OZ.AU (Andrew Bromage) |

Newsgroups: | comp.compilers |

Date: | 21 Feb 1999 21:41:10 -0500 |

Organization: | Computer Science, The University of Melbourne |

References: | 99-02-099 |

Keywords: | parse |

G'day all.

Joe Hotchkiss <joe.hotchkiss@gecm.com> writes:

*>I have been writing a small recursive descent parser, mostly for my own*

*>amusement, and have been trying to document it for others to use. In*

*>doing so I have tried to give definitions of some terms, but I can't*

*>actually find a clear definition of the various types of grammar.*

OK, here goes...

*> LL(1) = scans input left-to-right, produces output for the*

*>left-most bits first, and looks ahead at most 1 symbol at a time.*

LL(1) = scans input from left-to-right, produces a leftmost derivation

top-down, 1 symbol of lookahead

LL(k) is precisely the class of grammars which can be deterministically

parsed using a recursive descent parser where parsing decisions are based

on left context and k symbols of lookahead only.

*> LR(1) = scans input left-to-right, produces output for the*

*>right-most bits first (but does so in reverse order for some reason!),*

*>and looks ahead at most 1 symbol at a time.*

LR(1) = scans input from left-to-right, produces a rightmost derivation

in reverse bottom-up, 1 symbol of lookahead

LR(k) is precisely the class of grammars which can be deterministically

parsed using a shift-reduce (or recursive ascent) parser where parsing

decisions are based on left context and k symbols of lookahead only.

*> LALR(1) = Look-Ahead LR(1), but the (1) indicates that it looks*

*>ahead 1 symbol anyway, so what is the difference? I have seen clear*

*>statements that LR(1) is NOT the same as LALR(1).*

LALR(k) is not a simple class of grammars to reason about since its

definition is based on the kind of automaton used to parse it. LALR(k)

is, basically, what you get when you take an LR(k) parser and squish

it down to LR(0) size, possibly losing information along the way.

*>Then there are SLR and SLALR grammars and quite possibly others that I*

*>have not come across yet.*

SLR(k) is what you get when you start with an LR(0) parser and approximate

lookahead information by using follow sets. It's rarely used nowadays

since:

- People generally don't use k > 1

- LALR(1) is a superset of SLR(1)

- Modern LALR(1) generators are extremely efficient, and the

time saved generating SLR(1) parsers just isn't worth it.

Again, it's a bit hard to reason about SLR, because its definition is

based on the automaton which parses it. It's a bit easier than LALR,

though...

I don't know about SLALR.

As for a book, Nigel Chapman's "LR Parsing: Theory and Practice" is

a good one if you want to delve into the topic, and the definitions

are presented well.

Cheers,

Andrew Bromage

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.