ATLR 4 - итерационный против рекуррентного

Question

Пусть это абстрактное синтаксического дерева:

Я полагаю, что ANTLR будет пересекать это дерево, используя рекурсивный алгоритм я оценю это дерево много раз ((глубина первого обход.) например, 10MM раз.)

Вместо этого, используя рекурсивный алгоритм для перемещения этого дерева, я мог бы использовать итеративный (используя собственный стек). Я полагаю, что для кукольного представления производительности итеративный алгоритм будет работать намного лучше. Использует ли ANTLR рекурсивный траверс? Это проблема производительности?

Спасибо!

Answer 1

ANTLR 4 Посетители, безусловно, используют рекурсивный обход по умолчанию. В прослушивателях ANTLR 4 используется ходунок, а текущая реализация ParseTreeWalker.walk также использует рекурсивный обход.

В сценариях с высокой производительностью слушатели и посетители предназначены для удобного использования при преобразовании деревьев синтаксического анализа ANTLR 4 в какое-либо другое представление выполнения, например, для пользовательского интерпретатора байт-кода (например, StringTemplate 4), генерации динамического кода в ECMA -335 или JVM байт-код, или компиляция JIT/AOT в собственный код. Это не проблема производительности, потому что деревья синтаксического анализа оцениваются несколько раз.