第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として表現すると
代入文 ::= 変数 "=" 式
となります。このような表現を「生成規則」または「構文」と呼びます。細かく見ていきましょう。
a = b+100;
というプログラムの代入文について考えてみましょう。
この文のプログラム的な意味は、
式(変数bに100を加算する)を変数aに代入する
という意味になります。
#
# もし、これが数学なら
# aはbに100加算したものと等しい
# という意味になります。
#
これをEBNFとして表現すると
代入文 ::= 変数 "=" 式
となります。このような表現を「生成規則」または「構文」と呼びます。細かく見ていきましょう。
・EBNFの定義の仕方、::=の記号、文字列の表現方法
1. ::= の左側に定義したいものを書きます。
2. ::= の右側に定義の内容を書きます。
3. ::= が左辺、右辺を別ける記号になります。
文法上にもし ::=が出ても混乱しないように、文法上の文字列は、"ダブルコーテーションか'シングルコーテーションで括ります。代入文で言えば"="の表現が該当します。
インターネット上のEBNFの記述の中には、::= と 後述する特別な記号以外はわざわざ ""で囲まないという場合もありますので注意してください。
2. ::= の右側に定義の内容を書きます。
3. ::= が左辺、右辺を別ける記号になります。
文法上にもし ::=が出ても混乱しないように、文法上の文字列は、"ダブルコーテーションか'シングルコーテーションで括ります。代入文で言えば"="の表現が該当します。
インターネット上のEBNFの記述の中には、::= と 後述する特別な記号以外はわざわざ ""で囲まないという場合もありますので注意してください。
・左辺に出現できるもの、非終端記号
先ほどの例で、"代入文" のような::=の左辺値を"非終端記号"と呼びます。逆に、左辺にこないものを"終端記号"と呼びます。
・右辺に出現できるものと連接
先ほどの例で 変数 , "=" . 式 は
変数：終端記号
"=" ：終端記号
式 : 非終端記号
に分類できます。ここから判ることは、右辺は終端記号と非終端記号の組み合わせで記述することです。
そして、並び順についても意味があり、順番を表す場合、その並びを「連接」と呼びます。通常、終端記号と非終端記号の区切りは空白を使い、もし空白自体を表す場合はUnicodeを使います。
区切りとして空白を使わない場合は、厳密に連接を ,(カンマ)で区切ります。
先ほどの例の連接をカンマで区切った場合、
代入文 ::= 変数 , "=" , 式
となります。ただし、RFCやインターネット上の記載形式では、カンマをほとんど書きません。
例えば、非終端記号の名前として空白を含みたい場合は
<代 入 文> ::= <変 数> "=" <式>
<<代 入 文>> ::= <<変 数>> "=" <<式>>
のように、カンマを書くかわりに、<>や<<>>で非終端記号を囲むものもあります。
#
# 単語間をスペースで表現する英語などの言語では上記のような
# 回避策を講じることが多いです。
#
変数：終端記号
"=" ：終端記号
式 : 非終端記号
に分類できます。ここから判ることは、右辺は終端記号と非終端記号の組み合わせで記述することです。
そして、並び順についても意味があり、順番を表す場合、その並びを「連接」と呼びます。通常、終端記号と非終端記号の区切りは空白を使い、もし空白自体を表す場合はUnicodeを使います。
区切りとして空白を使わない場合は、厳密に連接を ,(カンマ)で区切ります。
先ほどの例の連接をカンマで区切った場合、
代入文 ::= 変数 , "=" , 式
となります。ただし、RFCやインターネット上の記載形式では、カンマをほとんど書きません。
例えば、非終端記号の名前として空白を含みたい場合は
<代 入 文> ::= <変 数> "=" <式>
<<代 入 文>> ::= <<変 数>> "=" <<式>>
のように、カンマを書くかわりに、<>や<<>>で非終端記号を囲むものもあります。
#
# 単語間をスペースで表現する英語などの言語では上記のような
# 回避策を講じることが多いです。
#
・選択
プログラムの構文は、代入文以外にも文を持ちます。
その他の文を列挙すると、if文、if-else文、while文、for文 (他にもありますが割愛)となります。すると、
文 ::= 代入文 | if文 | if-else文 | while文 | for文
のように表現できます。ここで | はEBNFにおいて選択を意味します。これは正規表現と同じです。
その他の文を列挙すると、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回以下出現する
{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の解説は以上となります。
例)
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の勧告の中では正しくグループ化してない場合があります。
# そのあたりは適宜読み替えが必要です。