Wanted: YACC for Java
Keith Lander
Does anyone know where I can get hold of a Java version of YACC?
Cheers
Keith Lander | kla...@enterprise.net
Lars Marius Garshol
"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
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
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
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
--