本家「@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 (']]>')
これらを検討していくとかなり長くなりますので、意味解析の説明を行うときに検討します。
次回からは字句解析器・構文解析器を作っていきます。
Comment(0)

コメント

コメントを投稿する