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

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

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

Это я мало подумал. Теперь думаю, что сложность будет кубическая от длины текста, помноженная на количество правил в грамматике (алгоритм CYK).