第016回_構文の整理3_PITarget_Contentspec

ポイント1
まず呼び出し元となる、PIの構文が
　 PI::=SYMBOL ('<?') PITarget (S PI_WORD)? SYMBOL ('?>')
となっています。ここで、SYMBOL ('<?') PITargetの部分に注目します。
SYMBOLトークンは、
　SYMBOL ::= '#FIXED' | '#IMPLIED'| '#PCDATA' | '#REQUIRED'

となっており、太字部分の<?xmlと<?は異なるSYMBOLとして抽出する必要があります。方法は字句解析側で考えるとして、そのようなことが可能とすると<?に続くPITargetは xmlでない保証を持ちます。
# もし、<?xmlの並びならSYMBOL ('<?xml')として取得し、
# そうでない場合はSYMBOL ('<?')として取得するので
# SYMBOL ('<?')とWORD ('xml')に分解して取得することはありません。

ポイント2
次にPITargetの構文は
　[17] PITarget ::= Name − (('X' | 'x') ('M' | 'm') ('L' | 'l'))
ですので、
　PITargetはNameかつ、
　もし3文字の場合はxml,Xml,xMl,xmL,XMl,XmL,xML,XMLではいけない
ということを示しています。

contentspecのLL (1)でない部分について確認します。

例えば、
　SYMBOL ('<!ELEMENT') S WORD (name) S contentspec SYMBOL ('>')
の具体値
　<!ELEMENT data EMPTY >
　<!ELEMENT data ANY >
　<!ELEMENT data (#PCDATA) >
　<!ELEMENT data (data0 ) >
のとき、
　SYMBOL ('<!ELEMENT') S WORD ('data') S WORD ('EMPTY')
　 S SYMBOL ('>')
　→contentspec EMPTYを適用

　SYMBOL ('<!ELEMENT') S WORD ('data') S WORD ('ANY')
　 S SYMBOL ('>')
　→contentspec ANYを適用

　SYMBOL ('<!ELEMENT') S WORD ('data') S SYMBOL ('(')
　 SYMBOL ('#PCDATA') SYMBOL (')') S SYMBOL ('>')
　→contentspecからMixedに至り、後半の構文を適用

　SYMBOL ('<!ELEMENT') S WORD ('data') S SYMBOL ('(')
　 WORD (data0) SYMBOL (')') S SYMBOL ('>')
　→contentspecからchildrenを通じてseqを適用
と決定する必要があります。

しかし、contentspecの最初のトークンで考えると、
となり、SYMBOL ('(')を取得した場合に構文が確定しないのでLL (1)ではありません。

Mixedとchildrenの共通部分を括りだすと
　 contentspec ::= EMPTY | ANY | ( SYMBOL ('(') S? (Mixed | children) )
となります。
また、この修正により、
　Mixed ::= ( SYMBOL ('#PCDATA')
　　　　　　　　　(S? SYMBOL ('|') S? Name)* S?
　　　　　　　SYMBOL (')*')
　　　　　　)
　　　　　　| ( SYMBOL ('#PCDATA')　S? SYMBOL (')')　)
と修正します。childrenは先頭の非終端記号のchioceとseqを修整する必要があり、
　choice　　　::= cp ( S? SYMBOL ('|') S? cp )+ S? SYMBOL (')')
　seq　　　　 ::= cp ( S? SYMBOL (',') S? cp )* S? SYMBOL (')')
となります。さらに、choiceとseqはcpにもあるのでcpも影響を受けて、
　cp　　　　　::= (Name | (SYMBOL ('(') S? choice) | (SYMBOL ('(') S? seq))
　　　　　　　　　(SYMBOL ('?') | SYMBOL ('*') | SYMBOL ('+'))?
となります。
これでcontentspecはLL (1)の構文になりました。

Mixedの新しい構文を見ると、同じようにLL (1)でないことが判ります。
そこで、共通項を括りだすと、
　Mixed ::= SYMBOL ('#PCDATA')
　　　　　　(
　　　　　　　( (S? SYMBOL ('|') S? Name)* S? SYMBOL (')*') )
　　　　　　　| (　　　　　　　　　　　　　　S? SYMBOL (')')　)
　　　　　　)
となります。さらに後の説明のために非終端記号で構文を分離して。
　Mixed ::= SYMBOL ('#PCDATA') ( MixedA | MixedB )
　MixedA::= (S? SYMBOL ('|') S? Name)* S? SYMBOL (')*')
　MixedB::=　S? SYMBOL (')')
とします。

このMixedのLL (1)化は不十分です。なぜならSYMBOL ('#PCDATA')の次に来るトークンは、
となり、S を取得した場合に構文が確定せずLL (1)でないからです。
そこで、MixedAの
　　(S? SYMBOL ('|') S? Name)*
の繰り返し部分を0回から3回まで展開してみると、
※具体的にするために3回分展開してみます
・・・
となりますので、 X ::= SYMBOL ('|') S? Name S? とすると、
・・・
になります。
すると最終的に、
　MixedA　::= S? SYMBOL (')*')
　MixedA' ::= S? (SYMBOL ('|') S? Name S?)+ SYMBOL (')*')
に変形できます。
# 後の変形を考えて、MixedAとMixedA'は分けておきます

MixedBと並べると、
　MixedA ::= S? SYMBOL (')*')
　MixedA'::= S? (SYMBOL ('|') S? Name S?)+ SYMBOL (')*')
　MixedB ::= S? SYMBOL (')')
ですから、S?が共通項となり、
　Mixed　::= SYMBOL ('#PCDATA') S? (MixedA | MixedA' | MixedB)
　MixedA ::= SYMBOL (')*')
　MixedA'::= (SYMBOL ('|') S? Name S?)+ SYMBOL (')*')
　MixedB ::= SYMBOL (')')
となります。

単独のトークンになった非終端記号はさらに整理して、
　Mixed ::= SYMBOL ('#PCDATA') S?
　　　　　　　(SYMBOL (')') | SYMBOL (')*') | MixedElemContents)
　MixedElemContents ::= ( SYMBOL ('|') S? Name S? )+ SYMBOL (')*')
とします。

　children ::= (choice | seq) (SYMBOL ('?') | SYMBOL ('*') | SYMBOL ('+'))?
　choice ::= cp ( S? SYMBOL ('|') S? cp )+ S? SYMBOL (')')
　seq ::= cp ( S? SYMBOL (',') S? cp )* S? SYMBOL (')')
　cp ::= (Name | (SYMBOL ('(') S? choice) | (SYMBOL ('(') S? seq))
　　　　　　　　(SYMBOL ('?') | SYMBOL ('*') | SYMBOL ('+'))?
において、childrenの先頭はchoiceかseqのAlternative句をとり、
かつ、choiceとseqの最初のトークンはどちらもcpであり、続くトークンがRepetition句からなります。
つまり、childrenはLL (1)ではありませんので、LL (1)に変形してみます。
まず、choiceとseqのRepetition句を展開してcp周りを整理します。
choice ::=
・・・
seq ::=
・・・
となります。先頭のcp S? を除き繰り返し部分を抽出して
　choiceTerm ::= SYMBOL ('|') S? cp S?
　seqTerm　　::= SYMBOL (',') S? cp S?
を非終端記号とすると、
choice ::=
・・・
seq ::=
・・・
となりますので、
　choice ::= cp S? choiceTerm+ SYMBOL (')')
　seq　　::= cp S? seqTerm*　　SYMBOL (')')
に整理できます。よってchildrenの先頭のAlternative句は
　(choice | seq) ::= cp S? (choiceTerm+ | seqTerm*) SYMBOL (')')
となります。

さてchoiceTermの繰り返しが+でseqTermの繰り返しが*なのは、childrenで単項(cpだけからなる)の場合に、seqTerm側の構文を通るようにするためです。上記の(choice | seq)句では、単項のcpを括りだしているのでその必要はありません。よって
　(choice | seq) ::= cp S? (choiceTerm+ | seqTerm+)? SYMBOL (')')
のように変形して繰り返し記号をあわせます。

最終的に、
となります。

cpを整理します。
　cp ::= (Name | (SYMBOL ('(') S? choice) | (SYMBOL ('(') S? seq))
　　　　　　(SYMBOL ('?') | SYMBOL ('*') | SYMBOL ('+'))?
から、
　cp ::= (Name | ( SYMBOL ('(') S? (choice | seq) ) )
　　　　　　(SYMBOL ('?') | SYMBOL ('*') | SYMBOL ('+'))?
に変形して、さらにchildrenのLL (1)化で
　(choice | seq) ::= cp S? (choiceTerm+ | seqTerm+)? SYMBOL (')')
としたので、
　cp ::= (Name
　　　　| ( SYMBOL ('(') S? cp S? (choiceTerm+ | seqTerm+)? SYMBOL (')') )
　　　　　)
　　　　 (SYMBOL ('?') | SYMBOL ('*') | SYMBOL ('+'))?
となります。

cpは SYMBOL ('(')とSYMBOL (')')で囲んだ部分にchildrenを書くことができます。
そこで、共通項を
　modifier ::= (SYMBOL ('?') | SYMBOL ('*') | SYMBOL ('+'))?
とすると
になります。cpは次のように形を変えると、
　cp ::= (Name modifier)
　　　　 | (SYMBOL ('(') S? cp S? (choiceTerm+ | seqTerm+)? SYMBOL (')')
　　　　　modifier )
とでき、childrenを含みますから
　cp ::= (Name modifier) | ( SYMBOL ('(') S? children )
となります。非終端記号cpName,multiTermを導入すると、
　cp　　　　::= (cpName | multiTerm)
　cpName　　::= Name modifier
　multiTerm ::= SYMBOL ('(') S? children
になります。

multiTermは、開き括弧はあるのに、同じ構文に閉じ括弧がありません。
そこでchildrenとmultiTermを修正して括弧を同じ構文内に収めます。
　term ::= cp S? (choiceTerm+ | seqTerm+)?
とすると、
　multiTerm　::= SYMBOL ('(') S? term S? SYMBOL (')') modifier
　children　::= term S? SYMBOL (')') modifier
に整理できます。

modifierは説明するために必要だったので導入しましたが
実際は SYMBOL (')') modifierが連続する場合は、1つのトークンになります。※cpName用のmodifierは残ります。
よって、ここまでの検討を経て

| '#IMPLIED'
| '#PCDATA'
| '#REQUIRED'
| '%'
| '&#'
| '&#x'
| '&'
| '('
| ')'
| ')?' //追加
| ')*'
| ')+' //追加
| '*'
| '+'
| ','
| '/>'
| ';'
| '='
| '<'
| '</'
| '<?'
| '<?xml'
| '<!['
| '<![CDATA['
| '<!ATTLIST'
| '<!DOCTYPE'
| '<!ENTITY'
| '<!ELEMENT'
| '<!NOTATION'
| '>'
| '?'
| '?>'
| '['
| ']'
| ']]>'
| '|'