Wanted: YACC for Java

68 views
Skip to first unread message

Keith Lander

unread,
Jul 4, 1997, 3:00:00 AM7/4/97
to

Does anyone know where I can get hold of a Java version of YACC?

Cheers
Keith Lander | kla...@enterprise.net

Lars Marius Garshol

unread,
Jul 4, 1997, 3:00:00 AM7/4/97
to

"Keith Lander" <kla...@enterprise.net> wrote:
>Does anyone know where I can get hold of a Java version of YACC?

Take a look at JavaCC:
http://www.suntest.com/JavaCC/

--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

unread,
Jul 4, 1997, 3:00:00 AM7/4/97
to

Take a peek at ANTLR 2.0 (aka PCCTS 2.0). It's at

http://java.magelang.com/antlr

I'm also writing a visual debugger for it at

http://www.scruz.net/~thetick/parseview

which should make developing parsers much more pleasant ;)

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...

Have fun!
Scott

--
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

Lars Marius Garshol

unread,
Jul 7, 1997, 3:00:00 AM7/7/97
to

Scott Stanchfield <the...@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...

Scott Stanchfield

unread,
Jul 7, 1997, 3:00:00 AM7/7/97
to

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

--

Reply all
Reply to author
Forward
0 new messages