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

» 2017/02/13

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

トークンの粒度

前回述べたように、字句解析は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やインターネット上の記載形式では、カンマをほとんど書きません。
例えば、非終端記号の名前として空白を含みたい場合は
　<代入文> ::= <変数> "=" <式>
　<<代入文>> ::= <<変数>> "=" <<式>>
のように、カンマを書くかわりに、<>や<<>>で非終端記号を囲むものもあります。
#
# 単語間をスペースで表現する英語などの言語では上記のような
# 回避策を講じることが多いです。
#

・選択

・繰り返し等のその他の表現

連接と選択だけあればほとんどの構文は表現できるのですが、同じものが何度も出現する部分については繰り返し表現を記述できます。
　{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の解説は以上となります。

0/1相転移炉 2017/02/13 10:00:00 Comment(0)

次の投稿へ

前の投稿へ