Balancer> Вроде, у парсеров давно уже сложность O(N). По крайней мере, 10Мб HTML 10 лет назад парсились за несколько секунд. А сейчас — за доли секунды. 15 лет назад оно бы тормозило сильно, но из-за процессора, а из-за нехватки памяти.
Ром, если ты имеешь ввиду лексический парсер, то да. А синтаксический очень сильно зависит от грамматик. 3 типа или регулярные выражения — тоже примерно так. Второго типа, или контекстно свободные, тоже так будут. Всякие LL(1), LR(1) — уже посложнее (контекст ограничен одним синтаксическим символом слева или справа). Если брать общие утверждение LL(n), LR(n), то там сложнее, возвраты могут быть наполную, но определяются глубиной контекста. В общем случае, когда просто грамматика типа 1 — полная попа. Насколько я знаю, HTML сочиняли не особо думая про парсеры.
Balancer> Повторюсь — речь не о парсинге, а об обработки. Парсить CSS даже куда проще, чем HTML, у него очень простая и однозначная грамматика. Вот потом на результат парсинга надо вызывать тонну сложных методов (в т.ч. и тех, где GPU реально востребован и работает), но к вопросу парсинга это отношения не имеет.
Проще? Может быть. Только по мнению W3C нужен LALR(1) механизм для нормального разбора —
Grammar of CSS 2.1, т.е. контекстно-свободного механизма не хватает.
А обработка — да, там работы ещё хватает.
Balancer> Реакция на некорректный HTML стандартами не описывается и в общем случае к радикальному, на порядки, усложнению парсера не приводит. Более того, никто парсер так усложнять не станет, так как реакция на некорректный HTML стандартами не описывается.
Да, не описывается. И тому есть причины.
Но жизнь может усложнить, т.к. некорректный HTML по стандарту не должен обрабатываться после нахождения ошибки. Но иметь поведение, как у ТурбоПаскаля никто не хочет. Потому все что-то своё делали.
Кстати, я ещё не видел формальное определение языка, которое бы предписывало поведение системы в ответ на синтаксическую ошибку. Ну кроме того, что надо бы показать, что ошибка была. А вот показать причину и где — этого уже не помню.