はじめに
今日は構文解析ハードウェアを作りたいと思います。
verilog言語では言語組み込みのスタックはありません。関数は作れますが再帰できません。
ステートマシンとして字句解析器や構文解析を書く必要があります。
1. PrologのDCGでパーサ
まずはどんな仕様のものを作るのかPrologのDCGを使って書いてみましょう:
*(F,[R|Rs])-->call(F,R), *(F,Rs).
*(_,[])-->{}.
+(F,[R|Rs])-->call(F,R), *(F,Rs).
i(I)-->[I],{member(I,[0,1,2,3,4,5,6,7,8,9])}.
n(R)--> +(i,I),{foldl([X,V,N]>>(N is V*10+X),I,0,R)}.
l(int(N))-->n(N).
l(add)-->[+].
ls(Ls)--> *(l,Ls).
e([int,I|S1]/S)-->[int,I], e1(S1/S).
e1([int,I,add|S1]/S)-->[add,int,I],e1(S1/S).
e1(S/S)-->{}.
:- ls(Ls,[1,2,+,2,3,+,3,4],[]),writeln(Ls),Ls=[int(12),add,int(23),add,int(34)].
:- e(E/[],[int,12,add,int,23,add,int,34],[]),writeln(e=E),E=[int,12,int,23,add,int,34,add].
:- halt.
*/4 述語は(DCGは後ろの引数が２つ省略されていますので２つ引数があれば4引数の述語になります) 0回以上の繰り返しを表す高階なパーサです。
+/4 述語は1回以上の繰り返しを表すパーサです。
i/3 は数字を１つ表すパーサ。
n/3 は数字の連続を１つにまとめた整数のパーサ。
l/3 は整数または+を表すパーサです。
ls/3 は整数または+を複数表すパーサであり字句解析器です。
e/3 はパース結果としてスタックマシンのコードを返す構文解析器です。
e1/3 は + と 整数 を繰り返すパーサです。
Prologでステートマシンの字句解析
これらと同様のものをステートマシンとして書いたものを以下に示します:
lx(i,[I|C],_,R):-integer(I),lx(n,C,I,R).
lx(i,[+|C],N,[add|R]):-lx(i,C,N,R).
lx(i,[-|C],N,[sub|R]):-lx(i,C,N,R).
lx(i,_,_,[]).
lx(n,[I|C],N,R):-integer(I),N1 is N*10+I,lx(n,C,N1,R).
lx(n,C,N,[int,N|R]):-lx(i,C,0,R).
lx(n,_,_,[]).
:-lx(i,[1,1,+,2,2,+,3,3],0,R),writeln(R),R=[int,11,add,int,22,add,int,33].
継続渡し形式のオートマトンを表したものとして字句解析器を書き直しました。
状態は初期状態iと整数状態nの２つがありまして、lx(状態,プログラムコード,値,戻り値)という述語として書きました。7つの規則で字句解析が書けるので私としては綺麗にモデル化できたなと思います。返り値を使ってリストを作っているから末尾再帰になってないじゃないか？と思うかもしれませんが、Prologの変数は単一化変数であり、穴を引き渡していって穴埋めしていって最後に穴を[]で埋めることで穴のないリストを作り出しているので末尾菜気になっています。関数的に書くなら、前後が反転した結果リストを引き渡していって最後にリストを反転させると良いでしょう。OCamlはこの辺をうまく処理する方法があったはずです。
Prologでステートマシンのパーサ
次に構文解析器をステートマシンとして書きます。スタックがあるのでプッシュダウンオートマトンと呼ばれるようなものになったような気がします。いい加減だなw
p(r,_,_->[]).
p(i,[int|C],S->[int|M]):- p(i1,C,S->M).
p(i1,[I|C],[P|S]->[I|M]):- p(P,C,S->M).
p(e,C,S->M):- p(i,C,[e1|S]->M).
p(e1,[add|C],S->M):- p(i,C,[e2,add|S]->M).
p(e1,C,[P|S]->M):- p(P,C,S->M).
p(e2,C,[O|S]->[O|M]):- p(e1,C,S->M).
:- p(e,[int,12,add,int,23,add,int,34],[r]->M),writeln(p=M),
P=[int,12,int,23,add,int,34,add].
:- halt.
p/3 の引数はp(状態,プログラムコード,スタック->戻り値)となってまして、実質的にp/4なのですが、出力がわかりやすいようになんとなく->をつけてみました。初期状態はeから始まり、まずはiにステートを移行するのですが終わったらe1に進むようにスタックに次の状態を積んで関数呼び出しをするように次の状態に進みます。i状態ではintを取り出してリストにintを加えi1に移行、i1では整数を１つ取り出して返り値に加え、スタックから次の状態を取り出して次の処理に移動します。最初はe1が入っているのでe1に移行することになります。e1ではaddがあればe2とaddをスタックに積んで、iに移行し、add出ないならスタックから状態を取り出して移行します。開始時にスタックにrを入れておくので終わったらrに移行して、穴を埋めて終了します。iを取り出すと次はe2に移行します。スタックから演算子を取り出して出力してe1に移動します。
Pythonでステートマシンのパーサ
このようにモデル化したものをpythonで実装すると以下のようになります:
def lex(inp):
p = 0
st = "NORMAL"
rc = [0 for i in range(256)]
rp = 0
inp += "\0"
while p < len(inp):
c = inp[p]
p += 1
print(f"c={c}; st = {st}")
match st:
case "NORMAL":
match c:
case "0"|"1"|"2"|"3"|"4"|"5"|"6"|"7"|"8"|"9": n = ord(c)-ord('0'); st = "NUMBER"
case "+": rc[rp]="ADD"; rp+=1
case "-": rc[rp]="SUB"; rp+=1
case "NUMBER":
match c:
case "0"|"1"|"2"|"3"|"4"|"5"|"6"|"7"|"8"|"9": n = (n<<3)+(n<<1)+ ord(c)-ord('0')
case _: rc[rp]="INT"; rp+=1; rc[rp] = n;rp+=1; p-=1; st = "NORMAL"
return rc
def parser(inp):
stack = ["r"]
mem = []
p = 0
st = "e"
while p < len(inp):
c = inp[p]; p+=1
print(f"stack{stack} c={c} st={st} mem={mem}")
match st:
case "r": return mem
case "i":
if c != "INT": return "error"
else: st = "i1"; mem.append("INT")
case "i1": st=stack.pop(); mem.append(c)
case "e": st="i"; stack.append("e1"); p-=1
case "e1":
match c:
case "ADD"|"SUB": st="i"; stack.append(c); stack.append("e2")
case _: st=stack.pop(); p-=1
case "e2": st="e1";mem.append(stack.pop());p-=1
print(parser(lex("1+2+34")))
こちらの方が分かりやすいという方も多くおられるかと思います。
動作としてはPrologと同じことをしています。
ここまで作ればあとはverilogで書けばいいだけのはずです。
まとめ
ステートマシンとしてパーサを書くにはそれなりの慣れが必要です。
Pythonでいきなり命令的に考えても良いのですが、美しくないと思われる方もいるかもしれません。
そのような場合はPrologや関数型言語でステートマシンモデルを考えると結構楽しくステートマシンを作れるようになるのではないかと思います。
Pythonなどのプログラミング言語で愚直にステートマシンを書けばあとはverilogなどで書けばハードウェアが作れるようになるはずです。