第006回_トークンを抽出する
»
これまで長い語りや既にソフトウェア工学を学んだ方にとっては当たり前の内容が多かったので、少し退屈だったかもしれません。
今回からはよりクリエイティブな内容になりますからご期待ください。
この点については次回のコラムで議論します。
#正しいかどうかは分かりません。
つまり、新言語の仕様においては
#インタプリタ型のパーサの仕様の場合はこうならないかもしれません。
今回からはよりクリエイティブな内容になりますからご期待ください。
XML構文における終端の抽出, 抽出方法について
■XMLの構文の問題と対処
XMLの構文は、
「EBNFを使って1文字単位の定義を行っている」
ので、字句解析が切り出すトークンとは上手くマッチしません。
この連載で定義する終端やトークン
と
XMLの定義する終端規則
は一致させません。
■構文を3つに分類する「EBNFを使って1文字単位の定義を行っている」
ので、字句解析が切り出すトークンとは上手くマッチしません。
このような1文字単位の定義のまま実装することは可能ですが、
構文解析を行おうとしたとき
そのトークンは1文字であり、
結局1文字ずつの構文解析することになり、
実装で検討しなければいけないことが細かすぎて
見通しが悪くなる
という問題が露見します。
この連載で定義する終端やトークン
と
XMLの定義する終端規則
は一致させません。
そこでXMLの構文を
1.トークンより細かい規則
2.トークンの規則(終端)
3.トークンの規則からなる規則(非終端)
に分類しながら、トークンの規則に対して適当なトークンを設定します。 分類手順は4つの工程からなります。
・手順1
トークンの規則からなる規則でも、他に出てこないトークンを持つ場合
があります。
例えば、
A ::= "<" B "/>"
というトークンの規則からなる規則があったとします。
このとき、Aの中にある、 "<" と "/>"は個別に切り出すトークンですが、A以外の生成規則に出てこなければ、これをAの生成規則からトークンとする作業が必要になります。
記号の集合であればSYMBOLトークン
文字の集合であればWORDトークン
とします。
・手順4
1.トークンより細かい規則
2.トークンの規則(終端)
3.トークンの規則からなる規則(非終端)
に分類しながら、トークンの規則に対して適当なトークンを設定します。 分類手順は4つの工程からなります。
・手順1
文字の集合を表す規則(1文字だけを指す規則)は、トークンより細かい規則とする。
・手順2
次に、
1文字以上の任意数を示すもの
(1文字を示すために"トークンより細かい規則"を含んでも良い)
かつ、
単一の規則からなるもの(非終端記号を含まないもの)
をトークンの規則とし、適当なトークンを設定する。
記号の集合であればSYMBOLトークン
文字の集合であればWORDトークン
とする。
・手順31文字以上の任意数を示すもの
(1文字を示すために"トークンより細かい規則"を含んでも良い)
かつ、
単一の規則からなるもの(非終端記号を含まないもの)
をトークンの規則とし、適当なトークンを設定する。
記号の集合であればSYMBOLトークン
文字の集合であればWORDトークン
とする。
最後に、残った規則をトークンの規則からなる規則とする。
また、トークンの規則からなる規則でも、他に出てこないトークンを持つ場合
があります。
例えば、
A ::= "<" B "/>"
というトークンの規則からなる規則があったとします。
このとき、Aの中にある、 "<" と "/>"は個別に切り出すトークンですが、A以外の生成規則に出てこなければ、これをAの生成規則からトークンとする作業が必要になります。
記号の集合であればSYMBOLトークン
文字の集合であればWORDトークン
とします。
・手順4
トークンの規則からなる規則中で非終端記号でないトークンを持つ場合、
記号の集合であればSYMBOLトークン
文字の集合であればWORDトークン
とする。
記号の集合であればSYMBOLトークン
文字の集合であればWORDトークン
とする。
手順に従ってトークンを抽出する
実際にトークンを抽出してみます。
[1] document ::= ( prolog element Misc* ) − ( Char* RestrictedChar Char* )
トークンの規則からなる規則と定義します。
[2] Char ::= [#x1−#xD7FF] | [#xE000−#xFFFD] | [#x10000−#x10FFFF]
文字を表す構文(1文字を表す構文)なので、トークンより細かい規則になります。
[2a] RestrictedChar ::= [#x1−#x8] | [#xB−#xC] | [#xE−#x1F]
[3] S::= (#x20 | #x9 | #xD | #xA)+
は1文字以上で他の非終端記号を含まないので、トークンの規則と言えます。
よって、WHITE_SPACEトークンを用意し、
WHITE_SPACE ::= (#x20 | #x9 | #xD | #xA)+
と定義します。
[4] NameStartChar ::= ":" | [A−Z] | "_" | [a−z] | [#xC0−#xD6]
[4a] NameChar::= NameStartChar | "−" | "." | [0−9]
[5] Name ::= NameStartChar (NameChar)*
は1文字以上で他の非終端記号を含まないので、トークンの規則と言えます。
NameCharはNameStartCharを含み、NameStartChar (NameChar)* は(NameChar)+ の部分集合です。
よって、WORDトークンを用意し、
WORD ::= (NameChar)+
と定義します。
[6] Names ::= Name (#x20 Name)*
トークンの規則からなる規則と定義します。
[7] Nmtoken ::= (NameChar)+
は1文字以上で他の非終端記号を含まないので、トークンの規則と言えます。ただし解析しようとすると、WORDトークンとなります。
[8] Nmtokens ::= Nmtoken (#x20 Nmtoken)*
トークンの規則からなる規則と定義します。
[9] EntityValue ::= '"' ([ˆ%&"] | PEReference | Reference)* '"'
| "'" ([ˆ%&'] | PEReference | Reference)* "'"
[10] AttValue ::= '"' ([ˆ<&"] | Reference)* '"'
| "'" ([ˆ<&'] | Reference)* "'"
[11] SystemLiteral ::= ('"' [ˆ"]* '"') | ("'" [ˆ']* "'")
EntityValue、AttValueを飛ばしてSystemLiteralをみると、1文字以上で他の非終端記号を含まないので、トークンの規則と言えます。
よって、LITERALトークンを用意し、
LITERAL ::= ('"' [ˆ"]* '"') | ("'" [ˆ']* "'")
と定義します。
すると、EntityValue、AttValueはLITERALで表現できます。
# EntityValueやAttValueは他の非終端を含み、問題があるので後で考えます。
[12] PubidLiteral ::= '"' PubidChar* '"' | "'" (PubidChar - "'")* "'"
は1文字以上で他の非終端記号を含まないので、トークンの規則と言えます。ただし解析しようとすると、LITERALトークンとなります。
[13] PubidChar::= #x20 | #xD | #xA | [a−zA−Z0−9]
[14] CharData ::= [ˆ<&]* − ([ˆ<&]* ']]>' [ˆ<&]*)
は1文字以上で他の非終端記号を含まないので、トークンの規則と言えます。
よって、CHARDATA_WORDトークンを用意し、
CHARDATA_WORD ::= [ˆ<&]* − ([ˆ<&]* ']]>' [ˆ<&]*)
と定義します。
[15] Comment ::= '<!−−' ((Char − '−') | ('−' (Char − '−')))* '−−>'
は1文字以上で他の非終端記号を含まないので、トークンの規則と言えます。
よって、COMMENTトークンを用意し、
COMMENT ::= '<!−−' ((Char − '−') | ('−' (Char − '−')))* '−−>'
と定義します。
[16] PI::='<?' PITarget (S (Char* − (Char* '?>' Char*)))? '?>'
は全体としてはトークンの規則からなる規則ですが、Char* − (Char* '?>' Char*)の部分は1文字以上で他の非終端記号を含まない規則なので、この部分をトークンの規則とします。
そこで、PI_WORDトークンを用意し、
PI_WORD ::= Char* − (Char* '?>' Char*)
と定義します。
# PI_WORDはWORDで表現できません。
#逆にPI_WORDはWORDを含むことができてしまうので問題があります。
#その点については後で議論します。
[17] PITarget ::= Name − (('X' | 'x') ('M' | 'm') ('L' | 'l'))
これはWORDに含みます。
[18] CDSect ::= CDStart CData CDEnd
トークンの規則からなる規則と定義します。
[19] CDStart ::= '<![CDATA['
は1文字以上で他の非終端記号を含まないので、トークンの規則と言えます。また、固定値で記号を含むためSYMBOLトークンと定義します。
[20] CData ::= (Char* − (Char* ']]>' Char*))
は1文字以上で他の非終端記号を含まないので、トークンの規則と言えます。
よって、CDATA_WORDトークンを用意し、
CDATA_WORD ::= Char* − (Char* ']]>' Char*)
と定義します。
[21] CDEnd ::= ']]>'
は1文字以上で他の非終端記号を含まないので、トークンの規則と言えます。また、固定値で記号を含むためSYMBOLトークンと定義します。
[22] prolog ::= XMLDecl Misc* (doctypedecl Misc*)?
トークンの規則からなる規則と定義します。
[23] XMLDecl ::= '<?xml' VersionInfo EncodingDecl? SDDecl? S? '?>'
トークンの規則からなる規則と定義します。尚、'<?xml' '?>'はSYMBOLトークンと定義します。
[24] VersionInfo ::= S 'version' Eq ("'" VersionNum "'" | '"' VersionNum '"')
トークンの規則からなる規則と定義します。 尚、'version'はWORDに含みます。
[25] Eq ::= S? '=' S?
トークンの規則からなる規則と定義します。
[26] VersionNum ::= '1.1'
は1文字以上で他の非終端記号を含まないので、トークンの規則と言えます。また、固定値で記号を含まないためWORDトークンに含めます。
[27] Misc ::= Comment | PI | S
トークンの規則からなる規則と定義します。
[28] doctypedecl ::= '<!DOCTYPE' S Name (S ExternalID)?
[28a] DeclSep ::= PEReference | S
[28b] intSubset ::= (markupdecl | DeclSep)*
[29] markupdecl ::= elementdecl | AttlistDecl | EntityDecl | NotationDecl
[31] extSubsetDecl ::= ( markupdecl | conditionalSect | DeclSep)*
はいずれもトークンの規則からなる規則と定義します。
[32] SDDecl ::= S 'standalone' Eq (("'" ('yes' | 'no') "'") | ('"' ('yes' | 'no') '"'))
トークンの規則からなる規則と定義します。尚、'standalone'はWORDに、"yes","no",'yes','no'はLITERALに含みます。
[39] element ::= EmptyElemTag | STag content ETag
トークンの規則からなる規則と定義します。
[40] STag ::= '<' Name (S Attribute)* S? '>'
トークンの規則からなる規則と定義します。尚、'<'はSYMBOLトークンと定義します。
[41] Attribute ::= Name Eq AttValue
トークンの規則からなる規則と定義します。
[42] ETag ::= '</' Name S? '>'
トークンの規則からなる規則と定義します。尚、'</'はSYMBOLトークンと定義します。
[43] content ::= CharData? ((element | Reference | CDSect | PI | Comment) CharData?)*
トークンの規則からなる規則と定義します。
[44] EmptyElemTag ::= '<' Name (S Attribute)* S? '/>'
トークンの規則からなる規則と定義します。尚、'/>'はSYMBOLトークンと定義します。
[45] elementdecl ::= '<!ELEMENT' S Name S contentspec S? '>'
はいずれもトークンの規則からなる規則と定義します。尚、'<!ELEMENT'はSYMBOLトークンと定義します。
[46] contentspec ::= 'EMPTY' | 'ANY' | Mixed | children
トークンの規則からなる規則と定義します。尚、'EMPTY','ANY'はWORDに含みます。
[47] children ::= (choice | seq) ('?' | '*' | '+')?
トークンの規則からなる規則と定義します。尚、'?','*','+'はSYMBOLトークンと定義します。
[48] cp ::= (Name | choice | seq) ('?' | '*' | '+')?
トークンの規則からなる規則と定義します。
[49] choice ::= '(' S? cp ( S? '|' S? cp )+ S? ')'
トークンの規則からなる規則と定義します。尚、'(' , '|' , ')'はSYMBOLトークンと定義します。
[50] seq ::= '(' S? cp ( S? ',' S? cp )* S? ')'
トークンの規則からなる規則と定義します。尚、','はSYMBOLトークンと定義します。
[51] Mixed ::= '(' S? '#PCDATA' (S? '|' S? Name)* S? ')*' | '(' S? '#PCDATA' S? ')'
トークンの規則からなる規則と定義します。尚、'#PCDATA', ')*'はSYMBOLトークンと定義します。
[52] AttlistDecl ::= '<!ATTLIST' S Name AttDef* S? '>'
トークンの規則からなる規則と定義します。尚、'<!ATTLIST'はSYMBOLトークンと定義します。
[53] AttDef ::= S Name S AttType S DefaultDecl
[54] AttType ::= StringType | TokenizedType | EnumeratedType
はいずれもトークンの規則からなる規則と定義します。
[55] StringType ::= 'CDATA'
は1文字以上で他の非終端記号を含まないので、トークンの規則と言えます。また、固定値で記号を含まないためWORDトークンに含めます。
[56] TokenizedType ::= 'ID' | 'IDREF' | 'IDREFS' | 'ENTITY' | 'ENTITIES'
[57] EnumeratedType ::= NotationType | Enumeration
トークンの規則からなる規則と定義します。
[58] NotationType ::= 'NOTATION' S '(' S? Name (S? '|' S? Name)* S? ')'
トークンの規則からなる規則と定義します。尚、'NOTATION' はWORDに含みます。
[59] Enumeration ::= '(' S? Nmtoken (S? '|' S? Nmtoken)* S? ')'
トークンの規則からなる規則と定義します。
[60] DefaultDecl ::= '#REQUIRED' | '#IMPLIED' | (('#FIXED' S)? AttValue)
トークンの規則からなる規則と定義します。尚、'#REQUIRED' , '#IMPLIED' , '#FIXED' はWORDトークンに含めます。
[61] conditionalSect ::= includeSect | ignoreSect
トークンの規則からなる規則と定義します。
[62] includeSect ::= '<![' S? 'INCLUDE' S? '[' extSubsetDecl ']]>'
トークンの規則からなる規則と定義します。尚、'INCLUDE' はWORDに含み、'<![' , ']]>'はSYMBOLトークンと定義します。
[63] ignoreSect ::= '<![' S? 'IGNORE' S? '[' ignoreSectContents* ']]>'
トークンの規則からなる規則と定義します。尚、'IGNORE' はWORDトークンに含めます。
[64] ignoreSectContents ::= Ignore ('<![' ignoreSectContents ']]>' Ignore)*
トークンの規則からなる規則と定義します。
[65] Ignore ::= Char* − (Char* ('<![' | ']]>') Char*)
は1文字以上で他の非終端記号を含まないので、トークンの規則と言えます。
よって、IGNORE_WORDトークンを用意し、
IGNORE_WORD ::= Char* − (Char* ('<![' | ']]>') Char*)
と定義します。
[66] CharRef ::= '&#' [0−9]+ ';' | '&#x' [0−9a−fA−F]+ ';'
トークンの規則からなる規則と定義します。尚、'&#' , ';' , '&#x'はSYMBOLトークンと定義します。
[67] Reference ::= EntityRef | CharRef
トークンの規則からなる規則と定義します。
[68] EntityRef ::= '&' Name ';'
トークンの規則からなる規則と定義します。尚、'&'はSYMBOLトークンと定義します。
[69] PEReference ::= '%' Name ';'
トークンの規則からなる規則と定義します。尚、'%'はSYMBOLトークンと定義します。
[70] EntityDecl ::= GEDecl | PEDecl
トークンの規則からなる規則と定義します。
[71] GEDecl ::= '<!ENTITY' S Name S EntityDef S? '>'
トークンの規則からなる規則と定義します。尚、'<!ENTITY'はSYMBOLトークンと定義します。
[72] PEDecl ::= '<!ENTITY' S '%' S Name S PEDef S? '>'
[73] EntityDef ::= EntityValue | (ExternalID NDataDecl?)
[74] PEDef ::= EntityValue | ExternalID
はいずれもトークンの規則からなる規則と定義します。
[75] ExternalID ::= 'SYSTEM' S SystemLiteral | 'PUBLIC' S PubidLiteral S SystemLiteral
[76] NDataDecl ::= S 'NDATA' S Name
[77] TextDecl ::= ''
[78] extParsedEnt ::= ( TextDecl? content ) − ( Char* RestrictedChar Char* )
トークンの規則からなる規則と定義します。尚、'SYSTEM' , 'PUBLIC', 'NDATA'はWORDに含みます。
[80] EncodingDecl ::= S 'encoding' Eq ('"' EncName '"' | "'" EncName "'" )
トークンの規則からなる規則と定義します。尚、'encoding'はWORDに含みます。
[81] EncName ::= [A−Za−z] ([A−Za−z0−9._] | '−')*
は1文字以上で他の非終端記号を含まないので、トークンの規則と言えますが、
EncodingDeclの構文によって、EncNameの両端がシングルクォートまたはダブルクォートで囲むため、解析しようとするとLITERALトークンとなります。
[82] NotationDecl ::= '<!NOTATION' S Name S (ExternalID | PublicID) S? '>'
トークンの規則からなる規則と定義します。尚、'<!NOTATION'はSYMBOLトークンと定義します。
[83] PublicID ::= 'PUBLIC' S PubidLiteral
トークンの規則からなる規則と定義します。
トークンの規則からなる規則と定義します。
[2] Char ::= [#x1−#xD7FF] | [#xE000−#xFFFD] | [#x10000−#x10FFFF]
文字を表す構文(1文字を表す構文)なので、トークンより細かい規則になります。
[2a] RestrictedChar ::= [#x1−#x8] | [#xB−#xC] | [#xE−#x1F]
| [#x7F−#x84] | [#x86−#x9F]
文字を表す構文(1文字を表す構文)なので、トークンより細かい規則になります。[3] S::= (#x20 | #x9 | #xD | #xA)+
は1文字以上で他の非終端記号を含まないので、トークンの規則と言えます。
よって、WHITE_SPACEトークンを用意し、
WHITE_SPACE ::= (#x20 | #x9 | #xD | #xA)+
と定義します。
[4] NameStartChar ::= ":" | [A−Z] | "_" | [a−z] | [#xC0−#xD6]
| [#xD8−#xF6] | [#xF8−#x2FF] | [#x370−#x37D]
| [#x37F−#x1FFF] | [#x200C−#x200D]
| [#x2070−#x218F] | [#x2C00−#x2FEF]
| [#x3001−#xD7FF] | [#xF900−#xFDCF]
| [#xFDF0−#xFFFD] | [#x10000−#xEFFFF]
文字を表す構文(1文字を表す構文)なので、トークンより細かい規則になります。| [#x37F−#x1FFF] | [#x200C−#x200D]
| [#x2070−#x218F] | [#x2C00−#x2FEF]
| [#x3001−#xD7FF] | [#xF900−#xFDCF]
| [#xFDF0−#xFFFD] | [#x10000−#xEFFFF]
[4a] NameChar::= NameStartChar | "−" | "." | [0−9]
| #xB7 | [#x0300−#x036F] | [#x203F−#x2040]
文字を表す構文(1文字を表す構文)なので、トークンより細かい規則になります。[5] Name ::= NameStartChar (NameChar)*
は1文字以上で他の非終端記号を含まないので、トークンの規則と言えます。
NameCharはNameStartCharを含み、NameStartChar (NameChar)* は(NameChar)+ の部分集合です。
よって、WORDトークンを用意し、
WORD ::= (NameChar)+
と定義します。
[6] Names ::= Name (#x20 Name)*
トークンの規則からなる規則と定義します。
[7] Nmtoken ::= (NameChar)+
は1文字以上で他の非終端記号を含まないので、トークンの規則と言えます。ただし解析しようとすると、WORDトークンとなります。
[8] Nmtokens ::= Nmtoken (#x20 Nmtoken)*
トークンの規則からなる規則と定義します。
[9] EntityValue ::= '"' ([ˆ%&"] | PEReference | Reference)* '"'
| "'" ([ˆ%&'] | PEReference | Reference)* "'"
[10] AttValue ::= '"' ([ˆ<&"] | Reference)* '"'
| "'" ([ˆ<&'] | Reference)* "'"
[11] SystemLiteral ::= ('"' [ˆ"]* '"') | ("'" [ˆ']* "'")
EntityValue、AttValueを飛ばしてSystemLiteralをみると、1文字以上で他の非終端記号を含まないので、トークンの規則と言えます。
よって、LITERALトークンを用意し、
LITERAL ::= ('"' [ˆ"]* '"') | ("'" [ˆ']* "'")
と定義します。
すると、EntityValue、AttValueはLITERALで表現できます。
# EntityValueやAttValueは他の非終端を含み、問題があるので後で考えます。
[12] PubidLiteral ::= '"' PubidChar* '"' | "'" (PubidChar - "'")* "'"
は1文字以上で他の非終端記号を含まないので、トークンの規則と言えます。ただし解析しようとすると、LITERALトークンとなります。
[13] PubidChar::= #x20 | #xD | #xA | [a−zA−Z0−9]
| [−'()+,./:=?;!*#@$_%]
文字を表す構文(1文字を表す構文)なので、トークンより細かい規則になります。[14] CharData ::= [ˆ<&]* − ([ˆ<&]* ']]>' [ˆ<&]*)
は1文字以上で他の非終端記号を含まないので、トークンの規則と言えます。
よって、CHARDATA_WORDトークンを用意し、
CHARDATA_WORD ::= [ˆ<&]* − ([ˆ<&]* ']]>' [ˆ<&]*)
と定義します。
[15] Comment ::= '<!−−' ((Char − '−') | ('−' (Char − '−')))* '−−>'
は1文字以上で他の非終端記号を含まないので、トークンの規則と言えます。
よって、COMMENTトークンを用意し、
COMMENT ::= '<!−−' ((Char − '−') | ('−' (Char − '−')))* '−−>'
と定義します。
[16] PI::='<?' PITarget (S (Char* − (Char* '?>' Char*)))? '?>'
は全体としてはトークンの規則からなる規則ですが、Char* − (Char* '?>' Char*)の部分は1文字以上で他の非終端記号を含まない規則なので、この部分をトークンの規則とします。
そこで、PI_WORDトークンを用意し、
PI_WORD ::= Char* − (Char* '?>' Char*)
と定義します。
# PI_WORDはWORDで表現できません。
#逆にPI_WORDはWORDを含むことができてしまうので問題があります。
#その点については後で議論します。
[17] PITarget ::= Name − (('X' | 'x') ('M' | 'm') ('L' | 'l'))
これはWORDに含みます。
[18] CDSect ::= CDStart CData CDEnd
トークンの規則からなる規則と定義します。
[19] CDStart ::= '<![CDATA['
は1文字以上で他の非終端記号を含まないので、トークンの規則と言えます。また、固定値で記号を含むためSYMBOLトークンと定義します。
[20] CData ::= (Char* − (Char* ']]>' Char*))
は1文字以上で他の非終端記号を含まないので、トークンの規則と言えます。
よって、CDATA_WORDトークンを用意し、
CDATA_WORD ::= Char* − (Char* ']]>' Char*)
と定義します。
[21] CDEnd ::= ']]>'
は1文字以上で他の非終端記号を含まないので、トークンの規則と言えます。また、固定値で記号を含むためSYMBOLトークンと定義します。
[22] prolog ::= XMLDecl Misc* (doctypedecl Misc*)?
トークンの規則からなる規則と定義します。
[23] XMLDecl ::= '<?xml' VersionInfo EncodingDecl? SDDecl? S? '?>'
トークンの規則からなる規則と定義します。尚、'<?xml' '?>'はSYMBOLトークンと定義します。
[24] VersionInfo ::= S 'version' Eq ("'" VersionNum "'" | '"' VersionNum '"')
トークンの規則からなる規則と定義します。 尚、'version'はWORDに含みます。
[25] Eq ::= S? '=' S?
トークンの規則からなる規則と定義します。
[26] VersionNum ::= '1.1'
は1文字以上で他の非終端記号を含まないので、トークンの規則と言えます。また、固定値で記号を含まないためWORDトークンに含めます。
[27] Misc ::= Comment | PI | S
トークンの規則からなる規則と定義します。
[28] doctypedecl ::= '<!DOCTYPE' S Name (S ExternalID)?
S? ('[' intSubset ']' S?)? '>'
トークンの規則からなる規則と定義します。尚、'<!DOCTYPE' , '[', ']' , '>'はSYMBOLトークンと定義します。[28a] DeclSep ::= PEReference | S
[28b] intSubset ::= (markupdecl | DeclSep)*
[29] markupdecl ::= elementdecl | AttlistDecl | EntityDecl | NotationDecl
| PI | Comment
[30] extSubset ::= TextDecl? extSubsetDecl [31] extSubsetDecl ::= ( markupdecl | conditionalSect | DeclSep)*
はいずれもトークンの規則からなる規則と定義します。
[32] SDDecl ::= S 'standalone' Eq (("'" ('yes' | 'no') "'") | ('"' ('yes' | 'no') '"'))
トークンの規則からなる規則と定義します。尚、'standalone'はWORDに、"yes","no",'yes','no'はLITERALに含みます。
[39] element ::= EmptyElemTag | STag content ETag
トークンの規則からなる規則と定義します。
[40] STag ::= '<' Name (S Attribute)* S? '>'
トークンの規則からなる規則と定義します。尚、'<'はSYMBOLトークンと定義します。
[41] Attribute ::= Name Eq AttValue
トークンの規則からなる規則と定義します。
[42] ETag ::= '</' Name S? '>'
トークンの規則からなる規則と定義します。尚、'</'はSYMBOLトークンと定義します。
[43] content ::= CharData? ((element | Reference | CDSect | PI | Comment) CharData?)*
トークンの規則からなる規則と定義します。
[44] EmptyElemTag ::= '<' Name (S Attribute)* S? '/>'
トークンの規則からなる規則と定義します。尚、'/>'はSYMBOLトークンと定義します。
[45] elementdecl ::= '<!ELEMENT' S Name S contentspec S? '>'
はいずれもトークンの規則からなる規則と定義します。尚、'<!ELEMENT'はSYMBOLトークンと定義します。
[46] contentspec ::= 'EMPTY' | 'ANY' | Mixed | children
トークンの規則からなる規則と定義します。尚、'EMPTY','ANY'はWORDに含みます。
[47] children ::= (choice | seq) ('?' | '*' | '+')?
トークンの規則からなる規則と定義します。尚、'?','*','+'はSYMBOLトークンと定義します。
[48] cp ::= (Name | choice | seq) ('?' | '*' | '+')?
トークンの規則からなる規則と定義します。
[49] choice ::= '(' S? cp ( S? '|' S? cp )+ S? ')'
トークンの規則からなる規則と定義します。尚、'(' , '|' , ')'はSYMBOLトークンと定義します。
[50] seq ::= '(' S? cp ( S? ',' S? cp )* S? ')'
トークンの規則からなる規則と定義します。尚、','はSYMBOLトークンと定義します。
[51] Mixed ::= '(' S? '#PCDATA' (S? '|' S? Name)* S? ')*' | '(' S? '#PCDATA' S? ')'
トークンの規則からなる規則と定義します。尚、'#PCDATA', ')*'はSYMBOLトークンと定義します。
[52] AttlistDecl ::= '<!ATTLIST' S Name AttDef* S? '>'
トークンの規則からなる規則と定義します。尚、'<!ATTLIST'はSYMBOLトークンと定義します。
[53] AttDef ::= S Name S AttType S DefaultDecl
[54] AttType ::= StringType | TokenizedType | EnumeratedType
はいずれもトークンの規則からなる規則と定義します。
[55] StringType ::= 'CDATA'
は1文字以上で他の非終端記号を含まないので、トークンの規則と言えます。また、固定値で記号を含まないためWORDトークンに含めます。
[56] TokenizedType ::= 'ID' | 'IDREF' | 'IDREFS' | 'ENTITY' | 'ENTITIES'
| 'NMTOKEN' | 'NMTOKENS'
は1文字以上で他の非終端記号を含まないので、トークンの規則と言えます。また、固定値で記号を含まないためWORDトークンに含めます。[57] EnumeratedType ::= NotationType | Enumeration
トークンの規則からなる規則と定義します。
[58] NotationType ::= 'NOTATION' S '(' S? Name (S? '|' S? Name)* S? ')'
トークンの規則からなる規則と定義します。尚、'NOTATION' はWORDに含みます。
[59] Enumeration ::= '(' S? Nmtoken (S? '|' S? Nmtoken)* S? ')'
トークンの規則からなる規則と定義します。
[60] DefaultDecl ::= '#REQUIRED' | '#IMPLIED' | (('#FIXED' S)? AttValue)
トークンの規則からなる規則と定義します。尚、'#REQUIRED' , '#IMPLIED' , '#FIXED' はWORDトークンに含めます。
[61] conditionalSect ::= includeSect | ignoreSect
トークンの規則からなる規則と定義します。
[62] includeSect ::= '<![' S? 'INCLUDE' S? '[' extSubsetDecl ']]>'
トークンの規則からなる規則と定義します。尚、'INCLUDE' はWORDに含み、'<![' , ']]>'はSYMBOLトークンと定義します。
[63] ignoreSect ::= '<![' S? 'IGNORE' S? '[' ignoreSectContents* ']]>'
トークンの規則からなる規則と定義します。尚、'IGNORE' はWORDトークンに含めます。
[64] ignoreSectContents ::= Ignore ('<![' ignoreSectContents ']]>' Ignore)*
トークンの規則からなる規則と定義します。
[65] Ignore ::= Char* − (Char* ('<![' | ']]>') Char*)
は1文字以上で他の非終端記号を含まないので、トークンの規則と言えます。
よって、IGNORE_WORDトークンを用意し、
IGNORE_WORD ::= Char* − (Char* ('<![' | ']]>') Char*)
と定義します。
[66] CharRef ::= '&#' [0−9]+ ';' | '&#x' [0−9a−fA−F]+ ';'
トークンの規則からなる規則と定義します。尚、'&#' , ';' , '&#x'はSYMBOLトークンと定義します。
[67] Reference ::= EntityRef | CharRef
トークンの規則からなる規則と定義します。
[68] EntityRef ::= '&' Name ';'
トークンの規則からなる規則と定義します。尚、'&'はSYMBOLトークンと定義します。
[69] PEReference ::= '%' Name ';'
トークンの規則からなる規則と定義します。尚、'%'はSYMBOLトークンと定義します。
[70] EntityDecl ::= GEDecl | PEDecl
トークンの規則からなる規則と定義します。
[71] GEDecl ::= '<!ENTITY' S Name S EntityDef S? '>'
トークンの規則からなる規則と定義します。尚、'<!ENTITY'はSYMBOLトークンと定義します。
[72] PEDecl ::= '<!ENTITY' S '%' S Name S PEDef S? '>'
[73] EntityDef ::= EntityValue | (ExternalID NDataDecl?)
[74] PEDef ::= EntityValue | ExternalID
はいずれもトークンの規則からなる規則と定義します。
[75] ExternalID ::= 'SYSTEM' S SystemLiteral | 'PUBLIC' S PubidLiteral S SystemLiteral
[76] NDataDecl ::= S 'NDATA' S Name
[77] TextDecl ::= ''
[78] extParsedEnt ::= ( TextDecl? content ) − ( Char* RestrictedChar Char* )
トークンの規則からなる規則と定義します。尚、'SYSTEM' , 'PUBLIC', 'NDATA'はWORDに含みます。
[80] EncodingDecl ::= S 'encoding' Eq ('"' EncName '"' | "'" EncName "'" )
トークンの規則からなる規則と定義します。尚、'encoding'はWORDに含みます。
[81] EncName ::= [A−Za−z] ([A−Za−z0−9._] | '−')*
は1文字以上で他の非終端記号を含まないので、トークンの規則と言えますが、
EncodingDeclの構文によって、EncNameの両端がシングルクォートまたはダブルクォートで囲むため、解析しようとするとLITERALトークンとなります。
[82] NotationDecl ::= '<!NOTATION' S Name S (ExternalID | PublicID) S? '>'
トークンの規則からなる規則と定義します。尚、'<!NOTATION'はSYMBOLトークンと定義します。
[83] PublicID ::= 'PUBLIC' S PubidLiteral
トークンの規則からなる規則と定義します。
抽出したトークンの整理
抽出したトークンについて、まとめると次のようになります。
WHITE_SPACE ::= (#x20 | #x9 | #xD | #xA)+
WORD ::= (":" | [A−Z]
LITERAL ::= '"' '"'以外の文字 '"' | "'" "'"以外の文字 "'"
SYMBOL ::= '#FIXED'
とりあえずの分類が終わりました。ただしこの分類のままではトークン同士に包含関係があります。WORD ::= (":" | [A−Z]
| "_"
| [a−z]
| [#xC0−#xD6]
| [#xD8−#xF6]
| [#xF8−#x2FF]
| [#x370−#x37D]
| [#x37F−#x1FFF]
| [#x200C−#x200D]
| [#x2070−#x218F]
| [#x2C00−#x2FEF]
| [#x3001−#xD7FF]
| [#xF900−#xFDCF]
| [#xFDF0−#xFFFD]
| [#x10000−#xEFFFF]
| "−"
| "."
| [0−9]
| #xB7
| [#x0300−#x036F]
| [#x203F−#x2040]
| [a−z]
| [#xC0−#xD6]
| [#xD8−#xF6]
| [#xF8−#x2FF]
| [#x370−#x37D]
| [#x37F−#x1FFF]
| [#x200C−#x200D]
| [#x2070−#x218F]
| [#x2C00−#x2FEF]
| [#x3001−#xD7FF]
| [#xF900−#xFDCF]
| [#xFDF0−#xFFFD]
| [#x10000−#xEFFFF]
| "−"
| "."
| [0−9]
| #xB7
| [#x0300−#x036F]
| [#x203F−#x2040]
)+
LITERAL ::= '"' '"'以外の文字 '"' | "'" "'"以外の文字 "'"
SYMBOL ::= '#FIXED'
| '#IMPLIED'
| '#PCDATA'
| '#REQUIRED'
| '%'
| '&#'
| '&#x'
| '&'
| '('
| ')'
| ')*'
| '*'
| '+'
| ','
| '/>'
| ';'
| '='
| '<'
| '</'
| '<?'
| '<?xml'
| '<!['
| '<![CDATA['
| '<!ATTLIST'
| '<!DOCTYPE'
| '<!ENTITY'
| '<!ELEMENT'
| '<!NOTATION'
| '>'
| '?'
| '?>'
| '['
| ']'
| ']]>'
| '|'
| '#PCDATA'
| '#REQUIRED'
| '%'
| '&#'
| '&#x'
| '&'
| '('
| ')'
| ')*'
| '*'
| '+'
| ','
| '/>'
| ';'
| '='
| '<'
| '</'
| '<?'
| '<?xml'
| '<!['
| '<![CDATA['
| '<!ATTLIST'
| '<!DOCTYPE'
| '<!ENTITY'
| '<!ELEMENT'
| '<!NOTATION'
| '>'
| '?'
| '?>'
| '['
| ']'
| ']]>'
| '|'
COMMENT ::= '<!−−' 連続した'−−'をもたない文字列 '−−>'
CDATA_WORD ::= (Char* − (Char* ']]>' Char*))
CHARDATA_WORD ::= [ˆ<&]* − ([ˆ<&]* ']]>' [ˆ<&]*)
IGNORE_WORD ::= Char* − (Char* ('<![' | ']]>') Char*)
PI_WORD ::= (Char* − (Char* '?>' Char*)この点については次回のコラムで議論します。
今後の言語設計のためのソフトウェア工学的な問題点
今回、XMLのパーサを検討するにあたってトークンの粒度をどのようにするかを検討していますが、既に世の中にたくさんのXMLパーサがあるのにこのような試行錯誤をしなければならなかったことを非常に情けなく思います。私は百年後の未来でも同じようなことをしていて良いとは思えません。このようなことはソフトウェア工学の内、コンパイラ理論とか言語設計論とかで必須要件にしておいて欲しいと思います。#正しいかどうかは分かりません。
つまり、新言語の仕様においては
言語の仕様
+LL (1)かどうか
字句解析レベルの仕様
構文解析レベルの仕様
を準備しておくと良いのではないでしょうか。+LL (1)かどうか
字句解析レベルの仕様
構文解析レベルの仕様
#インタプリタ型のパーサの仕様の場合はこうならないかもしれません。