（↓これは FlameGraph に描かせたもの）
こういう図を描いてみました。
手順
準備
説明用の簡単なサンプルです。1 + 2 のような入力を受理するパーサ。
ログ出力のために @yydebug, @racc_debug_out を設定しておきます。
# sample_add.y
class Parser
rule
expr: INT "+" INT
{
puts "expression found"
result = val
}
end
---- inner
def initialize
# parser.rb を使ったときにデバッグ情報を出力する
@yydebug = true
# デバッグ情報の出力先をファイルに変更（デフォルトでは標準エラー出力） …… これは必須ではない
@racc_debug_out = File.open("debug.log", "wb")
end
def next_token
@tokens.shift
end
def parse(src)
@tokens = src.split(" ").map do |s|
case s
when /^\d+$/ then [:INT, s.to_i]
else [s, s]
end
end
@tokens << [false, false]
do_parse
end
---- footer
src = ARGV[0]
result = Parser.new().parse(src)
puts "result: " + result.inspect
-t (--debug) オプションを付けて racc コマンドを実行。
# パーサを生成
racc -t -o parser.rb sample_add.y
生成されたパーサを実行すると次のような内容が debug.log に出力されます。
$ ruby parser.rb "1 + 2"
expression found
result: [1, "+", 2]
$ head -30 debug.log
read :INT(INT) 1
shift INT
[ (INT 1) ]
goto 2
[ 0 2 ]
read "+"("+") "+"
shift "+"
[ (INT 1) ("+" "+") ]
goto 4
[ 0 2 4 ]
read :INT(INT) 2
shift INT
[ (INT 1) ("+" "+") (INT 2) ]
goto 6
[ 0 2 4 6 ]
reduce INT "+" INT --> expr
[ (expr [1, "+", 2]) ]
goto 1
[ 0 1 ]
スタックの部分だけ欲しいので、 grep してみましょうか。
$ grep '\[ (' debug.log
[ (INT 1) ]
[ (INT 1) ("+" "+") ]
[ (INT 1) ("+" "+") (INT 2) ]
[ (expr [1, "+", 2]) ]
[ (expr [1, "+", 2]) ($end false) ]
[ (expr [1, "+", 2]) ($end false) ($end false) ]
軽く眺める程度ならこれだけでいいかもしれませんね。で、もっと複雑になったときにきれいに表示して見たい……ということで次へ。
パースしやすいログを出力する
ログに出力されたスタックの情報を使いたいのですが、そのままではパースしづらそうです。まじめにやろうとすると、これ用のパーサが必要になってしまいます（上の例のような簡単なものであればそんなに難しくなさそうですが）。
そこで、横着して最初からパースしやすいフォーマットで出力することにしました。
スタックの情報をどこで出力しているか調べると、ここ（Racc::Parser#racc_print_stacks）です。
https://github.com/ruby/racc/blob/v1.5.2/lib/racc/parser.rb#L604-L611
嬉しいことに単独のメソッドになっています。
※ ちなみに呼び出し元を追っていくと分かりますが、スタックの実体は
Racc::Parser#racc_tstack
Racc::Parser#racc_vstack
です（それぞれ記号と値のスタック）。
racc コマンドの出力は Racc::Parser を継承したクラスになるので、parser.y の inner セクションに racc_print_stacks メソッドを書いておくと動作をオーバーライドできます。
……というわけで、下記のようにしました。スタックの情報だけ JSON で別ファイルに出力します。
---- header
require "json"
---- inner
def initialize
# ...
@racc_stack_out = File.open("stack.log", "wb")
end
# Override Racc::Parser#racc_print_stacks
def racc_print_stacks(tstack, vstack)
super(tstack, vstack)
stack = tstack.zip(vstack).map { |t, v| [racc_token2str(t), v] }
@racc_stack_out.puts JSON.generate(stack)
end
$ ruby parser.rb "1 + 2"
expression found
result: [1, "+", 2]
$ cat stack.log
[["INT",1]]
[["INT",1],["\"+\"","+"]]
[["INT",1],["\"+\"","+"],["INT",2]]
[["expr",[1,"+",2]]]
[["expr",[1,"+",2]],["$end",false]]
[["expr",[1,"+",2]],["$end",false],["$end",false]]
これでパースしやすくなりました 
仕込み部分のまとめ
ここまでのポイントをまとめておきます。
@yydebug = true-
@racc_debug_outを設定- これは必須ではないが、標準エラー出力に出てほしくなければファイルなど別の出力先を設定しておく
-
Racc::Parser#racc_print_stacksをオーバーライド - racc コマンドに
-t (--debug)オプションを付けてパーサを生成
図に変換する
ここまでできたら、あとは stack.log を図に変換するだけ。
ruby stack_graph.rb stack.log > stack_graph.html
stack_graph.rb は 160行くらい1の簡単なスクリプトです。
※ この例では、 INT や expr など定型的なものはパレット指定、それ以外はランダムに色を決めています。
このリポジトリを git clone して ./run.sh sample_add.y "1 + 2" で試せます（パーサの生成 → パーサの実行 → 図の生成をまとめて実行）。
例1: 左結合・右結合の違いを見てみる
せっかくなので他の例も見てみましょう。
まずは左結合と右結合の違い。他の部分は同じなので class Parser ... end の部分だけ示します。
# sample_lr.y
class Parser
prechigh
left "+"
# right "+"
preclow
rule
program: expr
{
puts "program found"
result = val[0]
}
expr:
INT
| expr "+" expr { result = val }
end
./run.sh sample_lr.y "1 + 2 + 3"
1 + 2 が来た時点ですぐ還元（reduce）され、次に expr + 3 となったときにまた還元されています。
右結合に変えてみるとこう。パースの結果が [1, "+", [2, "+", 3]] になります。
最初の 1 + 2 までシフト（shift）した時点では 1 + 2 の還元は発生せず、さらにスタックが積み上がったところで 2 + 3 が還元され、その後で 1 + expr が還元されています。
例2: SQL
もう少し大きめの実際的なものということで、別件で作っているSQLパーサの例。select句、from句、…… と順番に還元され、最後に全体が1個の select文に還元されている様子です。
次のような入力を与えました。動作確認用なので内容は適当。
select
123, 'str', null
,t1.a
,max(b)
,(
case
when a = 1 then 2
else 3
end
) as foo
from
db1 . table1 as t1
left outer join db2 . table2 as t2
on (
t2 . a = t1 . a
and t2 . b = t1 . b
)
and t2.a = t1.a
where
a = 123
and b <> 456
and c in (1, 2)
group by a, b
order by a, b
limit 10
;
FlameGraph に渡してみる
stack.log をちょっと加工すると FlameGraph に渡せるのでは？ と後から気づいてやってみました（この節は後から追記しました）。
# to_flamegraph.rb
require "json"
File.open(ARGV[0]).each_line do |line|
labels = JSON.parse(line).map { |t, _| t.to_s.gsub(";", "(semicolon)") }
puts labels.join(";") + " 1"
end
ruby to_flamegraph.rb stack.log | path/to/flamegraph.pl > flamegraph.svg
できますね 
FlameGraph で生成した SVG だと、キーワードにマッチする部分のハイライトや一部分のズーム表示といったインタラクティブな機能が利用できて便利。
参考: ディスク使用量をFlameGraphで可視化する - ( ꒪⌓꒪) ゆるよろ日記
バージョン
racc 1.5.2
関連
以下は Racc 関連ではありませんが、Ruby + パーサ関連で書いたものということで。
- Rubyで素朴な自作言語のコンパイラを作った
- 四則演算と剰余のみのexprコマンドをRubyで作ってみた
- 正規表現エンジン（ロブ・パイクのバックトラック実装）をRubyで写経した
- Ruby: 入れ子の配列だけをパースできるパーサを作る（手書きの再帰下降パーサ）
- 『RubyでつくるRuby』のMinRubyのパーサを書いた（手書きの再帰下降パーサ）
他に Ruby 関連で書いたもの
-
2021-01-04 時点
出力された HTML をブラウザで開くとこういう図が表示されます。x軸が処理の経過の方向、y軸がスタックが伸びる方向です。 ↩