Converting a Grammar from LALR to LL

[from a post of mine in a thread about automated tools to convert from LALR grammars to LL grammars... NOTE: These are fairly general (but pointed to PCCTS 1.33 -- note that PCCTS 2.0 does not implement syntactic predicates with setjmp/longjmp]

Toolwise, I think you're pretty much SOL. But there are several common algorithms available that you could probably use to write a simple tool.

HOWEVER, I don't think you'd really want the code they'd generate, and hand-written ANTLR rules using its EBNF notation are much more maintainable.

There are two "big" issues to deal with in the conversion (and some minor headaches as well):

Most (if not all) yacc grammars can be converted into ANTLR grammars, but I suggest you use thought to do it rather than mechanical force (unless there's a mechanical force that smart enough, which I doubt.) It doesn't take too long to do it, either. A few other things to remember about ANTLR:

action code can be placed _anywhere_ in rules without adding conflicts (although placing them at the start of a rule makes it and "init action" rather than a normal action -- see the docs

You can pass/return values to/from other rules as parameters to the rules. This is a GREAT feature that you just can't do in yacc due to the nature of LALR parsing try to use label _names_ instead of label _numbers_ (as in yacc) this'll save tons of headache when you need to make a mod like adding a rule reference to a rule.

Figure 14: Action code

yacc :    a: B C {$$ = do($1, $2);}

ANTLR:    a: b:B c:C <<$0 = do($b, $c);>>

(keep in mind that you can only label terminals -- if you need a result from a subrule, pass it back as a return value)

Good luck!