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

第004回_字句解析_トークン粒度/EBNFについて

»

前回のコラムで
 字句解析、構文解析、意味解析
を作成すると述べましたので、字句解析から順に検討していきます。

トークンの粒度

前回述べたように、字句解析はtoken(トークン)を作成します。トークンは入力ストリームを適当な長さ(粒度)に分割したモノです。作成したトークンは構文解析にかけて、抽象構文木の終端ノード(以下、終端)と一致するか判定することなります。よって、トークンの分割粒度が構文解析の終端となっているべきです。このことは次のように考えてみるとわかります。
  • 分割粒度が終端より大きい場合、構文解析時に1トークンから2つ以上の終端が得られる。(場合がある)
  • 分割粒度が終端より小さい場合、構文解析時に2トークン以上から1つの終端が得られる。(場合がある)
どちらの場合も構文解析処理が複雑になるので、回避するためには字句解析のトークン粒度は構文解析の終端となっているのが良いことが判ります。

構文を定義するEBNF

XML構文の内容について吟味する前に、XMLの構文を定義するEBNFの表記法について説明します。対象読者をJavaのプログラムが書ける人としているので、今後のコラムで困らない程度の説明をします。詳しくはWikiや他の参考書をお読みください。

■なぜEBNF
ソフトウェア工学では、形式言語をEBNF(Extended Backus-Naur Form-拡張バッカスナウア記法)で記載するものが多くあります。XMLに関するW3Cの勧告もEBNFを使っています。

■EBNFの読み方
例えば、
 a = b+100;
というプログラムの代入文について考えてみましょう。
この文のプログラム的な意味は、
 式(変数bに100を加算する)を変数aに代入する
という意味になります。
#
#  もし、これが数学なら
#  aはbに100加算したものと等しい
# という意味になります。
#
これをEBNFとして表現すると
 代入文 ::= 変数 "=" 式
となります。このような表現を「生成規則」または「構文」と呼びます。細かく見ていきましょう。

EBNFの定義の仕方、::=の記号、文字列の表現方法
 1. ::= の左側に定義したいものを書きます。
 2. ::= の右側に定義の内容を書きます。
 3. ::= が左辺、右辺を別ける記号になります。
文法上にもし ::=が出ても混乱しないように、文法上の文字列は、"ダブルコーテーションか'シングルコーテーションで括ります。代入文で言えば"="の表現が該当します。
インターネット上のEBNFの記述の中には、::= と 後述する特別な記号以外はわざわざ ""で囲まないという場合もありますので注意してください。

左辺に出現できるもの、非終端記号
先ほどの例で、"代入文" のような::=の左辺値を"非終端記号"と呼びます。逆に、左辺にこないものを"終端記号"と呼びます。

右辺に出現できるものと連接
先ほどの例で 変数 , "=" . 式 は
 変数:終端記号
 "=" :終端記号
 式 : 非終端記号
に分類できます。ここから判ることは、右辺は終端記号と非終端記号の組み合わせで記述することです。
そして、並び順についても意味があり、順番を表す場合、その並びを「連接」と呼びます。通常、終端記号と非終端記号の区切りは空白を使い、もし空白自体を表す場合はUnicodeを使います。
区切りとして空白を使わない場合は、厳密に連接を ,(カンマ)で区切ります。
先ほどの例の連接をカンマで区切った場合、
 代入文 ::= 変数 , "=" , 式
となります。ただし、RFCやインターネット上の記載形式では、カンマをほとんど書きません。
例えば、非終端記号の名前として空白を含みたい場合は
 <代 入 文> ::= <変 数> "=" <式>
 <<代 入 文>> ::= <<変 数>> "=" <<式>>
のように、カンマを書くかわりに、<>や<<>>で非終端記号を囲むものもあります。
#
# 単語間をスペースで表現する英語などの言語では上記のような
# 回避策を講じることが多いです。
#

選択
プログラムの構文は、代入文以外にも文を持ちます。
その他の文を列挙すると、if文、if-else文、while文、for文 (他にもありますが割愛)となります。すると、
 文 ::= 代入文 | if文 | if-else文 | while文 | for文
のように表現できます。ここで | はEBNFにおいて選択を意味します。これは正規表現と同じです。

繰り返し 等のその他の表現
連接と選択だけあればほとんどの構文は表現できるのですが、同じものが何度も出現する部分については 繰り返し表現を記述できます。
 {A} : Aを任意数だけ繰り返す
 [A] : Aが0回か1回だけ出現する
厳密なEBNFは使い勝手が良くないので、次のように正規表現で表記することも多いです。
 A* : Aを0回以上繰り返す。
 A+ : Aを1回以上繰り返す。
 A? : Aが0回か1回だけ出現する
 A{x,y} : Aがx回以上y回以下出現する

グループ化
グループ化が必要なときがあるので実例をあげて考えましょう。
例)
 X ::= A | B C
があるとき、この意味は 
 終端X は A C または B Cを持つ
という意味になります。
もし、非終端X は A または B Cを持つ と表現したい場合、
 X ::= A | Y
 Y ::= B C
と間に非終端記号Yを挟む必要があります。
Yを挟むことは悪いことではないですが、Yなしで書きたい場合には、
 X ::= A | ( B C )
と括弧()で括ることで 選択や繰り返しの対象を複数の終端、非終端の並びに対して指定できます。
# W3Cの勧告の中では正しくグループ化してない場合があります。
# そのあたりは適宜読み替えが必要です。

おおざっぱですが、EBNFの解説は以上となります。
Comment(0)

コメント

コメントを投稿する