＜自作言語処理系の説明用テンプレ＞
自分がコンパイラ実装に入門するために作った素朴なトイ言語とその処理系です。簡単に概要を書くと下記のような感じ。
- 小規模: コンパイラ部分は 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 パーサを少し前にすでに書いていてある程度慣れていたのと、パーサのテストがそのまま使えたのが良かった。
関連
他に Racc 関連で書いたもの。
この記事を読んだ人はこちらの記事も読んでいます（たぶん）