Re: LL1 grammar conversion Algorithms

gholness@bu.edu 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
old


    list : list element | element ;


become
    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


    rule
        : A B C
        | A B D
        | A Q W
        ;


is as simple as


    rule
        : A ( B (C | D)
        | Q W
        ;


Factoring something like


    rule
        : rule2
        | rule3
        ;


    rule2 : A B C ;
    rule3 : A B D ;


gets a bit trickier -- you must "promote" the "A B" prefix to the parent
rule:


    rule
        : A B (rule2|rule3)
        ;


    rule2: C;
    rule3: D;


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
    http://www.scruz.net/~thetick/pcctstut
--

Return to the comp.compilers page.
Search the comp.compilers archives again.