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

L>А какие есть вообще варианты, когда у PEG получается сложность хуже чем линейная? Удалось придумать только такой изврат:
L>

L>xxxxxxxx
L>A = . A / . A / "y";
L>

L>(экспонента, негативный результат)

И что ты тут придумал?

Если '.' — это любой символ, то смысл в ' / . A / "y"' отсутствует на прочь, а разбираться эта байда будет за линейное время.

В PEG '/' — это приоритетный выбор. Если он сматчился, то другие альтернативы рассматриваться не будут. По сему в PEG любая грамматика однозначана.

Что до "когда у PEG получается сложность хуже чем линейная" то все зависит от алгоритма. Для PEG есть алгоритм Пакрат. У него линейная сложность для любой грамматики. Вот только тормоз он.
Ну, а без Пакрата (читай тотальной мемоизации). Любая грамматика требующая сильных откатов будет не ленейная. Но опять же все зависит от оптимизаций.