LoginSignup
8
9

More than 1 year has passed since last update.

@sonota88

Ruby/Racc: パース時のスタックの動きをFlameGraphっぽくビジュアライズする

Last updated at Posted at 2021-01-04

image.png

image.png

（↓これは FlameGraph に描かせたもの）
image.png

こういう図を描いてみました。

手順

準備

説明用の簡単なサンプルです。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]]

これでパースしやすくなりました :ok_hand:

仕込み部分のまとめ

ここまでのポイントをまとめておきます。

  • @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の簡単なスクリプトです。

image.png

※ この例では、 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"

image.png

1 + 2 が来た時点ですぐ還元（reduce）され、次に expr + 3 となったときにまた還元されています。

右結合に変えてみるとこう。パースの結果が [1, "+", [2, "+", 3]] になります。

image.png

最初の 1 + 2 までシフト（shift）した時点では 1 + 2 の還元は発生せず、さらにスタックが積み上がったところで 2 + 3 が還元され、その後で 1 + expr が還元されています。

例2: SQL

image.png

もう少し大きめの実際的なものということで、別件で作っている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

image.png

image.png

できますね :smiley:

FlameGraph で生成した SVG だと、キーワードにマッチする部分のハイライトや一部分のズーム表示といったインタラクティブな機能が利用できて便利。

参考: ディスク使用量をFlameGraphで可視化する - ( ꒪⌓꒪) ゆるよろ日記

バージョン

racc 1.5.2

関連

以下は Racc 関連ではありませんが、Ruby + パーサ関連で書いたものということで。

他に Ruby 関連で書いたもの

  1. 2021-01-04 時点
    出力された HTML をブラウザで開くとこういう図が表示されます。x軸が処理の経過の方向、y軸がスタックが伸びる方向です。 ↩

8
9
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
8
9