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

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

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