Является ли HTML контекстно-свободным языком?

Ответ 1

Context Free - это концепция теории языка, которая имеет важные последствия для реализации парсера. Контекстно-свободный язык можно описать с помощью свободной грамматики контекста, которая является таковой, в которой все правила имеют один нетерминальный символ слева от стрелки:

X→δ

Это простое ограничение позволяет заменить X на правую часть правил, которые появляются слева, независимо от того, что было до или после. Например, если при получении или синтаксическом анализе вы достигаете:

αXλ 

уверен, что

αδλ

. Примеры правил без контекста:

XY→δ
Xa→δ
aX→δ

Те, кто потребует знать, что можно получить arround X, чтобы определить, применяется ли правило, и что приводит к недетерминированности (что вокруг X также хотел бы знать, к чему оно приводит), что не является -no в разборе, и в любом случае мы хотим, чтобы язык был четко определен.

Единственный способ доказать, что язык не имеет контекста, доказывает, что для него существует контекстно-свободная грамматика, что не является легкой задачей. Большинство языков программирования, о которых идет речь, уже описаны CFG, поэтому работа выполнена. Но есть и другие языки, в том числе языки программирования, которые описываются с использованием логики или простого английского языка, поэтому требуется работа, чтобы определить, не являются ли они контекстуальными.

Для HTML ответ на его контекст-свободу - это да. SGML - это хорошо определенный язык контекста, а HTML, определенный поверх него, также является CFL. Парсеры и грамматики для обоих языков изобилуют в Интернете. Во всяком случае, существуют LL (k) грамматики для корректного HTML, достаточно доказательств того, что язык не имеет контекста, потому что LL является доказанным подмножество CF.

Но способ, которым HTML эволюционировал в течение жизни веб-браузеров, стал относиться к нему как к не столь четко определенному. Современные веб-браузеры будут изо всех сил пытаться сделать что-то разумное из всего, что они находят. Используемые грамматики не являются CFG, а синтаксические анализаторы намного сложнее, чем те, которые необходимы для SGML/HTML.

HTML определен на нескольких уровнях.

• На лексическом уровне существуют правила для допустимых символов, идентификаторов, строк и т.д.
• На следующем уровне находится XML, который состоит из открытия и закрытия <tags>, которые определяют иерархическую структуру документа. Вы можете использовать XML или что-то XML-подобное для любых целей, например Apache Ant для сценариев сборки.
• На следующем уровне находятся теги, которые действительны в HTML, и правила, по которым теги могут быть вложены в теги.
• На следующем уровне находятся правила, по которым атрибуты действительны для тех тегов, языков, которые могут быть встроены в HTML, например CSS и JavaScript.
• Наконец, у вас есть семантические правила о том, что означает данный документ HTML.

Синтаксическая часть определена достаточно хорошо, чтобы ее можно было verified. Семантическая часть намного больше, чем синтаксическая, и определяется в терминах действий браузера в отношении HTTP и Document Object Model (DOM), и как модель должна отображаться на экране.

В конце:

• Анализ корректного HTML очень прост (он не содержит контекста и LL/LR).
• Разбор HTML, который действительно существует в Интернете, затруднен.
• Реализация семантики (браузера) над HTML/CSS/DOM крайне затруднительна.

Ответ 2

Valid HTML не является контекстно-свободным языком.

Прежде всего, HTML, являющийся приложением SGML, является фикцией для всех практических целей, поэтому анализ SGML для ответа на вопрос бесполезен. (Тем не менее, SGML-фикция, вероятно, также не является контекстно-зависимой.)

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

Если вы рассматриваете процесс разделения входного потока на токены, этот уровень языка HTML является регулярным (за исключением обратной связи от конструктора дерева).

Однако есть три сложности: первая заключается в том, что разделение входного потока на токены является первым, а затем создателем дерева, которое действительно заботится об идентификаторах в токенах. Второй заключается в том, что построитель деревьев возвращается обратно в токенизатор, так что некоторые переходы состояния, выполняемые токенизатором, зависят от состояния конструктора дерева! Третий заключается в том, что действительные документы на языке определяются правилами, которые применяются к выходу этапа построения дерева, и эти правила достаточно сложны, чтобы их нельзя было полностью определить с помощью древовидных автоматов (о чем свидетельствует RELAX NG, не являющийся выразительным достаточно, чтобы описать все ограничения на достоверность).

Это не фактическое доказательство, но вы, вероятно, можете разработать реальные доказательства, работая от осложнений № 2 и № 3.

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

Изменить: интересные вопросы, оставленные как упражнение для читателя:

Является ли HTML без ошибок синтаксического анализа, но игнорируя действительность без контекста?

Является ли HTML без ошибок синтаксического анализа и игнорирует общую достоверность, но только с допустимыми именами элементов разрешен контекстно-свободный язык?

(Осложнение № 2 применяется в обоих случаях.)

Ответ 3

НЕТ

См. раздел "Редактирование ниже"

Это зависит.

Если вы говорите о подмножестве, состоящем только из теоретического HTML, тогда да.

Если вы также включаете реальную жизнь, рабочий HTML, к которому обращаются и успешно используются миллионы людей ежедневно на многих из лучших сайтов в Интернете, тогда НЕТ.

Именно это дает гибкость HTML. Механизм синтаксического анализа добавляет теги, закрывает теги и заботится о материалах, которые теоретический CFG не может сделать. Если вы взяли автоматы, вы могли бы помнить, что правило производства в формальной грамматике не может быть пустым (aka epsilon/lambda) на lhs (левая сторона). Поскольку механизм синтаксического анализа в основном использует знания, которые не могут иметь формальные грамматики и автоматы, он не ограничен этим, а "грамматика" имеет epsilon/lambda -> result, где определенное правило эпсилон/лямбда выбрано на основе информации, недоступной в грамматике.

Так как я не думаю, что пустые lhs разрешены в любых формальных грамматиках, HTML не может быть определен формальной грамматикой и вообще не является формальным языком.

Конечно, HTML5 может попытаться перейти к "более формальному" описанию языка, но вероятность того, что он станет контекстно-свободным языком в действительности (т.е. строки, не соответствующие грамматике, отвергнуты) - это вероятность того, что XHTML 2.0 перенесет мир штурмом и полностью заменяет HTML (XHTML - это попытка сделать HTML формальным языком... он был отклонён в массе из-за его хрупкости).

Следует отметить тот факт, что HTML 5 - это ПЕРВЫЙ стандарт HTML, который должен быть определен до его реализации! Правильно, HTML 1-4 состоит из случайных идей, которые только что были реализованы в браузере, и были собраны в стандарты после факта, основанного на том, какие функции широко использовались и широко применяются. Затем они попробовали XHTML, который полностью не был принят. Даже "xhtml" в Интернете автоматически анализируется как HTML почти при любых обстоятельствах, чтобы предотвратить простое нарушение с критической синтаксической ошибкой. Теперь вы можете увидеть, как мы сюда попали, и почему это вряд ли будет оформлено в ближайшее время.

Урок: "Теоретически нет разницы между теорией и практикой. На практике это есть". - Йоги Берра

EDIT:

Собственно, после прочтения документов получается, что HTML, даже в соответствии со спецификацией HTML 4.01, фактически не соответствует SGML. Чтобы убедиться в этом, просмотрите определение типа документа HTML 4.01 (doctype) в http://www.w3.org/TR/html4/strict.dtd и обратите внимание на следующие строки:

Спецификация HTML 4.01 включает дополнительные     синтаксические ограничения, которые не могут быть выражены внутри     DTD.

Итак, я бы сказал, что из-за этих возможностей это, вероятно, не CFL (хотя технически это не опровергает гипотезу о наличии некоторого возможного КПК, который принимает HTML 4.01, он предотвращает аргумент, что SGML является CFL поэтому HTML является CFL).

HTML5 триггеры, отказаться от любого подразумеваемого соответствия SGML, но, по-видимому, можно описать CFG. Тем не менее, он по-прежнему будет обеспечивать эффективный синтаксический анализ не на основе cfg, так что IMO в текущей ситуации (то есть спецификация языка определяется формально, с недопустимыми строками, которые все еще принимаются, анализируются и визуализируются наилучшим образом), в этом отношении маловероятно резко меняются в течение долгого, долгого, долгого времени.

Ответ 4

HTML5 отличается от предыдущих версий HTML тем, что он строго определяет поведение синтаксического анализа кода, которое не совсем корректно. Пред-HTML5 парсеров различаются, и каждый делает все возможное, чтобы "угадать" намерение автора кода.