# Re: LL1 grammar conversion Algorithms

## "Scott Stanchfield" <thetick@scruz.net>16 Feb 1997 22:28:52 -0500

From comp.compilers

Related articles
LL1 grammar conversion Algorithms gholness@bu.edu (1997-02-11)
Re: LL1 grammar conversion Algorithms jlilley@empathy.com (John Lilley) (1997-02-16)
Re: LL1 grammar conversion Algorithms thetick@scruz.net (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

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
--

Post a followup to this message

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