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

Adaptive choice of compaction algorithms #11

Open kjosib opened 5 years ago

kjosib commented 5 years ago

The GOTO compaction algorithm seems to be about optimal over a wide range of grammars, but the DFA and ACTION tables seem to display different characteristics depending on the size and complexity of the input grammar and scanner definitions. It may be worthwhile for the compiler to try a couple different approaches and see which method yields the smallest tables -- or perhaps let the user select a choice of table storage method at compile-time. The downside is that a complete port of the run-time would have to account for the variation inherent in the system. On the other hand, choice of compaction methods can also influence the size/speed trade-off, or provide an anchor-point for organizing a survey of different methods that have been used in past decades.

kjosib commented 4 years ago

Reference: https://www.researchgate.net/publication/220404687_Optimization_of_Parser_Tables_for_Portable_Compilers

TLDR: They tested various table compaction methods, alone and in combination, for 11 or so grammars looking at the time/space trade-off. They mention a source for published grammars, but it seems to be self-referential back to the same paper.