search

kjosib / booze-tools

Booze Tools will become the complete programming-language development workbench, all written in Python 3.9 (for now).
MIT License
14 stars 1 forks source link

Improve ACTION table compaction #7

Closed kjosib closed 5 years ago

kjosib commented 5 years ago

The present strategy for compacting the ACTION table can be improved upon.

Currently, it identifies and factors out "default reductions" -- the most common reduction on any given state/row -- and then yields a list of all non-default actions (except inessential errors). The typical way to compress this further involves finding commonalities among rows and storing only the differences between them, similar to the way the DFA table used to work (before issue #8 was committed).

An examination of the ACTION tables deriving from the DECAF and JSON examples shows that column/terminal equivalence classes may be worth identifying and factoring out between the "default-reduction" phase and the "similar-rows" phase. These appear to happen whenever particular groups of terminals are mutually interchangeable within the grammar. For example, the set {true, false, null, number} fits that criteria in the JSON case.

kjosib commented 5 years ago

Commonalities between rows are now exploited nicely and checked in as of 7 May 2019. It's usually a big win, except for relatively small tables. Column equivalence-class experiments will have to wait until there are more sample grammars.