Re: A new? table compression technique for LR parsers

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

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