К>>> лукохеды могут очень жёстко просадить производительность. Сделать квадратичную — легко. Сделать кубическую — чуть сложнее (двойное отрицание).
AS>>нет. при ненаивной реализации можно обеспечить линейную. И ненадо меня убеждать, что нельзя.
К>Есть что почитать на эту тему? Или на пальцах объяснить?

Мысль такова:
1) алгоритм Эрли при однозначности грамматики при парсинге текста даёт линейную сложность
2) рассмотрим оператор "-". У него слева грамматика, справа грамматика.
Видим, что линейная сложность получает множитель ~= 2
И ещё небольшая добавочная константа — для того, чтобы выполнить логические операции (при создании узла SPPF, что внутри диапазона не начинается другое, отрицательное, дерево)

таким образом сложность в квадратичную и кубическую превращаться не должна.

3) регэкспы перла — это не то же самое, что регэкспы нормального человека, описанные в Posix (статья в википедии)
4) парсер регулярных выражений Перла реализован на алгоритме Эрли (ЕВПОЧА)

К>>> лукохеды могут очень жёстко просадить производительность. Сделать квадратичную — легко. Сделать кубическую — чуть сложнее (двойное отрицание).
AS>>нет. при ненаивной реализации можно обеспечить линейную. И ненадо меня убеждать, что нельзя.
К>Есть что почитать на эту тему? Или на пальцах объяснить?

Это я мало подумал. Согласен на полиномиальную (сколько вложенных минусов — такая и степень).