おはこんばんちは!! 尾藤 a.k.a. BTO です。

システムの開発をしていると、いろんな言語を使いますよね。 Webシステムなら、PHPとかHTMLとか。 CSSも立派な言語です。このように我々エンジニア(デザイナーにとっても)身近な言語は、いったいどのように処理されているのでしょうか。

今回は、我々が普段使っている形式言語の解析が、どのように行われているのかを書きたいと思います。

言語

では、まず言語というのはいったい何でしょうか? かなりざっくりとした質問で、答えはいろいろ出てきそうですが、ここでは自然言語と形式言語の2種類にカテゴライズします。

自然言語

自然言語というのは、人が会話したり、文章を書いたりする時に使われる言語です。日本語や英語、他にも何百種類という言語が存在すると思います。

何と言っても自然言語で一番厄介なのは、曖昧さです。明確な文法が存在せず、助詞や接続詞の優先順位も定まっていません。その為、コンピュータで解析するのが著しく困難です。

形式言語

一方で、コンピュータでも処理しやすいように、きちんと定まった文字集合(アルファベット)と文法(生成規則)で定義されているのが形式言語です。形式言語には曖昧さがないので、コンピュータで機械的に処理しやすくなっています。

アルファベット

我々が普段アルファベットというと、a-zの26文字を指しますが、形式言語の世界では、その言語を形成する文字の有限集合を意味します。

例えば、0と1だけで構成される言語のアルファベットは

{0, 1}

になります。

普段使っているアルファベットとは、意味が異なるので気をつけてください。

チョムスキー階層

ノーム・チョムスキーという著名な言語学者がいるのですが、彼は言語を構造的に解析しようとして、チョムスキー階層というのを定義しました。彼の研究は、計算機科学に多大な影響を与えていて、我々が使用している形式言語の基礎となっています。

文法	オートマトン	例
正規文法	有限オートマトン	正規表現
文脈自由文法	プッシュダウンオートマトン	PHP, HTML, CSS...
文脈依存文法
制限のない文法

チョムスキー階層では、4つの階層を定義しているのですが、この中で我々に関係あるのが、正規文法と文脈自由文法の2つです。残り2つに関しては、浅学の身で説明できるほど理解できてないので省略します。

正規文法

正規文法はおなじみの何かに名前が似ていますね。そう、正規表現です!! 実際に我々が使用している正規表現は、便利にするためにいろいろ機能が拡張されているのですが、基本的な概念は同じです。

正規表現もコンピュータを使う上で重要な概念ですが、本記事では扱いません。

文脈自由文法

冒頭であげた我々が普段使用しているような形式言語は、ほとんどが文脈自由文法で定義されています。文脈自由文法の解析は歴史が長く、手法もツールもいろいろなものが存在します。

自分で実装することも、もちろん可能ですが、一般的には既存のツールを使って、解析処理を実装します。

文脈自由言語の解析手順

文脈自由言語の解析は大きく分けて字句解析と構文解析の二段階に分かれます。

字句解析

字句解析は、その名の通り入力された言語から定まった文字列(字句、トークン)を抜き出して、返す処理の事を言います。分解されたトークンは、構文解析処理に渡され、正しい構文で字句が並んでいるかどうかがチェックされます。

lex(flex)

字句解析に使われるツールがlexです。最近(?)では、lexを拡張したGNU製のflexがよく使われます。なんと、lexの開発者の一人は、Google元CEOのエリック・シュミットです!! こんなところにも彼の業績が残っていたんですね。

lexではトークンを正規表現で定義します。定義した正規表現に対して、実行するCのプログラムを記述します。

正規表現 処理
正規表現 処理
...

lex用のファイルには .l という拡張子をつけます。

例: lex

lexファイルの簡単な例を紹介します。

[0-9]+          {
                    yylval = atoi(yytext);
                    return NUMBER;
                }


[-+*/()=\n]     {
                    return *yytext;
                }

[ \t]+          ;   /* ignore whitespace */

最初の[0-9]+は数字の並びを認識します。小数点が入るとダメだったり、00000みたいなものも認識できたりと、ツッコミどころは満載ですが、例なので細かいところをは気にしません。

NUMBERは構文解析の方で定義されたトークン値になります。

[-+*/()=\n]は面倒なので、1文字キャラクタをそのまま返しています。 lexではこのように、1文字キャラクタであれば、トークンを定義せずに返す事ができます。

[ \t]+では、空白文字を無視しています。普段言語を書いていると、空白文字はデフォルトで無視されるのが当たり前のように感じられると思いますが、空白文字もメモリ上はちゃんとコードが割り当てられている立派なデータです。なので、空白文字を無視する処理を書いておかないと、空白入るだけで字句解析エラーになってしまいます。

バッカス・ナウア記法(BNF)

構文解析に進む前に、バッカス・ナウア記法(BNF)という重要な概念について説明しておきます。バッカス・ナウアというのは、2人の著名な計算機科学者、ジョン・バッカス, ピーター・ナウアから命名されています。 2人ともチューリング賞を受賞した偉大な方で、今日のコンピュータ技術の基礎を築いてきた人物です。

BNFでは、アルファベットで構成された終端記号(字句解析から受け取る)と生成規則によって定義された非終端記号を組み合わせて、非終端記号の生成規則を定義します。

非終端記号に対して、終端記号・非終端記号の記号列を定義します。また|を使うことによって、複数の生成規則を定義できます。

<foo> ::= <bar> | <baz>

再帰

プログラマにはおなじみですが、定義の中で自分自身を参照することを再帰と言います。 BNFでは再帰を使って繰り返しを定義します。

例: 四則演算

例として四則演算をBNFで定義してみます。

<expr>   ::= <term> | <expr> + <term> | <expr> - <term>
<term>   ::= <factor> | <term> * <factor> | <term > / <factor>
<factor> ::= ( <expr> ) | <number>
<number> ::= 数値

見ていただくとわかりますが、expr、termの定義の中で、expr、term自身を参照しています。これが再帰です。

exprでは、加算(+)・減算(-)が定義されています。 termでは、乗算(*)・除算(/)が定義されています。 factorでは、括弧()が定義されています。

これらを一つの生成規則で定義していないのにはちゃんと意味があって、この場合、演算子の優先順位は下に行くほど高くなります。つまり、()の優先順位が一番高く、次が*,/で、一番優先順位が低いのが+,-になります。

この定義では、終端記号は数値 + - * /で、非終端記号はnumber factor term exprになります。数値に関しては字句解析で解析したトークンが返ってくるイメージです。

例: 1 + 2 * ( 3 - 4 )

例として、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

我々が普段使用している形式言語もBNFで定義されていることがほとんどです。例えばCSSであれば、Grammar of CSS 2.1で定義されています。このページでは、構文だけでなく字句解析用の定義もあります。

他の言語に関しても、探せば見つかると思います。

yacc(bison)

yaccはYet Another Compiler Compilerの略で、その名の通りコンパイラのためのコンパイラです。具体的にはBNFで定義された文法を元に、構文解析用のプログラムを生成します。通常はyaccの上位互換実装であるGNU Bisonを使うことが多いでしょう。

BNFをベースにして、生成規則を定義します。定義された生成規則に対して、どのような処理を行うかを具体的に定義していきます。

yaccのファイル名には.yという拡張子をつけます。

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

簡単なサンプルとして、四則演算ができる簡単な電卓、0calc を実装してみました。

https://github.com/bto/0calc

機能としてはかなり物足りないものですが、文脈自由文法がどのように解析されているのかがわかるかと思います。

機能は非常にシンプルです。

整数のみ
四則演算のみ
()は使える

抽象構文木(AST)

プログラムを書いていると、抽象構文木(AST)という単語を聞いたことがあると思います。今回の電卓の例では、すぐに計算結果を表示すれば良かったので、即時実行すればいいだけでした。

通常のプログラミング言語では、制御構文が入ってきますので、実行されない処理や、繰り返しの処理が入ってきますので、そうもいきません。

そのため、プログラミング言語の解析では、一度抽象構文木と呼ばれる中間形式に変換してから、様々な処理を実行することがほとんどです。

今回は時間もあまりないので、また別の機会にでも

結論

人狼は楽しい

OTOBANK Engineering Blog

オトバンクはコンテンツが大好きなエンジニアを募集しています！

プログラミング言語を作ってみよう(入門編)

言語