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

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

44 голосов
/ 03 марта 2011

Чтение некоторые связанные вопросы заставили меня задуматься о теоретической природе HTML.

Я не говорю о XHTML-подобномкод здесь.Я говорю о таких вещах, как этот сумасшедший фрагмент разметки, который является абсолютно правильным HTML (!) 

<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01//EN">
<html<head>
<title//
<p ltr<span id=p></span</p>
</>

Итак, учитывая огромную сложность, которую SGML внедряет здесь, является ли HTML языком без контекста?В любом случае это официальный язык?С грамматикой?

А как насчет HTML5?

Я новичок в концепции формальных языков, поэтому, пожалуйста, потерпите меня.И да, я прочитал статью в Википедии;)

Ответы [ 4 ]

53 голосов
/ 06 марта 2011

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

X→δ

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

αXλ

, можно быть уверенным, что 

αδλ

также допустимо.Примерами неконтекстно-свободных правил могут быть: 

XY→δ
Xa→δ
aX→δ

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

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

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

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

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

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

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

В конце:

  1. Парсинг правильного HTML чрезвычайно прост (он не зависит от контекста и LL / LR).
  2. Парсинг HTML, который фактически существует надВ Интернете сложно.
  3. Реализация семантики (браузера) через HTML / CSS / DOM чрезвычайно сложна.
14 голосов
/ 06 марта 2013

Действительный HTML не является контекстно-свободным языком.

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

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

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

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

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

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

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

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

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

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

10 голосов
/ 24 ноября 2011
нет

NO

См. Изменить ниже

Зависит.

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

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

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

Поскольку я не думаю, что в любых формальных грамматиках допустимы пустые 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 Strict (doctype) в http://www.w3.org/TR/html4/strict.dtd и обратите внимание на следующие строки:

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

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

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

4 голосов
/ 03 марта 2011

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

...