構文解析の前の字句解析

ゲームに簡単なプログラムを組み込むためにスクリプト言語とそれを実行するインタープリタをC++で作ってしまおうというコーナーです。
構文解析を一度にやってしまうのが思ったより大変だったので、その前段階として字句解析を試みます。

• 字句解析
• マイクロ構文

字句解析

前回は頑張って手動でBNFから簡単な計算式を解析をしようとして見事に撃沈していました。
そもそも、15が数字かどうかとか、そういうのは構文とか、そういうのより一段階前のような気がするのです。
つまり、この数字が周りと関係してどんな風に計算されるかとか、そういうことをする前に、「これは数字だ！」「これは足し算記号だ！」みたいに、文字に意味を与える段階が必要なのです。
「これは15という数字"である"かもしれません」と「この+は足し算を"している"かもしれません」の、"である"と"している"を分けて考えようと、そういうわけです。
何事も一気に全てやろうとするより、ある程度の段階に分けて事を進めたほうが順調に行くときがあるのです。
この一段階前の、「何であるか」という解析を字句解析といい、その後の「何をするか」という解析を構文解析というんです。たぶん

えっと、色々わかりにくい言い方ですみません。
字句解析の必要性を言葉に表すのが意外に大変だったもので…。
たぶんそのうち忘れられた頃に文面が改善されているかもしれません。

で、ですね。字句解析と構文解析には結構大きな違いがありまして。
例えば「-」が出てきたら、引き算ということはわかりますが、何を引けばいいのかは結構先まで調べなければわかりません。
しかし、「15」などの数字であればここから先は数字じゃないとわかる場所まで見れば他の場所で何がどんな意味を持ってどんな動作をしているかなんて関係ないのです。

例によって「15+7-2-2-(2+3)*12/(14-4)」を使って見てみます。
例えば、真ん中へんにある「*」を見てみると、「*」を見ただけでそれが掛け算記号であることは明らかですが、何と何を掛けているか、というのは、その記号の周りを見てやらなければわからないわけです。
この場合、掛け算記号であることを調べるのが字句解析で、どれとどれを掛けているかを調べるのが構文解析というわけです。
うろ覚えなんですが、この見る範囲の違いでマイクロ構文・マクロ構文といったりすることもあるようです。

マイクロ構文

最終的にはこんな数式じゃなくてPerlとかPHPっぽいオリジナル言語を解析したいわけですが、まだしばらくは簡単な数式を例にとって考えていきます。
とりあえず前回のごとく書いてみます。

(1) 数字 ::= '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'
(2) 非ゼロ数字 ::= '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'
(3) 数 ::= '0' | 非ゼロ数字 数字*
(4) 加減記号 ::= '+' | '-'
(5) 乗除記号 ::= '*'| '/'
(6) 開き括弧 ::= '('
(7) 閉じ括弧 ::= ')'

えっと、詳しい過程は省きますが、これを使って「15+7-2-2-(2+3)*12/(14-4)」を解析すると、「数字 加減記号 数字 加減記号 数字 加減記号 数字 加減記号 開き括弧 数字 加減記号 数字 閉じ括弧 乗除記号 数字 乗除記号 開き括弧 数字 加減記号 数字 閉じ括弧」となるわけです。
激しく長くなりました！
まあ、実際にはコンピュータにとって都合の良い数値が「数字」とか「加減記号」とかの代わりに使われるんですから、別にいいんでしょう。

…続く。