https://en.wikipedia.org/wiki/Method_of_Four_Russians
The algorithm was introduced by V. L. Arlazarov, E. A. Dinic, M. A. Kronrod, and I. A. Faradzev in 1970.
uses precomputed lookup tables to speed up transitive closure
goes from O(n^3) to O(n^3/log n)
so for a grammar of say 1000 symbols, it would reduce a transitive closure time by one order of magnitude
also video of a UCDavis professor explaining it https://youtu.be/cYJrMUvJQGc (sub-cubic method for bit-matrix multiplication)
А встречается transitive closure в парсере Marpa (дефалтовом парсере языка perl):
https://irclog.perlgeek.de/marpa/2015-11-18
Отредактировано ВежливыйЛис (10.09.2016 10:32:43)