おはこんばんちは。 尾藤 a.k.a. BTOです。
普段我々開発者は、プログラミング言語を使ってシステムを開発しています。 しかし、プログラミング言語も人によって開発されたコンピュータプログラムです。
先日社内勉強会で、普段使っているプログラミング言語が、どういう仕組みで成り立っているのかを発表しました。 それで実際に簡単な四則演算を計算する簡単な電卓を実装してみました。 ソースコードを公開していますので、最初のとっかかりの参考程度にはなるかと思います。
正規文法・文脈自由文法
ノーム・チョムスキーという有名な言語学者が形式言語の生成文法を定式化しました(チョムスキー階層)。 彼は生成規則の制限の強さによって、階層を分けました。 制限は緩ければ緩いほど、言語としての表現力は上がりますが、解析は難しくなります。 このチョムスキー階層の中で、我々が慣れ親しんでいるのが、正規文法と文脈自由文法です。
正規文法は名前から連想される通り、正規表現に使用されている文法です。
文脈自由文法は、我々が普段使用しているプログラミング言語を定義するのに使用されている文法です。 文脈自由文法は、文脈の前後によって意味が変わることはありませんので、解析している部分だけ生成規則に合っているかどうかを気にするだけで処理できるようになっています。 例えば我々が普段会話で使用している自然言語は、前後の単語によって意味が変わったりしますので、文脈自由文法ではありません。 文脈自由文法でない言語は、常に前後の文脈の状態を気にしないといけなくなりますので、解析処理が複雑になってしまいます。
プログラミング言語は、コンピュータにとって都合よく処理できた方が設計は楽になりますので、文脈自由文法が採用されています。
字句解析・構文解析
形式言語の解析は、大きく分けて2つに分かれます。 1つが字句解析で、もう1つが構文解析です。
その名の通り、入力された文字列から字句(トークン)を抜き出すのが字句解析です。 字句解析器は抜き出したトークンを順番に構文解析器に渡していきます。
構文解析器は受け取ったトークンが定義された生成規則に合っているかどうかを判定します。 あってなければ構文エラーになり、あっていれば合致した構文に対応した処理を実行していきます。
字句解析
入力された文字列をトークンに分割する処理が字句解析です。 プログラミング言語でいうところの、if, for, {, }のような意味のあるトークンが抜き出されます。 通常は字句解析の段階で、余分な空白文字や改行は無視されます。 これにより、空白文字や改行があってもなくても、プログラミング言語として問題なく処理できるようになっています。
字句解析を行うための字句解析器を生成するツールはいろいろありますが、一番有名なのは lex というツールです。 lex は UNIXでコンパイラを作成するために開発されました。 なんと lex の開発者の一人は、Googleの元CEOのエリック・シュミットなんですね。
現在では、オリジナルの lex が使われることはほとんどなくて、GNU による拡張版である flex が使われることが多いです。
lex(flex)
lex(flex)は指定されたフォーマットにしたがって字句解析を定義すると、C言語で書かれた字句解析器を生成してくれます。 開発者は lex で自動生成されたプログラムを組み込むことで、コンパイラを作成することができます。
lex での字句解析器の定義をとても簡単で、字句を取り出す正規表現にたいして、C言語の処理を記述していくだけです。
正規表現 {
// Cのプログラム
}
正規表現 {
// Cのプログラム
}
こちらは今回作った計算機プログラムで実際に使われている lex ファイルの中身です。
[0-9]+ { yylval = atoi(yytext); return NUMBER; } [-+*/()=\n] { return *yytext; } [ \t]+ ; /* ignore whitespace */
0-9で構成された文字は数字として認識するので、NUMBERを返し、文字列を整数に変換した値を格納しています。 細かい記号類は面倒なので、そのまま返します。 最後の行で、無駄なスペースを読み飛ばしています。正確にはトークンとして認識していますが、何も処理しないようになっています。
バッカス・ナウア記法(BNF)
次に構文解析に進む前に、バッカス・ナウア記法(BNF)について説明します。 BNFはジョン・バッカスとピーター・ナウアの2人名前からついています。 2人とも偉大な計算機科学者で、共にチューリング賞を受賞しています。 2人によって考案された BNF は、文脈自由文法を記述するのに使われます。
BNF では(非)終端記号に対して、その生成規則を再帰的に定義することによって、文脈自由文法を定義します。 例えば、次のように(非)終端記号を生成する非終端記号列で定義していきます。 生成規則は複数存在することもあり、それぞれの生成規則は | で区切ります。
<symbol> ::= <symbol1> <symbol2> | <symbol2>
再帰的定義
プログラムを書いているなら、再帰処理はお馴染みだと思います。 再帰処理では、その関数の中で自分自身を呼び出します。 文脈自由文法の定義でも再帰は利用されていて、繰り返し現れるような構文規則は、再帰的定義を使って定義されます。
四則演算
試しに四則演算を再帰的定義を用いて定義してみます。 結論から言うと、次のような定義になります。
<expr> ::= <term> | - <term> | <expr> + <term> | <expr> - <term> <term> ::= <factor> | <term> * <factor> | <term > / <factor> <factor> ::= ( <expr> ) | <number> <number> ::= 数値
ここで定義されている記号は次のようになります。
- 終端記号: 数値 + - * / ( )
- 非終端記号: expr term factor number
expr の定義をみると、生成規則の中に expr が現れていますので、これは再帰的定義になります。 同じように term の生成規則に term が使用されているのがわかります。
expr では加減算が定義されていて、再帰的に定義されていますので、何回演算が現れても大丈夫なように定義されています。 同じように term では乗除算が定義されています。 加減算と乗除算で定義が分かれているのは、演算の優先順位をつけるためです。
試しに 1 + 2 * (3 - 4) という計算式を上記の構文定義を用いて解析する場合を考えてみます。 構文解析の結果は次のようになります。
1+2*(3-4)<expr>
/ \
1<expr> 2*(3-4)<term>
| / \
1<term> 2<term> (3-4)<factor>
| | |
1<factor> 2<factor> 3-4<expr>
| | / \
1<number> 2<number> 3<expr> 4<term>
| |
3<term> 4<factor>
| |
3<factor> 4<number>
|
3<number>
最初の式は、
ここでわかりやすさのために、構文規則の上の方から考えていきましたが、実際には構文解析器にはトークンの一覧が渡されるので、実際の処理としては下の方から構文規則に適用していくイメージになります。
構文定義の例(CSS)
実際に身近で使われているものの文法定義を見てみましょう。 Webエンジニアにはお馴染みの CSS ですが、CSSの構文は次のように定義されています。
こちらは BNF ではなく、次に出てくる yacc での定義になっていますが、意味はほとんど同じなので問題なく読めると思います。 同じページには、字句解析の定義も載っていますね。こちらは、lex による定義と同じになっています。
yacc(bison)
構文解析にも字句解析と同じように専用ツールがあります。 yacc(Yet Another Compiler Compiler)と呼ばれるのがそれです。 yacc も lex と同じように、UNIX で構文解析器を生成するために開発されました。 その略称通り、コンパイラをコンパイルするためのツールです。
lex と同じように yacc 専用の定義ファイルを準備して yacc に書けると、構文解析用の C言語のソースファイルを出力します。 開発者は、出力されたソースコードを自分のソフトウェアに組み込んで、構文解析ができるようになります。
実際は yacc が直接使われることはほとんどなく、GNUの拡張版である bison が使われることがほとんどです。
BNF と全く同じ記号ではありませんが、意味的にはほとんど BNF と同じ記法で生成規則を定義していきます。 それぞれの生成規則に対して、具体的にどのような処理を行うのかを C言語で記述します。
yaccで四則演算
では、実際に yacc で四則演算を定義してみましょう。 yacc での四則演算は次のようになります。
expr : term
| '-' term { $$ = -$2; }
| expr '+' term { $$ = $1 + $3; }
| expr '-' term { $$ = $1 - $3; }
;
term : factor
| term '*' factor { $$ = $1 * $3; }
| term '/' factor { $$ = $1 / $3; }
;
factor : '(' expr ')' { $$ = $2; }
| NUMBER
;
先に紹介した、BNFでの定義をほとんど同じですね。 見ればわかると思いますが、それぞれの生成規則(演算)の部分で、計算結果を格納しているだけです。 これだけで、四則演算の定義が完結します。
0calc
以上のことを踏まえて、簡単な四則演算を行う計算機を実際に実装してみました。 プログラムはかなり最小限の構成にしてあるので、lex, yacc の動作を理解するのにはちょうどいいと思います。
できることは非常に少なくて
- 整数のみ扱える
- 四則演算のみ
- () は使える
といって機能だけあります。
では、実際にコンパイルして実行してみましょう。
% ./0calc 1 + 2 * (3 - 4) >> -1 0.1 .syntax error
ちゃんと計算できていますね。 しかし整数しか扱えないので、小数点とか入れても syntax error になってしまいますw
今回は我々が普段使っているプログラミング言語の解析の部分に焦点を当てて解説してみました。 使っているツールが違ってたり、自前で実装していたりと違いはありますが、字句解析と構文解析の2段構えになっているのはほとんど同じはずです。
自分が普段使っている言語が、どのように構文解析をしているのか調べてみるのもいいかもしれません。
まとめ
UUUMではハースストーンが流行っています。