|LL1 grammar conversion Algorithms email@example.com (1997-02-11)|
|Re: LL1 grammar conversion Algorithms firstname.lastname@example.org (John Lilley) (1997-02-16)|
|Re: LL1 grammar conversion Algorithms email@example.com (Scott Stanchfield) (1997-02-16)|
|From:||"Scott Stanchfield" <firstname.lastname@example.org>|
|Date:||16 Feb 1997 22:28:52 -0500|
email@example.com wrote in article 97-02-075...
> Does anyone know of any implementation of an algorithm which will
> convert an LALR grammar to LL1.
A lot depends on the tool you're using too. If you're using a tool
such as PCCTS, you can do some swell optimizations using EBNF
notation. You can do much better thinking about it than using an
algorithm (gives a MUCH more readable translation.) Things like the
list : list element | element ;
list : (element)+ ;
(if it had been list : list ',' element | element you would use
list : element (',' element)* )
Note that you need to be careful with actions here -- the list is
built up in the _opposite_ order!
In general, take a look at what the recursion is accomplishing -- what
is getting repeated. Just be careful of orders in actions, because if
you turn a left-recursive rule into a right-recursive rule or use a
loop, you'll probably end up reversing the order in which things are
"reduced" ("matched" would be a better term for LL(k) )
For the old expression rules, take a look at my PCCTS tutorial (see my
sig). It has a good walkthrough of converting operator precedence
rules into LL(1) grammar rules.
For left factoring, there are a couple approaches.
-- just up the value of "k" (the amount of lookahead used) if the parser
generator is LL(k) instead of just LL(1)
(note that this can cause performance problems as k grows, both at
parser-generation time and runtime)
-- predicate the grammar with syntactic/semantic predicates -- see PCCTS
info for details -- adds extra checks besides "is the lookahead "x")
-- do the left factoring -- if possible, this is always your best bet. I
like to say, though, find a good balance between readability and factoring
-- a tricky quest...
With PCCTS, left factoring a rule like
: A B C
| A B D
| A Q W
is as simple as
: A ( B (C | D)
| Q W
Factoring something like
rule2 : A B C ;
rule3 : A B D ;
gets a bit trickier -- you must "promote" the "A B" prefix to the parent
: A B (rule2|rule3)
and this is usually tricky, especially if actions are involved.
Overall -- I know it's more work up front, but by doing a well-thought-out
hand conversion, you'll save a ton of time figuring out the mess that an
algorithm comes up with. (Maintenance will be soooo much easier!)
For PCCTS info, see http://java.MageLang.com/antlr/entry.html.
Scott Stanchfield, Santa Cruz CA
See my PCCTS Tutorial at
Return to the
Search the comp.compilers archives again.