16 Feb 1997 22:28:52 -0500

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

From: | "Scott Stanchfield" <thetick@scruz.net> |

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.