12 May 1998 22:21:33 -0400

Related articles |
---|

A new? table compression technique for LR parsers torbenm@diku.dk (Torben Mogensen) (1998-05-07) |

Re: A new? table compression technique for LR parsers vmakarov@cygnus.com (Vladimir N. Makarov) (1998-05-12) |

Re: A new? table compression technique for LR parsers paulmann@thegrid.net (Paul Mann) (1998-05-15) |

From: | "Vladimir N. Makarov" <vmakarov@cygnus.com> |

Newsgroups: | comp.compilers |

Date: | 12 May 1998 22:21:33 -0400 |

Organization: | Cygnus Solutions |

References: | 98-05-031 |

Keywords: | LALR |

Torben Mogensen wrote:

*> The idea is that two states in the parse table can be joined if for*

*> each symbol (terminal or nonterminal) they either have the same action*

*> or one of them has an error action. When joining the states, the first*

*> case yields the common action and the second case yields the non-error*

*> action. An example (taken from The Dragon Book) is*

*>*

*> | id + * ( ) $ | E*

*> --+-----------------------+---*

*> 0 | s3 s2 | 1*

*> 1 | s4 s5 acc|*

*> 2 | s3 s2 | 6*

*> 3 | r4 r4 r4 r4|*

*> 4 | s3 s2 | 7*

*> 5 | s3 s2 | 8*

*> 6 | s4 s5 s9 |*

*> 7 | r1 s5 r1 r1|*

*> 8 | r2 r2 r2 r2|*

*> 9 | r3 r3 r3 r3|*

*>*

*> We can combine:*

*>*

*> 0, 1 and 6 to a new state 0,*

*> 2 and 3 to a new state 1,*

*> 4 and 7 to a new state 2,*

*> 5 and 8 to a new state 3,*

*> 9 to a new state 4.*

*>*

*> This gives*

*>*

*> | id + * ( ) $ | E*

*> --+-----------------------+---*

*> 0 | s1 s2 s3 s1 s4 acc| 0*

*> 1 | s1 r4 r4 s1 r4 r4| 0*

*> 2 | s1 r1 r1 s1 r1 r1| 2*

*> 3 | s1 r2 r2 s1 r2 r2| 3*

*> 4 | r3 r3 r3 r3|*

*>*

*> Obviously, a parser using the new table will take non-error actions*

*> where it should have reported an error. This problem is solved by*

*> letting reduce actions check that the stack actually contains the*

*> correct symbols. Since all reductions done by the parser are correct*

*> reductions, you can only get correct parses.*

*>*

*> The problems with this methods are:*

*>*

*> 1) You detect errors later than you would using a traditional LR*

*> parser.*

*>*

*> 2) You need to store the grammar symbols on the stack and check these*

*> on reductions.*

*>*

*> On the other hand, you save a lot of space. Experiments (by hand) with*

*> small parse tables (from chapter 4 in The Dragon Book) yield around*

*> 50% compression and I expect it will be better with large tables,*

*> which tends to be sparser than small tables.*

*>*

*> If (as is commonly done) precedence declarations are used to eliminate*

*> conflicts, you must be careful about nonassoc declarations, as these*

*> can replace one or more actions by an error action (left and right*

*> associative declarations only eliminate comflicts, so they are no*

*> problem). If, by joining states, we replace the error action*

*> introduced by the nonassoc declaration by a non-error action, we might*

*> accept associative uses of the operator in question. This can be*

*> solved by letting nonassoc declarations introduce a special kind of*

*> error action that can not be merged with a non-error action.*

I think that this method is covered by simple comb-vector method of

packing. There are also many other methods of packing tables and

articles which describe them. All these methods (and your one also)

weakly take specific of table data into account. For example, merging

some or all LR-sets into LALR-sets (I call it LALR-optimization) can be

considered also as table compacting . But this is more adequate and fast

solution of table compression.

You could be also use better (with the point of view table space) -

splitting different canonical LR-sets onto common parts and obtain ever

more compact table although and with more rows. For example,

1. LR-Set 2. LR-set 3. LR-set

A: . B B: .C C:.a

B: . C C: .a

C: . a

transform to

A: .B --------B: .C -----C: a

This is only brute illustration.

It could be named by LL-optimization. Moreover it is possible to use

further step - regular-optimizations.

Vlad Makarov

http://visitweb.com/vmakarov

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.