Thu, 14 May 1992 23:22:39 GMT

Related articles |
---|

LL vs LR, no jihad initiation, but... parrt@ecn.purdue.edu (1992-05-11) |

Re: LL vs LR, strengths and weaknesses eifrig@blaze.cs.jhu.edu (1992-05-11) |

Re: LL vs LR, strengths and weaknesses reid@csgrad.cs.vt.edu (1992-05-13) |

Re: LL vs LR, strengths and weaknesses mauney@adm.csc.ncsu.edu (1992-05-13) |

Re: LL vs LR, strengths and weaknesses ressler@cs.cornell.edu (1992-05-14) |

Re: LL vs LR, strengths and weaknesses eifrig@blaze.cs.jhu.edu (1992-05-14) |

Re: LL vs LR, strengths and weaknesses henry@zoo.toronto.edu (1992-05-15) |

Re: LL vs LR, strengths and weaknesses bob@tera.com (1992-05-19) |

Re: LL vs LR, strengths and weaknesses jos@and.nl (1992-05-16) |

Newsgroups: | comp.compilers |

From: | eifrig@blaze.cs.jhu.edu (Jonathan Eifrig) |

Keywords: | LL(1), LR(1), parse |

Organization: | The Johns Hopkins University CS Department |

References: | 92-05-059 92-05-090 |

Date: | Thu, 14 May 1992 23:22:39 GMT |

[ Hopefully, this can be my last world on this subject. I'm sure we're all

getting bored with this by now. - Jack]

Just a quick review: We're comparing the relative merits of parsing

expressions; in particular, bottom-up using

LR grammar: E -> E + T | E - T | T

T -> T * N | T / N | N

N -> (E) | 1 | 2 | ...

or top-down using

LL grammar: E -> T E'

E'-> + T E' | - T E' | (empty)

T -> N T'

T'-> * N T' | / N T' | (empty)

N -> (E) | 1 | 2 | ...

I think we've established that these are the two "canonical" grammars for

expressions. In 92-05-085, Michael Scott

(scott@cs.rochester.edu) does a very nice job of comparing the two

approaches. In particular, he correctly points out that:

*> This is LL parsing at its absolute worst; if you can stomach expressions,*

*> you won't object to anything else.*

In particular, he points out that LR grammar parse tree for an

expression can be generated using the LL grammar in a top-down fashion by

using inherited attributes: if E -> T E', the parse tree for T is handed

to the "parser" for E', which consumes the operator and the other operand,

cons's them up, and passes the result along to the next E'.

An ingenious solution, sort of like "parsing with continuations."

Let's agree to call this "the canonical LL hack." :-)

Michael Scott continues:

*> It should probably be pointed out that the (less common) RIGHT-associative*

*> operators (e.g. exponentiation) are more naturally expressed with top-down*

*> grammars.*

To be fair, it should be mentioned that right-recursion _can_ be

used in an LR parser; it only causes the maximum stack depth to become

unbounded, something that's going to happen anyways (if we allow

parentheses). LL(k) parsing techniques can't handle left-recursion

_at_all_.

Finally, I think what we've established is that there is no

"right" way to think about parsing. Some people will find that annoyance

of the "canonical hack" is more than compensated by the clarity of

top-down parsing, and will opt to use an LL parser-generator. Others

(like myself) have been so warped by using yacc that our brains have

turned inside out and LR parsing seems perfectly clear while LL is murky.

(Either that, or we've been looking at the results of too many CPS

transformations! :-)

BTW, what _I_'d really like to see is a version of yacc that

allows me to specify a special "reduce function" for productions, such

that the production is reduced iff the "reduce function" evaluates to

"true".

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.