In this paper we apply similar techniques to the Earley recogniser and construct two versions of a complete Earley parser, both of which are worst case cubic order
Следите за выводами:
1) примем во внимание, что алгоритм парсинга Эрли имеет кубическую сложность по времени и памяти
2) посчитаем, какого размера исходники мы можем обрабатывать, учитывая размер имеющейся свободной памяти у компьютеров
Если взять смартфон с 6 гигабайтами памяти, то теоретически
всего байтов = 6 * 2 ^ 30 = 1.5 * 2 ^ 32
Если извлечь кубический корень, получается 1860 байтов
Интересно, какой в среднем размер файла у программ на C++ ?
Если взять брутальный десктопный комп, то в нём 512 ГБ памяти => максимум 8000 байтов
Как-то это очень прожорливо в худшем случае...
С другой стороны,
https://github.com/vnmakarov/yaep
It can parse 300K lines of C program per second on modern computers and allocates about 5MB memory for 10K line C program.
То-ли в среднем худшие случаи редкие,
то ли чего-то я не понимаю...
Отредактировано Лис (2017-08-26 06:51:24)