1. はじめに
四則演算の文法は e ::= i | e+e | e-e | e*e | e/e のように書けます。
このような理論で用いられている数学的なBNFはバッカスが作った文字列を構文解析するための記法に似ています。
しかしながら数学的な BNF は木構文に対する BNF のような構文定義をしながら代数的データ型を定義してしまうという２つの意味を持っています。
実はこのような数学的なBNFは数行のPrologのコードで書くことができます。
ここでは、木構文に対する BNF の論理型言語実装について詳しく説明します。
2. 数学的 BNF の実装
2.1. 文法の要素を取り出す述語 ∈/2
e ::= i | e+e | e-e | e*e | e/e のような文法があった場合 | で区切られた各文法要素を取り出せると便利です。
そこで i | e+e | e-e | e*e | e/e から i, e+e, e-e, e*e, e/e を取り出す述語 ∈/2 を考えます。
∈/2 は以下のように定義できます:
G ∈ (G|_).
G ∈ (_|G1) :- !, G ∈ G1.
G ∈ G.
1つ目の規則は | 演算子の左側が構文の要素である規則です。
2つ目の規則は | 演算子の右側の構文要素を取り出す規則です。!はカットと言ってバックトラックを防ぐ特殊な述語です。
最後の規則は式が構文であるという規則です。
| 演算子は最後に書くことができない点に注意してください。 しかしながら t ::= (t | t) | i のように最後に書かなければ十分に機能します。
Prolog では ::=や∈の演算子は :- op(1200,xfx,::=). :- op(650,xfx,∈). という記述で使用できるようになります。
Prolog は非決定的な計算ができるのでたったこれだけの規則で分離された情報を取り出すことができます。
% test1.pl
:- op(650,xfx,∈).
G ∈ (G|_).
G ∈ (_|G1) :- !, G ∈ G1.
G ∈ G.
:- E ∈ (i | e+e | e-e | e*e | e/e),writeln(E),fail;true.
e ::= i | e+e | e-e | e*e | e/e.
:- (e::=Es),G ∈ Es,writeln(G),fail;true.
:- halt.
実行してみましょう:
$ swipl test1.pl
i
e+e
e-e
e*e
e/e
i
e+e
e-e
e*e
e/e
うまく取り出せました。
スクリプト言語のsplit関数みたいなものですが、式に対して規則を書いて非決定的に取り出せるのが面白いところです。
2.2. bnf/2 述語
次に文法と式を指定して構文検査する述語 bnf/2 を作ります。
構文が複合項なら分解して各引数を再帰型的に検査し、
構文が構文名なら構文要素を取り出して構文要素であるかどうかを調べ、
構文が端末となるものであれば単に値をチェックします。
bnf/2 述語は１引数目に文法を2引数目に式を指定して構文検査する述語で、以下のように定義できます:
bnf(G,E):-G=..[O|Gs],E=..[O|Es],maplist(bnf,Gs,Es),!.
bnf(G,E):-(G::=Gs),!,G1∈Gs,bnf(G1,E),!.
bnf(i,I):-integer(I),!.
1つ目の規則は構文要素の複合項を=../2述語によって分解し引数をそれぞれ再帰型的にbnfに渡して構文検査します。
2つ目の規則は構文名から構文の定義 G::=Gs を述語データベースにあれば取り出しその要素に対して構文検査を行います。
3つ目の規則はiは整数であるという規則です。他に規則を追加したければ追加すると良いでしょう。
2.3. 使用例
bnf/2 述語は以下のように用いることができます:
:- op(1200,xfx,::=).
:- op(650,xfx,∈).
G ∈ (G|_). G ∈ (_|G1) :- !, G ∈ G1. G ∈ G.
bnf(G,E):-G=..[O|Gs],E=..[O|Es],maplist(bnf,Gs,Es),!.
bnf(G,E):-(G::=Gs),!,G1∈Gs,bnf(G1,E),!.
bnf(i,I):-integer(I),!.
e ::= i | e+e | e-e | e*e | e/e.
:- bnf(e,1*2+3/4-5). % valid
:- not(bnf(e,a)). % invalid
:- halt.
2.4. 拡張例
bnf/2 は正しいか正しくないかをチェックするだけでしたがこれだと物足りないので、変換機能をつけた述語bnf/3を作ってみました:
% test3.pl
:- op(1200,xfx,::=).
:- op(1100,xfx,^^).
:- op(650,xfx,∈).
G ∈ (G|_). G ∈ (_|G1) :- !, G ∈ G1. G ∈ G.
bnf(G^^{EA=>A|F},E,A):-
G=..[O|Gs],E=..[O|Es],EA=..[O|As],
maplist(bnf,Gs,Es,As),!,call(F),!.
bnf(G^^{EA=>A},E,A):-
G=..[O|Gs],E=..[O|Es],EA=..[O|As],
maplist(bnf,Gs,Es,As),!.
bnf(G,E,A):-(G::=Gs),!,G1∈Gs,bnf(G1,E,A),!.
bnf(i^^{I=>A|F},I,A):-integer(I),!,call(F),!.
bnf(i^^{I=>A},I,A):-integer(I),!.
e ::= i ^^ {I=>int(I)}
| e+e ^^ {E1+E2=>add(E1,E2)}
| e-e ^^ {E1-E2=>sub(E1,E2)}
| e*e ^^ {E1*E2=>mul(E1,E2)}
| e/e ^^ {E1/E2=>div(E1,E2)}.
m ::= i ^^ {I=>I}
| m+m ^^ {E1+E2=>I|I is E1+E2}
| m-m ^^ {E1-E2=>I|I is E1-E2}
| m*m ^^ {E1*E2=>I|I is E1*E2}
| m/m ^^ {E1/E2=>I|I is E1 div E2}.
:- bnf(e,1*2+3/4-5,R),writeln(R). % sub(add(mul(int(1),int(2)),int(3)div int(4)),int(5))
:- bnf(m,1*2+3/4-5,R),writeln(R). % -3
:- not(bnf(e,a,_)). % invalid
:- halt.
詳細な説明はしませんがPrologの場合ネストした式は通常計算しないので計算するような場合には|で区切って書くことにしてみました。
自由に変えて遊べます。
3. 評価文脈
スモールステップ評価器での操作的意味論ではよく評価文脈なるものが出てきます。
それを Prolog で使えるようにしたいと思います。
基本的なアイディアは、評価文脈の構文と式を渡してやって、穴に対応する式と穴の空いた式と穴に対応する空の変数を返す述語 evalctx/4 のようなものがあれば評価文脈を素直に扱えるはずだというものです。
このアイディアに基づいて evalctx/4 を実装してみたいと思います。
3.1. 実装
evalctx/4 は 文法要素と式を受け取って評価文脈に対応する式と 穴の空いた式/穴 を返します。
評価したい式を評価した式を穴に埋めると穴の空いた式は完全な式に変わればいいわけです。
evalctx([],E,E,H/H).
evalctx(G,E,V,H_/H):-G=..[O|Gs],E=..[O|Es],hole(Gs/G1,Es/E1,Hs/H1),
evalctx(G1,E1,V,H1/H),H_=..[O|Hs].
evalctx(G,E,V,H_/H):-(G::=Gs),G1∈Gs,evalctx(G1,E,V,H_/H).
1つ目の規則は穴だったら式と穴をそのまま返します。
3つ目の規則は文法名だった場合に文法名に対する各要素を取り出して再帰的に評価文脈を探します。
２つ目の規則は複合項だった場合は、引数を取り出して引数のうちのどれかを取り出して穴とし、再帰型的に呼び出します。
ここで、hole/2 は文法リストと式リストと評価文脈リストを受け取りN番目の値が穴だとして返します。
穴であるとされた箇所のみがEにはならず単なる変数として返されることになります。
hole([G|_]/G,[E|Es]/E,[H|Es]/H).
hole([_|Gs]/G,[E|Es]/E_,[E|Hs]/H):-hole(Gs/G,Es/E_,Hs/H).
このevalctx/4 を使うと
% calc_hole.pl
:- op(1200,xfx,::=),op(600,xfx,∈).
:- op(250,yf,*).
:- op(920, xfx, ['→', '↠']).
G∈(G|_). G∈(_|G2):-!, G∈G2. G∈G.
bnf(G,E):-G=..[O|Gs],E=..[O|Es],maplist(bnf,Gs,Es),!.
bnf(G,E):-(G::=Gs),!,G1∈Gs,bnf(G1,E),!.
bnf(i,I):-integer(I),!.
bnf(x,I):- atom(I),!.
bnf(m*,Ls) :- maplist(bnf(m),Ls).
hole([G|_]/G,[E|Es]/E,[H|Es]/H).
hole([_|Gs]/G,[E|Es]/E1,[E|Es_]/H):-hole(Gs/G,Es/E1,Es_/H).
evalctx([],E,E,H/H).
evalctx(G,E,V,E_/H):-G=..[O|Gs],E=..[O|Es],hole(Gs/G1,Es/E1,Es_/H_),evalctx(G1,E1,V,H_/H),E_=..[O|Es_].
evalctx(G,E,V,E_/H):-(G::=Gs),G1∈Gs,evalctx(G1,E,V,E_/H).
small(F,G,E,E_):-evalctx(G,E,V,E_/H),call(F,V,H),writeln(E_).
all(F)-->call(F),all(F);!.
m::= i|m+m|m-m|m*m|m/m.
a::=[]|a+[]|[]+a|a-[]|[]-a|a*[]|[]*a|a/[]|[]/a.
A+B → I :- i(A),i(B),I is A+B.
A-B → I :- i(A),i(B),I is A-B.
A*B → I :- i(A),i(B),I is A*B.
A/B → I :- i(A),i(B),I is A div B.
run(M) :- bnf(m,M),all(small(→,a),M,_).
:- run((1+2*3)+4*5).
:- halt.
4. まとめ
Prolog を用いて数学的 BNF を定義し構文検査をしてみたり、セマンティックアクションを加えてみたりしました。
また評価文脈を処理するプログラムも紹介しました。
結果的に四則演算を行う構文検査付きの処理系は以下のような記述で実装できることを確かめました:
m::= i|m+m|m-m|m*m|m/m.
a::=[]|a+[]|[]+a|a-[]|[]-a|a*[]|[]*a|a/[]|[]/a.
A+B → I :- i(A),i(B),I is A+B.
A-B → I :- i(A),i(B),I is A-B.
A*B → I :- i(A),i(B),I is A*B.
A/B → I :- i(A),i(B),I is A div B.
このようにアカデミックな世界での言語実装を Prolog を使えば素直に書き下すことができます。
また実際に簡潔に作ることで全能感を得ることができます。
みなさんも是非使ってみてください。