関連するいくつかの 質問を読んで、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はどうですか？
私は形式言語の概念に慣れていないので、ご容赦ください。そして、はい、私はウィキペディアの記事を読みました;）
Context Freeは、パーサーの実装に重要な意味を持つ言語理論の概念です。Context Free Languageは、 Context Free Grammarによって記述できます。これは、すべてのルールの矢印の左側に単一の非終端記号があるものです。
X→δ
その単純な制限によりX、前後に関係なく、左側に表示されるルールの右側に置き換えることができます。たとえば、導出または解析中に次の値に到達した場合:
αXλ
1つはそれを確信しています
αδλ
も有効です。非コンテキストフリー ルールの例は次のとおりです。
XY→δ
Xa→δ
aX→δ
それらは、ルールが適用されるかどうかを判断するために周囲に何が導出できるかを知る必要がありX、それは非決定論につながります（周りXにあるものは、それが何に導出されるかを知りたがります）。私たちは言語を明確に定義したいと考えています。
言語が文脈自由であることを証明する唯一の方法は、その言語に文脈自由文法があることを証明することですが、これは簡単な作業ではありません。登場するほとんどのプログラミング言語は、すでに CFG によって記述されているため、作業は完了です。しかし、プログラミング言語など、ロジックや平易な英語を使用して記述されている言語が他にもあるため、それらが文脈自由であるかどうかを確認する作業が必要です。
HTML の場合、コンテキストの自由に関する答えはイエスです。SGML は明確に定義された Context Free Language であり、その上に定義された HTML も CFL です。両方の言語のパーサーと文法は Web 上にたくさんあります。いずれにせよ、有効な HTML にLL (k) 文法が存在するということは、言語が文脈自由であることの十分な証拠です。LL は CF の証明済みのサブセットだからです。
しかし、Web の存続期間中に HTML が進化した方法により、ブラウザーは HTML をそれほど明確に定義されていないものとして扱うことを余儀なくされました。最新の Web ブラウザーは、見つけたほとんどすべてのものから適切なものをレンダリングしようと、あらゆる手段を講じます。彼らが使用する文法は CFG ではなく、パーサーは SGML/HTML に必要なものよりもはるかに複雑です。
HTML はいくつかのレベルで定義されています。
<tags>次のレベルは XML で、階層的なドキュメント構造を定義するオープニングとクロージングで構成されます。Apache Antビルド スクリプトの場合と同様に、XML または XML に似たものを任意の目的に使用できます。構文部分は、検証できるほど十分に定義されています。セマンティック部分は構文部分よりもはるかに大きく、HTTP とドキュメント オブジェクト モデル(DOM) に関するブラウザー アクション、およびモデルを画面にレンダリングする方法に関して定義されます。
最終的には：
有効な HTML は文脈自由言語ではありません。
まず第一に、HTML が SGML のアプリケーションであるということは、実用的な目的からすればフィクションであり、質問に答えるために SGML を分析しても意味がありません。(ただし、SGML フィクションもおそらく文脈自由ではありません。)
実際に定義された HTML 構文解析アルゴリズムを見ると、さらに役に立ちます。トークン化とツリー構築の 2 つのレベルで機能します。HTML がトークン化と呼ぶものは、パーサーについて話すときに通常トークン化と呼ばれるものよりも高レベルの操作です。HTML の場合、トークン化は文字のストリームを開始タグ、終了タグ、コメント、テキストなどの単位に分割します。トークナイザーは文字参照を拡張します。通常、パーサーについて話すとき、小なり記号のようなものを「トークン」として扱い、文字参照はトークナイザーによって解決されるのではなく、トークンで構成されると考えるでしょう。
入力ストリームをトークンに分割するプロセスを考慮すると、HTML 言語のそのレベルは通常です (ツリー ビルダーからのフィードバックを除く)。
ただし、複雑な点が 3 つあります。最初の 1 つは、入力ストリームをトークンに分割することは最初の 1 つであり、その後、トークン内の識別子を実際に気にするツリー ビルダー側が存在することです。2 つ目は、ツリー ビルダーがトークナイザーにフィードバックするため、トークナイザーによって行われる一部の状態遷移がツリー ビルダーの状態に依存することです。3 つ目は、言語内の有効なドキュメントは、ツリー ビルダー ステージの出力に適用されるルールによって定義され、それらのルールは非常に複雑であるため、ツリー オートマトンを使用して完全に定義することはできません (RELAX NG が表現力がないことからも明らかです)。すべての妥当性制約を説明するのに十分です)。
これは実際の証明ではありませんが、複雑な問題 2 と 3 から作業することで、実際の証明を作成できる可能性があります。
無効なドキュメントのケースは、言語が文脈自由であるかどうかの問題として特に興味深いものではないことに注意してください。構文解析木が何らかの理解可能な解釈を持っているかどうかに関係なく、すべての可能な文字列を生成する文脈自由文法が存在するという意味です。 HTMLパーサーが生成するツリーに関して。HTML パーサーは可能なすべての文字列を正常に消費するため、その意味で、可能なすべての文字列は「無効な HTML」言語になります。
編集: 読者への演習として残されている興味深い質問:
構文解析エラーのない HTML は妥当性を無視して文脈自由言語ですか?
解析エラーがなく、一般的な有効性を無視する HTML は、有効な要素名のみが許可されているコンテキストフリー言語ですか?
(複雑な問題 #2 はどちらの場合にも当てはまります。)
以下の編集を参照してください
場合によります。
理論上の HTML のみで構成されるサブセットについて話している場合は、はい.
インターネット上の多くのトップサイトで毎日何百万人もの人々がアクセスし、正常に使用している実際の作業 HTML も含める場合は、NO .
それが HTML の柔軟性を提供するものです。解析エンジンは、タグを追加し、タグを閉じ、理論上の CFG ではできないことを処理します。オートマトンを使用した場合、正式な文法のプロダクション ルールを lhs (左側) で空 (別名イプシロン/ラムダ) にすることはできないことを覚えているかもしれません。解析エンジンは基本的に、正式な文法とオートマトンが持つことができない知識を使用しているため、それによって制限されることはなく、「文法」にはepsilon/lambda -> result、文法で利用できない情報に基づいて特定のイプシロン/ラムダ規則が選択される場所があります。 .
形式文法では空の lh が許可されていないと思うので、HTML は形式文法で定義することはできず、形式言語ではありません。
確かに、HTML5 は「より正式な」言語記述に移行しようとする可能性がありますが、実際にそれが文脈自由言語になる可能性 (つまり、文法に一致しない文字列が拒否される可能性) は、XHTML 2.0 が世界を席巻する可能性とほぼ同じです。 HTML を完全に置き換えます (XHTML は、HTML を正式な言語にしようとする試みです...その脆弱性のために一斉に拒否されました)。
注目に値するのは、HTML 5 が実装前に定義された最初の HTML 標準であるという事実です! そうです、HTML 1-4 は、誰かがブラウザに実装したばかりのランダムなアイデアで構成されており、一般的に使用され、広く実装されている機能に基づいて、事後に標準に集められました。その後、XHTML を試してみましたが、まったく採用されませんでした。Web 上の 'xhtml' でさえ、ほとんどすべての状況で HTML として自動的に解析され、暗号化された構文エラーで問題が発生するのを防ぎます。これで、私たちがどのようにしてここにたどり着いたのか、そしてなぜすぐに正式化される可能性が低いのかがわかります.
教訓：「理論上、理論と実践の間に違いはありません。実際には違いがあります。」- ヨギ・ベラ
編集：
実際、ドキュメントを読んでみると、HTML 4.01 仕様に従っても、HTML は実際には SGML に準拠していないことがわかります。自分で確認するには、http://www.w3.org/TR/html4/strict.dtd で HTML 4.01 Strict ドキュメント タイプ定義 (doctype) を表示し、次の行に注意してください。
HTML 4.01 仕様には、DTD 内で表現できない追加の構文上の制約が含まれています。
したがって、これらの機能のためにおそらくCFL ではないと思います (技術的には、HTML 4.01 を受け入れる可能性のある PDA が存在するという仮説を反証するものではありませんが、SGML は CFL であり、したがって HTML はCFL)。
HTML5 フリップフロップ。暗黙の SGML への準拠を放棄しますが、おそらく CFG によって記述可能です。ただし、それでも cfg に基づかないベストエフォートの解析を提供するため、IMO の現在の状況 (つまり、言語仕様は正式に定義されており、無効な文字列は引き続き受け入れられ、解析され、ベスト エフォート方式でレンダリングされます) は、この点に関して、そうではない可能性があります。長い、長い、長い間劇的に変化します。
HTML5は、完全に正しくないコードの解析動作を厳密に定義するという点で、以前のHTMLバージョンとは異なります。HTML5以前のパーサーはさまざまであり、それぞれがコード作成者の意図を「推測」するために最善を尽くしています。