うちの会社に来てくれる人に誘われてCSNagoyaという勉強会に参加しています。最近のテーマはコンパイラの実装方法です。理論的な話は全くないので、コンパイラを作ったことがない初心者がとっつきやすいと思います。

このテーマでは最終的に各人が好きな言語でコンパイラを書きます。私はJavaが好きなのですが、飲み会の成り行きによりprologで書くことになりました。

prologはテキスト処理という世界ではものすごく強力です(遅いですが)。parserを作るために生まれてきたような言語です。左再帰がない文脈自由文法であれば、ほぼそのままprologのプログラムに落とせます。

今回はprologを思い出すために、整数の四則演算ができる計算機を作ってみました。構文と字句の定義(EBNFもどき)は次です。

構文の定義

add = multiply [add_options]
add_options = add_option [add_options]
add_option = '+' multiply
add_option = '-' multiply
multiply = primary [multiply_options]
multiply_options = multiply_option [multiply_options]
multiply_option = '*' primary
multiply_option = '/' primary
primary = '(' add ')'
primary = integer

字句の定義

tokens = token [tokens]
token = ignore | '+' | '-' | '*' | '/' | integer
ignore = ' ' | 'b' | 'f' | 'n' | 'r' | 't'
integer = ('0'..'9')+

この構文と字句の定義をprologに落とすと次のようになります。prologでよくつかわれる差分リストを使って実現しました。各行がほぼそのまま上記に対応しています。

prologプログラム

parse(A, P) :- tokens(A, [], Q), add(Q, [], P).
add(A, C, P) :- multiply(A, B, Q), (add_options(B, C, Q, P); B = C, P = Q).
add_options(A, C, P, R) :- add_option(A, B, P, Q), (add_options(B, C, Q, R); B = C, Q = R).
add_option([0'+ | A], B, P, add(P, Q)) :- multiply(A, B, Q).
add_option([0'- | A], B, P, subtract(P, Q)) :- multiply(A, B, Q).
multiply(A, C, P) :- primary(A, B, Q), (multiply_options(B, C, Q, P); B = C, P = Q).
multiply_options(A, C, P, R) :- multiply_option(A, B, P, Q), (multiply_options(B, C, Q, R); B = C, Q = R).
multiply_option([0'* | A], B, P, multiply(P, Q)) :- primary(A, B, Q).
multiply_option([0'/ | A], B, P, divide(P, Q)) :- primary(A, B, Q).
primary([0'( | A], B, parenthesis(P)) :- add(A, [0') | B], P).
primary([integer(P) | A], A, integer(P)).
tokens(A, C, P) :- token(A, B, P, Q), (tokens(B, C, Q); B = C, Q = []).
token([A | B], B, P, P) :- member(A, [0' , 0'b, 0'f, 0'n, 0'r, 0't]).
token([A | B], B, [A | P], P) :- member(A, [0'+, 0'-, 0'*, 0'/, 0'(, 0')]).
token(A, B, [integer(Q) | P], P) :- integer(A, B, Q, _).
integer([A | B], C, S, R * 10) :- P is A - 0'0, P >= 0, P =< 9, (integer(B, C, Q, R), S is P * R + Q; B = C, S = P, R = 1).

SWI-Prologで実行すると、こんな感じです。抽象構文木が得られました。これをこねくり回せば、計算機のできあがりです。

1 ?- parse("12+34*(56/78)", P).
P = add(integer(12), multiply(integer(34), parenthesis(divide(integer(56), integer(78))))) .

「抽象構文木はいらないよ」という人はadd/subtract/multiply/divide/parenthesisのノードを生成している部分を計算式にすれば、直接的に計算結果を得ることができます。

直接的に計算結果がほしい場合

parse(A, P) :- tokens(A, [], Q), add(Q, [], P).
add(A, C, P) :- multiply(A, B, Q), (add_options(B, C, Q, P); B = C, P = Q).
add_options(A, C, P, R) :- add_option(A, B, P, Q), (add_options(B, C, Q, R); B = C, Q = R).
add_option([0'+ | A], B, P, P + Q) :- multiply(A, B, Q).
add_option([0'- | A], B, P, P - Q) :- multiply(A, B, Q).
multiply(A, C, P) :- primary(A, B, Q), (multiply_options(B, C, Q, P); B = C, P = Q).
multiply_options(A, C, P, R) :- multiply_option(A, B, P, Q), (multiply_options(B, C, Q, R); B = C, Q = R).
multiply_option([0'* | A], B, P, P * Q) :- primary(A, B, Q).
multiply_option([0'/ | A], B, P, P / Q) :- primary(A, B, Q).
primary([0'( | A], B, P) :- add(A, [0') | B], P).
primary([integer(P) | A], A, integer(P)).
tokens(A, C, P) :- token(A, B, P, Q), (tokens(B, C, Q); B = C, Q = []).
token([A | B], B, P, P) :- member(A, [0' , 0'b, 0'f, 0'n, 0'r, 0't]).
token([A | B], B, [A | P], P) :- member(A, [0'+, 0'-, 0'*, 0'/, 0'(, 0')]).
token(A, B, [integer(Q) | P], P) :- integer(A, B, Q, _).
integer([A | B], C, S, R * 10) :- P is A - 0'0, P >= 0, P =< 9, (integer(B, C, Q, R), S is P * R + Q; B = C, S = P, R = 1).

今回のprologプログラムはなんと16行です。たった、これだけの行数でできるなんて驚きです。
これだけの行数で文脈自由文法やそれに類似する文法に従ったテキスト処理ができる汎用言語はなかないので、prologはすごいですね。

カテゴリー: 技術情報