WH>Другими словами ненадо ничего делать. Ибо ровно тоже самое получается при генерации кода методом "в лоб".

да, есть такое
таким образом мы зафиксировали наивный граф автомата, дальше его необходимо редуцировать, чтобы избавиться от восстановления позиции — для этого необходимо "схлопнуть" все три ветки: красную, синюю и зеленую.

DG>>здесь необходимо модифицировать правила построения автомата
DG>>правила перехода для first-variant должны всегда перекрывать такие же правила для second-variant
WH>Спасибо тебе КО. Вот только засада в том что лесом пойдет вся теория автоматов и все алгоритмы придется выдумывать с нуля.

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

DG>>в состояния автомата необходимо добавить информацию к какой именно части какого конкретного правила эти состояния относятся
WH>И что это даст?

для правила .*. — это даст автомат:

(0,.)->0
(0,else)->1
(1,.)->end
(1,else)->error

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

VD>Да, я как-то упустил из виду, что речь идет о случае облома. Ну, так надо или алгоритмы сложнее плинтуса использовать или не писать абсолютно бредовые грамматики. А лучше и то, и другое. На что циклы то?

Просто у меня появилась идея, как сделать эффективную реализацию пакрата. Но возникает вопрос — а так ли сильно оно надо? Потому и спрашиваю.. есть ли вообще реальные случаи, где это сильно нужно.

WH>>Это да. Но тут видимо имелось в виду реализация без мемоизации.
VD>Ну, раз имелось, то надо было об этом и говорить. Без этого его слова являются чушью.

Чушью является предположение, что я писал про реализацию с мемоизацией — потому что она всегда имеет линейную сложность

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

VD>Причем с точки зрения сложения разницы не будет вовсе.

Кому нафиг нужно сложение без вычитания?

VD>Ассоциативность и приоритеты становятся декларируемыми.

А в какой форме это у вас записывается в грамматике?

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

L>Просто у меня появилась идея, как сделать эффективную реализацию пакрата.

Это иллюзия. Единственный способ сделать Пакрат быстрее это уменьшать мемоизацию.
Собственно наш алгоритм довольно шустр именно потому, что вместо тотальной мемоизации используется очень шустрая мемоизация для самого глубокого применения правил.

L>Но возникает вопрос — а так ли сильно оно надо? Потому и спрашиваю.. есть ли вообще реальные случаи, где это сильно нужно.

Что? Гарантированно линейное время разбора? Это было бы идеальным решением, если бы при этом не получались гарантированные тормоза.

Лично я практик не верящий в чудеса. Потому меня удоволетворяет наша реализация. Она довольно шустра и предотвращает наиболее вероятные случаи экспоненциального роста вычислительных затрат.

WH>>>Это да. Но тут видимо имелось в виду реализация без мемоизации.
VD>>Ну, раз имелось, то надо было об этом и говорить. Без этого его слова являются чушью.

L>Чушью является предположение, что я писал про реализацию с мемоизацией — потому что она всегда имеет линейную сложность

Линейную сложность имеет только тотальная мемоизация.

Более того PEG вообще не обязывает к использованию конкретных алгоритмов. Так что говоря о каких-то характеристиках нужно упоминать и алгоритм.