第038回_コンシュームドトークンマップ_抽象構文木_サブセット
»
今回は、今後の説明で使用する用語を定義します。
<Hoge>data</Hoge>
があった場合、EBNFデータツリーの
TokenManager#consumeTokenを実施して結果がtrueになるノードとその親ノードだけを抜き出したものを
コンシュームドトークンマップ(Consumed Token Map)
と呼ぶことにします。
#
# 巡回したノードという意味ではfalseになるノードも巡回していますが
# それらは示しません。
# またSequence等の基本ノードとSノードは表示しません。
#
#
# コンシュームドドークン"ツリー"のほうが適当かもしれません。
# ただし、既にEBNFデータツリーや抽象構文木といったツリー/木の名称が付く用語が
# 頻出しているので混同を防ぐために
# trueの部分だけをマッピングしたという意味で
# "マップ"という名称にします。
#
1.構文(EBNFで定義したもの)
2.(具象)構文木
3.抽象構文木
それぞれについて以下に説明します
■木構造
コンシュームドトークンマップ(Consumed Token Map)
XML文書のcontentに<Hoge>data</Hoge>
があった場合、EBNFデータツリーの
EbnfContentNode
+EbnfElementNode
+EbnfSTagNode
+EbnfSymbolNode('<')
+EbnfNameNode(取得した文字列:Hoge)
+EbnfSymbolNode('>')
+EbnfContentNode
+EbnfElementNode
+EbnfCharDataNode(取得した文字列:data)
+EbnfETagNode
+EbnfSymbolNode('</')
+EbnfNameNode(取得した文字列:Hoge)
+EbnfSymbolNode('>')
のように、EBNFデータツリー上の+EbnfElementNode
+EbnfSTagNode
+EbnfSymbolNode('<')
+EbnfNameNode(取得した文字列:Hoge)
+EbnfSymbolNode('>')
+EbnfContentNode
+EbnfElementNode
+EbnfCharDataNode(取得した文字列:data)
+EbnfETagNode
+EbnfSymbolNode('</')
+EbnfNameNode(取得した文字列:Hoge)
+EbnfSymbolNode('>')
TokenManager#consumeTokenを実施して結果がtrueになるノードとその親ノードだけを抜き出したものを
コンシュームドトークンマップ(Consumed Token Map)
と呼ぶことにします。
#
# 巡回したノードという意味ではfalseになるノードも巡回していますが
# それらは示しません。
# またSequence等の基本ノードとSノードは表示しません。
#
#
# コンシュームドドークン"ツリー"のほうが適当かもしれません。
# ただし、既にEBNFデータツリーや抽象構文木といったツリー/木の名称が付く用語が
# 頻出しているので混同を防ぐために
# trueの部分だけをマッピングしたという意味で
# "マップ"という名称にします。
#
抽象構文木
抽象構文木という代物が、色々とややこしいので整理しておきます。このコラムで出てくる木構造は1.構文(EBNFで定義したもの)
2.(具象)構文木
3.抽象構文木
それぞれについて以下に説明します
■木構造
1.構文(EBNFで定義したもの)
■抽象構文木の必要性
構文解析で説明した EBNFデータツリーで定義したものを指します。いうまでもなく木構造です。
2.(具象)構文木
構文にしたがって、各トークンを単純に木構造に変換したデータ要素。タグの開始"<"やETagなどの上位アプリケーションが使用しない冗長なデータを含みます。
3.抽象構文木
(具象)構文木から、冗長性を排除した木構造データ。一般的に(具象)構文木を一旦作成してから抽象構文木を作成せず、用途にあわせた抽象構文木を直接作成します。
(具象)構文木を使ってもXMLファイルを処理することができますが、(具象)構文木はデータ構造として冗長であるため、簡素にした抽象構文木を作った方が無駄がありません。
■抽象構文木の必要条件
(具象)構文木から無駄を省いたものが抽象構文木ですから、「冗長な抽象構文木」は「設計の不備」か「用途が絞りきれていない」と言えます。
※冗長性が存在する理由とその例
※冗長性が存在する理由とその例
構文の認識において必要だった情報が構文解析終了と同時に不要になるため冗長性が発生します。
例1:開始タグに対する、終了タグ
XMLのタグ<HOGE>というデータは(具象)構文木では、
[40] STag ::= '<' Name (S Attribute)* S? '>'
であるので(Attribueを説明のため割愛すると)
START_TAG
+LEFT_ANGLE
+NAME
+RIGHT_ANGLE
という構造になります
しかし、なんらかの処理をするにあたって、
START_TAG,LEFT_ANGLE,RIGHT_ANGLEのノードを
処理することはおそらくありません。(つまり冗長)
結局
TAG_NODE(m_name = HOGE)
とすればよいことがわかります。
#
# ETagも例1で不要であると説明済みなのでXMLの
# STAG_NODEではなく、TAG_NODEとして良いでしょう。
#
XMLの終了タグというのは、XMLのタグの範囲を示すものとして(認識するために)必要です。しかし、
構文解析が完了し、木構造に変換すると
その子ノードが範囲を示してくれるので
終了タグ ETag ::= SYMBOL ('</') Name S? SYMBOL ('>')
は木構造にする必要がありません。
例2:開始タグ内の不要な要素構文解析が完了し、木構造に変換すると
その子ノードが範囲を示してくれるので
終了タグ ETag ::= SYMBOL ('</') Name S? SYMBOL ('>')
は木構造にする必要がありません。
XMLのタグ<HOGE>というデータは(具象)構文木では、
[40] STag ::= '<' Name (S Attribute)* S? '>'
であるので(Attribueを説明のため割愛すると)
START_TAG
+LEFT_ANGLE
+NAME
+RIGHT_ANGLE
という構造になります
しかし、なんらかの処理をするにあたって、
START_TAG,LEFT_ANGLE,RIGHT_ANGLEのノードを
処理することはおそらくありません。(つまり冗長)
結局
TAG_NODE(m_name = HOGE)
とすればよいことがわかります。
#
# ETagも例1で不要であると説明済みなのでXMLの
# STAG_NODEではなく、TAG_NODEとして良いでしょう。
#
サブセットの仕様
XMLを特定の用途に限定して使う仕様のことをサブセットと呼びます。構文(生成規則)に出てくる内部サブセットや外部サブセットとは意味合いが違います。このサブセットの仕様に合わせて抽象構文木を作ります。
サブセットの仕様を明確にせず、何にでも通用しそうな抽象構文木を作ると「冗長な抽象構文木」になります。
今回のサブセットの仕様は次のものとします。
・W3C勧告の仕様を満たす(できるだけ、可能な範囲で)
・DTDのチェックをすべて行う(できるだけ、可能な範囲で)
・DOMっぽい抽象構文木を生成する(Visitorパターンのためのacceptインタフェースは追加する)
次回から、W3C勧告の仕様を満たすためにW3C勧告を基にXMLの知識について解説しつつ、仕様を整理します。ある程度の機能単位の仕様が明確になったらその都度、実装を行います。
サブセットの仕様を明確にせず、何にでも通用しそうな抽象構文木を作ると「冗長な抽象構文木」になります。
今回のサブセットの仕様は次のものとします。
・W3C勧告の仕様を満たす(できるだけ、可能な範囲で)
・DTDのチェックをすべて行う(できるだけ、可能な範囲で)
・DOMっぽい抽象構文木を生成する(Visitorパターンのためのacceptインタフェースは追加する)
次回から、W3C勧告の仕様を満たすためにW3C勧告を基にXMLの知識について解説しつつ、仕様を整理します。ある程度の機能単位の仕様が明確になったらその都度、実装を行います。