Re: LL vs LR, strengths and weaknesses

ressler@cs.cornell.edu (Gene Ressler)
Thu, 14 May 1992 22:14:00 GMT

          From comp.compilers

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)
| List of all articles for this month |

Newsgroups: comp.compilers
From: ressler@cs.cornell.edu (Gene Ressler)
Keywords: LL(1), LR(1), parse
Organization: Cornell Univ. CS Dept, Ithaca NY 14853
References: 92-05-059 92-05-079
Date: Thu, 14 May 1992 22:14:00 GMT

I've been surprised that no one has mentioned the inherent problem that LL
has with many precedence levels, i.e. to parse ((x*x)+(y*y)) in C
requires perhaps 70 recursive descent calls (or stack pushes in a
table-driven LL parser) with the stack up to 30 deep, whereas an LALR
parser does 13 stack ops and never gets deeper than 6. (All these subject
to the correctness of my hand parses, but I think they're in the
ballpark).


Comments on the practical effects of this observation, especially from the
LL advocates?


(For starters, I believe this is why at least some RD parsers have
embedded operator precedence parsers to do arithmetic.)


Gene
--


Post a followup to this message

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