Re: LL1 grammar conversion Algorithms

"Scott Stanchfield" <>
16 Feb 1997 22:28:52 -0500

          From comp.compilers

Related articles
LL1 grammar conversion Algorithms (1997-02-11)
Re: LL1 grammar conversion Algorithms (John Lilley) (1997-02-16)
Re: LL1 grammar conversion Algorithms (Scott Stanchfield) (1997-02-16)
| List of all articles for this month |

From: "Scott Stanchfield" <>
Newsgroups: comp.compilers
Date: 16 Feb 1997 22:28:52 -0500
Organization: scruz-net
References: 97-02-075
Keywords: LL(1), parse 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
        | rule3

    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)

    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
Scott Stanchfield, Santa Cruz CA
See my PCCTS Tutorial at

Post a followup to this message

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