RSS
コード改革論・入門

本家「＠IT」にはない内容をエンジニアライフで技術紹介するコラム。広く議論する場になることを目指します。

第017回_構文の整理4_markupdecl

»

簡単な検討を要するもの2

前回に引き続き、LL (1)でない構文について検討します。

■AttlistDecl,AttDef
LL (1)で解析できないので、変形が必要です。
まずは単純に変形すると、
　AttlistDecl ::= SYMBOL ('<!ATTLIST') S Name AttDef* S? SYMBOL ('>')
　AttDef ::= S Name S AttType S DefaultDecl
になります。

問題点
問題箇所は、
　AttlistDecl上のAttDefが0回以上の繰り返しを持つ
　AttlistDecl上のAttDefの後ろにS?を持つ
　AttDef上先頭にSを持つ
ところです。この問題箇所によって、
　AttlistDeclでAttDef無しでSを書いた場合、
　これは必ずAttDefの先頭のSとして認識し、
　LL (1)の性質上、AttDefの構文が確定したものとみなします。
　よって、Nameの後ろにSがあり、AttDefなしの場合を正しく構文解析できません。

検討
整理するために、AttDefの繰り返し部分と最後のS?を展開してみましょう。

AttDefなし/SなしSYMBOL ('<!ATTLIST') S Name SYMBOL ('>')
AttDefなし/SSYMBOL ('<!ATTLIST') S Name S SYMBOL ('>')
AttDef1回/S?SYMBOL ('<!ATTLIST') S Name S AttType S DefaultDecl S? SYMBOL ('>')
AttDef2回/S?SYMBOL ('<!ATTLIST') S Name S AttType S DefaultDecl S AttType S DefaultDecl S? SYMBOL ('>')
ここで、
　AttDef ::= Name S AttType S DefaultDecl
と修正することによって
AttDefなし/SなしSYMBOL ('<!ATTLIST') S Name SYMBOL ('>')
AttDefなし/SSYMBOL ('<!ATTLIST') S Name S SYMBOL ('>')
AttDef1回/S?SYMBOL ('<!ATTLIST') S Name S AttDef
S? SYMBOL ('>')
AttDef2回/S?SYMBOL ('<!ATTLIST') S Name S AttDef S AttDef
S? SYMBOL ('>')
になります。
ここで方針としては、(S AttDef)* のような繰り返し表現をすればよさそうであると想像できます。

ただし、先程から述べているように(S AttDef)の句の後ろにS?を置くとLL (1)になりませんから、S?を(S AttDef)の句で表現することを考えることになります。
(S AttDef)の句で Sを表現するために、(S (AttDef)? ) を導入すると、
　AttlistDecl ::= SYMBOL ('<!ATTLIST') S Name (S (AttDef)? )* SYMBOL ('>')
　AttDef ::= Name S AttType S DefaultDecl
のように変形できます。ただし、AttListDeclは元の構文と完全に等価な構文ではありません。この構文がもたらす結果は、
　SYMBOL ('<!ATTLIST') S Name S+ AttDef S+ AttDef.....S+ AttDef S* SYMBOL ('>')
のように展開することになります。しかしながら、
　S ::= (#x20 | #x9 | #xD | #xA)+
ですから、字句解析器はS+は返さずに必ずSとして取得します。結局、
　SYMBOL ('<!ATTLIST') S Name S AttDef S AttDef.....S AttDef S? SYMBOL ('>')
と等価と扱っても問題ありません。

結果
クラス名整理した構文
EbnfAttlistDeclNodeAttlistDecl ::=
SYMBOL ('<!ATTLIST') S Name (S (AttDef)? )* SYMBOL ('>')
EbnfAttDefNodeAttDef ::= Name S AttType S DefaultDecl

■EntityDecl以下の構文
導入
LL (1)で解析できないので、変形が必要です。

まずは自動的な変換を行うと次のようになります。
　EntityDecl ::= GEDecl | PEDecl
　GEDecl ::= SYMBOL ('<!ENTITY') S Name S EntityDef S? SYMBOL ('>')
　PEDecl ::= SYMBOL ('<!ENTITY') S SYMBOL ('%') S Name S PEDef S? SYMBOL ('>')
さらに先頭の共通項を括りだすと、
　EntityDecl ::= SYMBOL ('<!ENTITY') S (GEDecl | PEDecl)
　GEDecl ::= Name S EntityDef S? SYMBOL ('>')
　PEDecl ::= SYMBOL ('%') S Name S PEDef S? SYMBOL ('>')
となります。
EntityDefのLL (1)化
　EntityDef ::= EntityValue | (ExternalID NDataDecl?)
はLL (1)で解析できないので、変形が必要です。
GeDeclにて、
　NDataDecl ::= S WORD ('NDATA') S Name
であることを考えると
EntityValueName S EntityValue SYMBOL ('>')
EntityValue SName S EntityValue S SYMBOL ('>')
ExtenralIDName S ExternalID SYMBOL ('>')
ExtenralID SName S ExternalID S SYMBOL ('>')
NDataDeclName S ExternalID S WORD ('NDATA') S Name SYMBOL ('>')
NDataDecl SName S ExternalID S WORD ('NDATA') S Name S SYMBOL ('>')
となり、ExternalID の後ろにSが来たとき、NDataDeclの解析を行おうとして、
　Name S ExternalID S SYMBOL ('>')
の場合に失敗します。そこでLL (1)化すると、
　EntityDef ::= (EntityValue S?) | ( ExternalID (S (WORD ('NDATA') S Name S?)? )? )
となります。さらに、
　GEDecl ::= Name S GeEntityDef SYMBOL ('>')
　GeEntityDef ::= GeInternalDef | GeExternalDef
　GeInternalDef ::= EntityValue S?
　GeExternalDef ::= ExternalID (S NDataDecl? )?
　NDataDecl ::= WORD ('NDATA') S Name S?
と整理できます。

クラス名整理した構文
EbnfEntityDeclNodeEntityDecl ::= SYMBOL ('<!ENTITY') S (GEDecl | PEDecl)
EbnfGEDeclNodeGEDecl ::= Name S GeEntityDef SYMBOL
EbnfGeEntityDefNodeGeEntityDef ::= GeInternalDef | GeExternalDef
EbnfGeInternalDefNodeGeInternalDef ::= EntityValue S?
EbnfGeExternalDefNodeGeExternalDef ::= ExternalID (S NDataDecl? )?
EbnfNDataDeclNodeNDataDecl ::= WORD ('NDATA') S Name S?
EbnfPEDeclNodePEDecl ::= SYMBOL ('%') S Name S PEDef S? SYMBOL ('>')

■doctypedecl
LL (1)で解析できないので変形が必要です。まずは自動的な変換を行うと次のようになります。
　doctypedecl ::= SYMBOL ('<!DOCTYPE') S Name (S ExternalID)?
　　　　　　　　　　S? (SYMBOL ('[') intSubset SYMBOL (']') S?)? SYMBOL ('>')
この問題点もAttlistDeclと同じで (S ExternalID)?とその後ろのS?でSが正しく認識できません。
問題部分だけ展開すると、
　　...　　　　　　　　(SYMBOL ('[') ...
　　... S　　　　　　　(SYMBOL ('[') ...
　　... S ExternalID　 (SYMBOL ('[') ...
　　... S ExternalID S (SYMBOL ('[') ...
となりますので、(S External S)を(S (ExternalID S?)? )? と変形すれば良いでしょう。
よって、
クラス名整理した構文
EbnfDoctypedeclNodedoctypedecl ::=
SYMBOL ('<!DOCTYPE') S Name
(S (ExternalID S?)? )?
(SYMBOL ('[') intSubset SYMBOL (']') S?)? SYMBOL ('>')
となります。

■element
LL (1)で解析できないので変形が必要です。まずは自動的な変換を行うと次のようになります。
　element ::= EmptyElemTag | ( STag content ETag )
　EmptyElemTag ::= SYMBOL ('<') Name (S Attribute)* S? SYMBOL ('/>')
　STag ::= SYMBOL ('<') Name (S Attribute)* S? SYMBOL ('>')
ですから、
　element ::= (SYMBOL ('<') Name (S Attribute)* S? SYMBOL ('/>') )
　　　　　| (SYMBOL ('<') Name (S Attribute)* S? SYMBOL ('>') content ETag )
となり、先頭の共通項を括りだすと、
クラス名整理した構文
EbnfElementNodeelement ::= SYMBOL ('<') Name (S Attribute)* S? ( SYMBOL ('/>') | ( SYMBOL ('>') content ETag) )
となります。

W3Cを詳しく読まないといけないもの

次のEBNF構文は読み解けない仕様を持っています。
　intSubset ::= ( markupdecl | DeclSep)*
　markupdecl ::= elementdecl | AttlistDecl | EntityDecl | NotationDecl | PI | Comment
　extSubsetDecl::= ( markupdecl | conditionalSect | DeclSep)*
　※EbnfConditionalSectNodeと循環参照が存在します。
　conditionalSect ::= includeSect | ignoreSect
　includeSect ::= SYMBOL ('<![') S? WORD ('INCLUDE') S? SYMBOL ('[') extSubsetDecl SYMBOL (']]>')
　ignoreSect ::= SYMBOL ('<![') S? WORD ('IGNORE') S? SYMBOL ('[') ignoreSectContents* SYMBOL (']]>')
これらを検討していくとかなり長くなりますので、意味解析の説明を行うときに検討します。
次回からは字句解析器・構文解析器を作っていきます。
0/1相転移炉 2017/05/15 10:00:00 Comment(0)

コメント

コメントを投稿する