Account Options

  1. Sign in
The old Google Groups will be going away soon, but your browser is incompatible with the new version.
Google Groups Home
« Groups Home
Message from discussion Wanted: YACC for Java
The group you are posting to is a Usenet group. Messages posted to this group will make your email address visible to anyone on the Internet.
Your reply message has not been sent.
Your post was successful
 
From:
To:
Cc:
Followup To:
Add Cc | Add Followup-to | Edit Subject
Subject:
Validation:
For verification purposes please type the characters you see in the picture below or the numbers you hear by clicking the accessibility icon. Listen and type the numbers you hear
 
Scott Stanchfield  
View profile  
 More options Jul 7 1997, 3:00 am
Newsgroups: comp.lang.java.softwaretools
From: Scott Stanchfield <thet...@scruz.net>
Date: 1997/07/07
Subject: Re: Wanted: YACC for Java

I hope this doesn't start a war...

First -- Frank, if you see this, don't shoot me.  (My boss is Frank
DeRemer, the creator of LALR parsing...)

(I Borrowed this summary from Fischer&LeBlanc's "Crafting a Compiler")

  Simplicity    -- LL
  Generality    -- LALR
  Actions       -- LL
  Error repair  -- LL
  Table sizes   -- LL
  Parsing speed -- comparable (me: and tool-dependent)

Simplicity -- LL wins
==========
The workings of an LL parser are much simpler.  And, if you have to
debug a parser, looking at a recursive-descent parser (a common way to
program an LL parser) is much simpler than the tables of a LALR parser.

Generality -- LALR wins
==========
For ease of specification, LALR wins hands down.  The big
difference here between LL and (LA)LR is that in an LL grammar you must
left-factor rules and remove left recursion.

Left factoring is necessary because LL parsing requires selecting an
alternative based on a fixed number of input tokens.

Left recursion is problematic because a lookahead token of a rule is
always in the lookahead token on that same rule.  (Everything in set A
is in set A...)  This causes the rule to recurse forever and ever and
ever and ever...

To see ways to convert LALR grammars to LL grammars, take a look at my
page on it:
  http://www.scruz.net/~thetick/lalr2ll.html

Many languages already have LALR grammars available, so you'd have to
translate.  If the language _doesn't_ have a grammar available, then I'd
say it's not really any harder to write a LL grammar from scratch.  (You
just have to be in the right "LL" mindset, which usually involves
watching 8 hours of Dr. Who before writing the grammar...  I actually
prefer LL if you didn't know...)

Actions -- LL wins
=======
In an LL parser you can place actions anywhere you want without
introducing a conflict

Error repair -- LL wins
============
LL parsers have much better context information (they are top-down
parsers) and therefore can help much more in repairing an error, not to
mention reporting errors.

Table sizes -- LL
===========
Assuming you write a table-driven LL parser, its tables are nearly half
the size.  (To be fair, there are ways to optimize LALR tables to make
the smaller, so I think this one washes...)

Parsing speed -- comparable (me: and tool-dependent)

Hope this helps a bit!
 -- Scott

Lars Marius Garshol wrote:

> Scott Stanchfield <thet...@scruz.net> wrote:

> >Note that both ANTLR and JavaCC are LL(k) tools (although ANTLR performs
> >more analysis on k>1 lookahead).  If you're looking for a LALR-based
> >tool, look for JavaCUP.  I think gamelan has a link to it somewhere,
> >but, being an LL junkie I've avoided it...

> Just curious: what advantages does LL have? I know it's more
> straightforward, but still...

> --Lars M.

> ________________________________________________________________________

>  Lars Marius Garshol

>  "Make it idiot proof and someone will make a better idiot", Bill Arnett
>  http://www.ifi.uio.no/~larsga/        http://birk105.studby.uio.no/

--
Scott Stanchfield  Santa Cruz,CA
Get some info on ParseView - my Visual ANTLR debugger at
    http://www.scruz.net/~thetick/parseview
Visit my PCCTS Tutorial at http://www.scruz.net/~thetick/pcctstut
See my cute baby girl at   http://www.scruz.net/~thetick/claire

 
You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.