[antlr-interest] Bug in generation code

Loring Craymer lgcraymer at yahoo.com
Sat Oct 13 00:50:01 PDT 2007


Johannes--

Your original message raised the issue of why I was using an outdated version of the ANTLR 3 engine and asking why I had not incorporated the rewrite syntax (as I interpreted your writing) that Ter adopted for ANTLR 3.

I tracked the ANTLR 3 engine up to 3.0; I probably will not track 3.1 beyond bug fixes to avoid incorporating Ter's inheritance mechanism (a kludge).  3.0 fixes all of the problems that plagued earlier versions of the internals.

Ter adapted the rewrite syntax used in most attribute grammars based on LALR BNF parser generators--the main addition is his += operator.  I rejected that approach when I did ANTLR 2.8 (which was actually released about the same time as ANTLR 2.7.5 through an outfit that JPL was doing business with at the time and may still be).  My original analysis was that the implementation cost would be high, and the syntax becomes problematic for EBNF grammars that support iterative closures ( * and + ).  It also appeared unlikely to integrate well with the ^ annotation.  I am gratified that Ter's ANTLR 3 work confirmed that analysis:  if you look at the ANTLR 3 internals, it takes a lot of code to support the -> rewrites, the += is an interesting addition which does help with iterative closures but is not ideal, and you cannot mix ^ annotation with rewrites within a rule.

ANTLR 2.8 was one of the inspirations for ANTLR 3.  When Ter, Monty, and I got together to plan ANTLR 3, the key elements were a.)  templates for action code, b.) a first-class rewrite syntax, c.) attribute scoping (Monty's idea), and d.) automatic tree grammar generation (also from 2.8).  LL* came along later.  At that time, I was pushing for a decent attribute syntax, but had no clear idea of what one looked like:  my experience was that I had not gone far enough with ANTLR 2.8 and in particular could not capture retyping of tokens when doing grammar generation.

At any rate, the current status of ANTLR Yggdrasil is that I am in the midst of debugging the passes of a tree grammar generator that track translocation of tree fragments; the next step after that is to implement the algorithm I used in ANTLR 2.8 to rewrite iterative closures that contain ^'s.

I also have a half-done ANTLR 2 to Yggdrasil translator.  I had intended to finish that before I did the tree grammar generation, but ended up needing the tree grammar generation to do the translator.  I should point out that this is a full translator, including a Java-to-Yggdrasil translation of actions and attributes.  Any less than that and it would be difficult to convert the ANTLR 2 implementation of Yggdrasil to Yggdrasil in Yggdrasil; as Ter has pointed out, that is a significant task for ANTLR 3.

I have thought about of doing an ANTLR 3 to Yggdrasil translator at some later time, but do not really see much point.  The ANTLR 3 rewrite support is much weaker than that in Yggdrasil (ANTLR 3 does not support translocation of tree fragments across rule boundaries; in my experience, translocation is essential for most interesting translation problems), and working with a tree grammar generator makes a radical impact on how one works with ANTLR.

Once I finish the tree grammar generator, I will probably run out of excuses for not having posted Yggdrasil on sourceforge.  Or maybe not:  real world distractions take their toll.

--Loring

----- Original Message ----
From: Johannes Luber <jaluber at gmx.de>
Cc: antlr-interest <antlr-interest at antlr.org>
Sent: Friday, October 12, 2007 6:55:31 AM
Subject: Re: [antlr-interest] Bug in generation code


Gavin Lambert wrote:
> At 10:48 12/10/2007, Johannes Luber wrote:
>>BTW, how is your ANTLR derivative named again? I'd like
>>to ask if you overlooked an email with some critiques
>>regarding your project, but I can't find that email again. :(
> 
> I don't have an ANTLR derivative, so you must be thinking of someone
> else :)
> 
I could have sworn, that the name of the email author was Loring Cramer
and not you. Well, maybe he reads this email here.

Johannes





      ____________________________________________________________________________________
Catch up on fall's hot new shows on Yahoo! TV. Watch previews, get listings, and more!
http://tv.yahoo.com/collections/3658 


More information about the antlr-interest mailing list