字句解析のハードウェアを作る

1. はじめに

前回は字句解析のステートマシンのモデルを考えてPythonで実装しました。

今回は愚直にverilog化してみます。

2. 実装

主に Lex モジュールが字句解析器で top モジュールがテスト用のモジュールとなります。
通信周りのモジュールはスタックマシンを作った際のモジュールと同じものを使用しました。

2.1. 字句解析

仕様としては以下のようなステートマシンを作ります:

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,2,+,3,4,+,5,6],0,R),writeln(R),R=[int,11,add,int,22,add,int,33].

入力文字列は、ゼロ終端の配列データとしたいので、reg [7:0] inp [32] = {>>{"12+34+56",0}}; のように書くと上手くいきました。最終的には外部メモリを読み込むように書き換えると汎用的になるでしょうけどとりあえず動かしたいのでこれでよしとします。終了ステータスがなかったので追加し結果としてrcが結果データの入っている配列でrpが結果の長さ、flgが結果が出た時に立つフラグにしました。

module Lex(input clk, rst, output reg flg, reg [7:0] rc [32],reg [7:0] rp);
  reg [7:0] inp [32] = {>>{"12+34+56",0}};
  reg [7:0] p, st, n;
  localparam INI = 0, NML = 1, NUM = 2, FIN = 3;
  localparam ADD = 1, SUB = 2, INT = 3, BYE = 4;
  reg [7:0] c;
  initial begin st = INI; end
  always @(posedge clk) begin
    if (rst) st <= INI; else
    case (st)
    INI: begin p = 0; rp = 0; n = 0; st <= NML; end
    NML: begin
      c = inp[p];
      if ("0" <= c && c <= "9")
      begin n <= c - "0"; st <= NUM; p <= p + 1; end else
      case (c)
      "+": begin rc[rp]=ADD; rp <= rp + 1; p <= p + 1; end
      "-": begin rc[rp]=SUB; rp <= rp + 1; p <= p + 1; end
      default: begin flg <= 1; st <= FIN; end
      endcase
    end
    NUM: begin
      c = inp[p];
      if ("0" <= c && c <= "9")
      begin n <= (n<<3)+(n<<1)+(c - "0"); p <= p + 1; end else
      begin rc[rp]<=INT; rc[rp+1] <= n; rp <= rp + 2; st <= NML; end
    end
    FIN: begin flg <= 0; end
    endcase
  end
endmodule

2.2. トップモジュール

字句解析器を動かして結果をUartで出力するだけですが、配列のデータを１つずつ取り出して出力し、出力中はPWAIT状態で終了すると次のステータスに移行するように作り慣れていないので結構悩みました。慣れれば楽に作れると思います:

module top(input clk, s1, output reg [5:0] led, output uart_txp);
  `define INCLUDE
  `include "UartTx.v"
  `undef INCLUDE
  assign print_clk = clk;
  `define ln {8'd13,"\n"}
  `define p(a,s) begin `print(a,STR);led[0]<=0; if(print_state==PRINT_IDLE_STATE) begin st<=PWAIT; pwait_st<=s; end end
  localparam FREQ=27_000_000;

  reg [4:0] st,pwait_st;
  initial begin st = INI; rst1 = 1; end
  localparam INI = 0, WAIT = 1, RUN = 2, OUT2 = 3, OUT3 = 4, FIN = 5, IDLE=6,PWAIT=7;
  wire flg; wire [7:0] rc [32]; wire [7:0] rp; reg [7:0] i,v; reg rst1; reg [32:0] cnt; 
  Lex lx(clk,rst1,flg,rc,rp);
  always @(posedge clk) begin
    led[0] = ~s1;
    if (s1) begin st <= INI; led[3:1]<= ~0; end else
    case (st)
    INI: begin st <= WAIT; cnt <= 0; led[3:2]<= ~0; led[1] <= 0; `p({"initialize",`ln},WAIT) end
    WAIT:if (cnt >= FREQ/2) begin st <= RUN; rst1 <= 1; end
         else cnt <= cnt+1;
    RUN: begin led[2] <= 0; rst1 <= 0; if (flg) begin i<= 0; st <= OUT2; end end
    OUT2: begin
      v <= rc[i];
      if (i<rp) st <= OUT3; else st <= FIN;
      i <= i + 1;
    end
    OUT3: `p({hexf(v),", "},OUT2)
    FIN: begin led[3] <= 0; `p({`ln,"ok",`ln},IDLE) end
    PWAIT: st<=pwait_st;
    endcase
  end
endmodule

3. 出力結果

initialize
03, 0c, 01, 03, 22, 01, 03, 38, 
ok

このように出力され、"12+34+56" をコンパイルした結果の[INT,12,ADD,INT,34,ADD,INT,56]とコンパイルできたことが確認できました。

4. まとめ

字句解析をモデル化し、普通のプログラミング言語で実装してみたのちにハードウェア化して動かしてみました。

5. 感想

CPUがなくても字句解析できるのはわかっていることですが、実際に動くとちょっと嬉しいです。
わかっている人にとっては当たり前の話かもしれませんが、CPU上でしか字句解析器を作ったことがなかったので良い経験となりました。
次回はパーサを作りますが、これもハードウェア化は初体験になるので楽しみです。