Я тут сравнил производительность леворекурсивных и обычных правил в ANTLR: https://github.com/KvanTTT/AntlrBenchmarks/tree/master/AntlrLeftRecursionBenchmark Оказалось, что обычные рвут леворекурсивные - они быстрее в 3 раза!

|               Method             |     Mean  |     Error       |    StdDev   | Ratio |
|    LeftRecursionTest     | 3.277 ms | 0.0636 ms | 0.0827 ms |  1.00 |
| NotLeftRecursionTest | 1.008 ms | 0.0178 ms | 0.0166 ms |  0.31 |

Придется, видимо, отказываться от левой рекурсии, если производительность парсера критична.

Не зря, значит, я несколько правил переписал без левой рекурсии. 😄

на идрисе есть парсер который на уровне типов её запрещает :)

У нас еще это окончательно решит проблему с восходящих построением дерева (ну и у всех, кто не строит дефолтное дерево, т.е. BuildParseTree = false), т.к. вся эта магия типа GetLeftChildFromLeftRecursiveRule и IsLeftRecursiveAlternative не понадобится.

А зачем ее запрещать на уровне типов?

чтобы наслаждаться тотальностью

т.е. гарантируется что каждый комбинатор что-то отъедает от входа, не может быть бесконечной рекурсии по построению

Как эпично тема в тему.
У нас рантайм на рекурсии упал с Max Call Stack

Технически хвостовая рекурсия может же быть бесконечной?

конечно

Тогда она не хвостовая же

Или хвостовая без оптимизации.

Еще есть хвостовая modulo cons. То есть, оптимизация, превращающая обычную функцию map в нежрущую стек.

Ну всегда считал, что хвостовая от обычной отличается именно оптимизацией

хвостовая - это просто вызов является последней операцие

Либо первым

Вроде же есть автоматические алгоритмы по избавлению от левой рекурсии?

Я таких не знаю. 🤷‍♀
Сомневаюсь, что они бы справились с той грамматикой, с которой я работаю. Там реальный трешачок. 😄

Лол.
Мне тут сказали что нахер нам не нужен инкрементальный компилятор.
Гони все сразу в JS. Подожди год пока оно собирется.

Если не секрет, какой минимальный пример граммитики, который нельзя "исправить" этим алгоритмом? https://neerc.ifmo.ru/wiki/index.php?title=Устранение_левой_рекурсии