＜自作言語処理系の説明用テンプレ＞

自分がコンパイラ実装に入門するために作った素朴なトイ言語とその処理系です。簡単に概要を書くと下記のような感じ。

小規模: コンパイラ部分は 1,000 行程度
pure Ruby / 標準ライブラリ以外への依存なし
独自VM向けにコンパイルする
ライフゲームのために必要な機能だけ
- 変数宣言、代入、反復、条件分岐、関数呼び出し
- 演算子: +, *, ==, != のみ（優先順位なし）
- 型なし（値は整数のみ）
Ruby 以外の言語への移植（コンパイラ部分のみ）
セルフホスト版（別リポジトリ）

下記も参照してください。

＜説明用テンプレおわり＞

もともとパーサ部分は手書きの再帰下降パーサでしたが、Racc 版を作ってみました。

Racc で四則演算のパーサを作る方法は分かったがもう少しプログラム言語らしきものを扱っているサンプルを見たいとか、パースしたそばから実行する方式（インタプリタ方式）ではなく構文木が欲しいんだけど、という感じの人には参考になるかもしれません（昔の自分に送ってあげたい）。

できたもの

vgparser_racc.y を追加したブランチです。

300行弱なので全部貼ってもいいのですが、雰囲気程度ということで途中を省略したものを貼ります。全体は GitHub の方で見てください。

class Parser

  prechigh
    left "+" "*"
  preclow

rule

  program:
    top_stmts
      {
        top_stmts = val[0]
        result = ["top_stmts", *top_stmts]
      }

  top_stmts:
    top_stmt
      {
        top_stmt = val[0]
        result = [top_stmt]
      }
  | top_stmts top_stmt
      {
        top_stmts, top_stmt = val
        result = [*top_stmts, top_stmt]
      }

  top_stmt:
    func_def

  func_def:
    "func" IDENT "(" args ")" "{" stmts "}"
      {
        _, fn_name, _, args, _, _, stmts, _, = val
        result = ["func", fn_name, args, stmts]
      }

  args:
    # nothing
      {
        result = []
      }
  | arg
      {
        arg = val[0]
        result = [arg]
      }
  | args "," arg
      {
        args, _, arg = val
        result = [*args, arg]
      }

  arg:
    IDENT | INT

  stmts:
    # nothing
      {
        result = []
      }
  | stmt
      {
        stmt = val[0]
        result = [stmt]
      }
  | stmts stmt
      {
        stmts, stmt = val
        result = [*stmts, stmt]
      }

  stmt:
    stmt_var
  | stmt_set
  | stmt_return
  | stmt_call
  | stmt_call_set
  | stmt_while
  | stmt_case
  | stmt_vm_comment
  | stmt_debug

  stmt_var:
    "var" IDENT ";"
      {
        _, ident, _ = val
        result = ["var", ident]
      }
  | "var" IDENT "=" expr ";"
      {
        _, ident, _, expr = val
        result = ["var", ident, expr]
      }

# ... 途中省略 ...

---- header

require "json"
require_relative "common"

---- inner

def next_token
  @tokens.shift
end

def to_token(line)
  token = Token.from_line(line)
  return nil if token.nil?

  if token.kind == :int
    Token.new(token.kind, token.value.to_i)
  else
    token
  end
end

def read_tokens(src)
  tokens = []

  src.each_line do |line|
    token = to_token(line)
    next if token.nil?

    tokens << token
  end

  tokens
end

def to_racc_token(token)
  kind =
    case token.kind
    when :ident then :IDENT
    when :int   then :INT
    when :str   then :STR
    else
      token.value
    end

  [kind, token.value]
end

def parse(src)
  tokens = read_tokens(src)
  @tokens = tokens.map { |token| to_racc_token(token) }
  @tokens << [false, false]

  do_parse()
end

---- footer

if $0 == __FILE__
  ast = Parser.new.parse(ARGF.read)
  puts JSON.pretty_generate(ast)
end

実行の例

入力とするプログラムの例です。

// sample.vg.txt
func main() {
  return 1 + (2 * 3);
}

次のように実行するとASTに変換できます。

## vgparser_racc.rb を生成
$ bundle exec racc -t -o vgparser_racc.rb vgparser_racc.y

$ ruby vglexer.rb sample.vg.txt > tmp/tokens.txt
$ ruby vgparser_racc.rb tmp/tokens.txt 
[
  "top_stmts",
  [
    "func",
    "main",
    [

    ],
    [
      [
        "return",
        [
          "+",
          1,
          [
            "*",
            2,
            3
          ]
        ]
      ]
    ]
  ]
]

スタックの動きを見てみる

せっかく Racc を使っているので、適当なサンプルコード（下記）をパースさせてスタックの動きを図にしてみました。

func add(a, b) {
  var c = a + b;
  return c;
}

func main() {
  var x = -1;
  var i = 0;

  while (i != 10) {
    case when (i == 1) {
      call_set x = add(i, x);
    } when (i == 2) {
      set x = 1 + 2;
    } when (1) {
      set x = 1 + (2 * 3);
    }

    set i = i + 1;
  }
}

図の描き方については Ruby/Racc: パース時のスタックの動きをFlameGraphっぽくビジュアライズする - Qiita を参照。

左端の、全体の 1/5 くらいの小さめの山が add 関数で、残りが main 関数ですね。

メモ

レキサはすでにあるのでそれを流用した
- to_racc_token メソッドで Token オブジェクトを Racc が期待する形式に変換
1時間くらいで書けた。これより大きめの SQL パーサを少し前にすでに書いていてある程度慣れていたのと、パーサのテストがそのまま使えたのが良かった。

この記事を読んだ人はこちらの記事も読んでいます（たぶん）

できたもの

実行の例

スタックの動きを見てみる

メモ

関連

この記事を読んだ人はこちらの記事も読んでいます（たぶん）