Здравствуйте, WolfHound, Вы писали:

WH>Исключительно во время восстановления. Там Эрли улетает в O(N^2) при этом порождая экспоненциально большой лес деревьев разбора. Как чинить в принципе ясно. Но пока не чинил.

Эрли, вообще-то O(n³) в худшем случае. А при восстановлении этот худший случай мы сами и организуем.

Ты, кстати, разобрался с тем, что в АНТЛР 4 сделано? Там очень похожая на Эрли ситема применяется, а от тормозов спасает то, что он там прямо в онлайн строит НКА и переводит его в ДКА. И за счет этого ДКА отбрасывает большинство альертнатив. За счет этого же у него и восстановление после ошибок упрощается.

Как я понимаю идея строить ДКА-предсказатель в чем-то схожа с идеей делать левую факторизацию для текущих альтернатив. Получается один путь (для однозначной грамматики), который можно пройти очень быстро просто потому он один. Ну, и для восстановления — это просто песня. Вместо перебора 100500 вариантов можно перебирать только те где есть возможность восстановления.

WH>Основной парсер строго линейный на всех поддерживаемых грамматиках.

Линейный не значит одинаково быстрый. Всегда есть зависимость от размера грамматики/числа подправил/числа альтернатив. И наш парсер не исключение. Например, JSON у нас быстрее разбирается чем C# (кстати, в АНТЛР-е все наоборот, почему-то).