ydah blog.

Ruby構文解析器 開発日録#2

このエントリーをはてなブックマークに追加

こんにちはydahです。昨日に引き続き筆を執っています。今日はクリスマスイブですね。

さて、今回はANDPAD Advent Calendar 2023の24日目の記事として、今年Lramaの開発で手を動かしてきた内容の中で、これまで発表していないものを紹介します1。もうすぐ今年も終わりますので、いわゆる「今年の振り返り」的な内容です。

今年はどれくらい手を動かしたかというと大体140コミットほどでした。2 グラフを眺めているとKaigi on Rails 2023、RubyWorld Conference 2023辺りでKaigi Effectを受けていることが目に見える3ので、とてもおもしろいですね。それでは、振り返りをしていきましょう。

#includeを明示しなくていいようにする

Bisonとの差分を解消した対応です。Bisonはヘッダーファイルを生成するオプションをつけると、#includeを明示しなくてもヘッダーファイルをインクルードしてくれます。 これをLramaでも同じ挙動にするために、-h、--header、-dオプションをつけた場合には、#includeを明示しなくてもヘッダーファイルをインクルードするようにしました。

たとえば、以下のコマンドを実行したとします。

lrama calc.y --header=calc.h -o calc.c

この場合、calc.yからcalc.cとcalc.hが生成されますが、calc.yにおいて以下のように#include "calc.h"を明示する必要がなくなりました。

#include <stdlib.h>
#include <ctype.h>

-#include "calc.h"

static int yylex(YYSTYPE *val, YYLTYPE *loc);
static int yyerror(YYLTYPE *loc, const char *str);

今までは#includeディレクティブにヘッダーファイルの名前を決め打ちで書く必要があったので、コマンドを以下のように変更するとたちまちコンパイルエラーになってしまっていました。4

lrama calc.y --header=other.h -o calc.c

Helpコマンドの改善

Lramaに文法ファイルを渡して色々と試していた時に、どんなオプションがあるのだろうと思っておもむろにlrama --helpを実行したところ、以下のような出力がされていました。

❯ lrama --help
Usage: lrama [options]
    -V, --version
    -S, --skeleton=FILE
    -t
    -h, --header=[FILE]
    -d
    -r, --report=THINGS
        --report-file=FILE
    -v
    -o, --output=FILE
        --trace=THINGS
    -e

Bisonのオプションと概ね同じ意味になっているとは思いましたが、--helpコマンドを実行した時に、どんなオプションがあるのかを一目でわかるようにするために、オプションを整理して表示するようにしました。

❯ lrama --help
Lrama is LALR (1) parser generator written by Ruby.

Usage: lrama [options] FILE

STDIN mode:
lrama [options] - FILE               read grammar from STDIN

Tuning the Parser:
    -S, --skeleton=FILE              specify the skeleton to use
    -t                               reserved, do nothing

Output:
    -h, --header=[FILE]              also produce a header file named FILE
    -d                               also produce a header file
    -r, --report=THINGS              also produce details on the automaton
        --report-file=FILE           also produce details on the automaton output to a file named FILE
    -o, --output=FILE                leave output to FILE
        --trace=THINGS               also output trace logs at runtime
    -v                               reserved, do nothing

Error Recovery:
    -e                               enable error recovery

Other options:
    -V, --version                    output version information and exit
        --help                       display this help and exit

そして、--helpコマンドを整理していて気づいたのですが、いくつかreservedになっているのみのオプションもあったので、整理しておいて良かったと感じました。 また、この副産物としてBisonとのオプションの差異に気づくこともできました。

具体的には生成するヘッダファイルを生成するのためのオプションは-Hなのですが、Lramaでは-hとなっていました。 これは段階的に、-Hオプションへと移行していて、v0.5.8以降のLramaではBisonとの差異は解消しています。

エラーメッセージの改善

Lramaはv0.5.7から、内部に持っている手書きパーサーが、Raccによる自動生成したものに置き換わりました5。つまり、parser.yという文法ファイルからparser.rbを生成するように変わりました。 それに伴い、内部パーサーで文法ファイルを解析する際に、もしパースエラーが発生した場合にはRaccが提供しているon_errorでerror_valueから情報がとれるのでエラーメッセージがリッチにできます。

なので、パースエラーが発生した場合に、以下のようにファイル名と位置情報とエラーが発生した周辺をエラーメッセージとして表示するようにしています。

❯ lrama -d test.y
parser.y:400:in `on_error': a.y:5:7: parse error on value #<struct Lrama::Lexer::Token::Ident s_value="invalid", alias_name=nil> (IDENTIFIER) (Racc::ParseError)
%expect invalid
        ^^^^^^^
        from racc/parser.rb:276:in `_racc_do_parse_c'
        from racc/parser.rb:276:in `do_parse'
        from parser.y:386:in `block in parse'
        from /ydah/lrama/lib/lrama/report/duration.rb:14:in `report_duration'
        from parser.y:381:in `parse'
        from /ydah/lrama/lib/lrama/command.rb:11:in `run'
        from lrama:6:in `<main>'

これによって、よりエラーとなった位置が分かりやすくなり、開発の体験を少しでもよくすることができたのではないかと思っています。 また、Lramaの内部でいくつか残っていたraiseだけしていた箇所も、それぞれ例外が発生した理由を追加しています。（すべて倒しきったはず）

パフォーマンスの改善

Profileによるとlexerがそれなりに重かったです。 LexerではStringScannerを使って文法ファイルを読んでトークン列に分割していっているのですが、StringScanner#getchで一文字ずつ読んでいる箇所があり、ここがボトルネックになっているようでした。なので、StringScanner#scanで読めるところまで1回で読んでしまうように変更しました。

この変更によって、約30%ほど処理時間が改善しています。

Before

❯ lrama --trace=time -o parse.tmp.c --header=parse.tmp.h parse.tmp.y
parse    4.38929 s
compute_lr0_states    0.88006 s
compute_direct_read_sets    0.06813 s
compute_reads_relation    0.01174 s
compute_read_sets    0.04809 s
compute_includes_relation    0.72033 s
compute_lookback_relation    1.40715 s
compute_follow_sets    0.12471 s
compute_look_ahead_sets    1.00162 s
compute_conflicts    0.06503 s
compute_default_reduction    0.00617 s
compute_yydefact    0.08520 s
compute_yydefgoto    0.07973 s
sort_actions    0.00674 s
compute_packed_table    0.41180 s
render    0.09383 s

After

❯ lrama --trace=time -o parse.tmp.c --header=parse.tmp.h parse.tmp.y
parse    0.93149 s
compute_lr0_states    0.90139 s
compute_direct_read_sets    0.07115 s
compute_reads_relation    0.01218 s
compute_read_sets    0.04671 s
compute_includes_relation    0.69610 s
compute_lookback_relation    1.35323 s
compute_follow_sets    0.11844 s
compute_look_ahead_sets    1.01038 s
compute_conflicts    0.06607 s
compute_default_reduction    0.00666 s
compute_yydefact    0.08754 s
compute_yydefgoto    0.08042 s
sort_actions    0.00655 s
compute_packed_table    0.45709 s
render    0.08769 s

stackprofで見ても以下の通り、Lrama::Lexer#lex_c_codeという今回修正したメソッドの速度が改善した6ことが分かります。

Before

❯ bundle exec stackprof --limit 10 tmp/stackprof-cpu-myapp.dump
==================================
  Mode: cpu(1000)
  Samples: 6449 (3.30% miss rate)
  GC: 1784 (27.66%)
==================================
     TOTAL    (pct)     SAMPLES    (pct)     FRAME
      1858  (28.8%)        1858  (28.8%)     (sweeping)
      1305  (20.2%)        1216  (18.9%)     Lrama::Lexer#lex_c_code
       531   (8.2%)         371   (5.8%)     Struct#==
       785  (12.2%)         339   (5.3%)     Lrama::States#compute_look_ahead_sets
       294   (4.6%)         252   (3.9%)     Lrama::Context#compute_packed_table
       192   (3.0%)         192   (3.0%)     Integer#>>
       186   (2.9%)         186   (2.9%)     Integer#&
       188   (2.9%)         158   (2.4%)     Lrama::Lexer::Token#==
      3027  (46.9%)         147   (2.3%)     Array#each
       637   (9.9%)         138   (2.1%)     Lrama::States#compute_lookback_relation

After

❯ bundle exec stackprof --limit 10 tmp/stackprof-cpu-myapp.dump
==================================
  Mode: cpu(1000)
  Samples: 3711 (0.51% miss rate)
  GC: 186 (5.01%)
==================================
     TOTAL    (pct)     SAMPLES    (pct)     FRAME
       797  (21.5%)         338   (9.1%)     Lrama::States#compute_look_ahead_sets
       474  (12.8%)         307   (8.3%)     Struct#==
       329   (8.9%)         290   (7.8%)     Lrama::Context#compute_packed_table
       246   (6.6%)         240   (6.5%)     Lrama::Lexer#lex_c_code
       191   (5.1%)         191   (5.1%)     Integer#>>
       180   (4.9%)         180   (4.9%)     Integer#&
       187   (5.0%)         157   (4.2%)     Lrama::Lexer::Token#==
       592  (16.0%)         146   (3.9%)     Lrama::States#compute_lookback_relation
      3037  (81.8%)         138   (3.7%)     Array#each
       137   (3.7%)         137   (3.7%)     Lrama::States::Item#hash

さいごに

今回、紹介したものは細々とした対応が多かったかもしれないですが、少しずつでもLramaをより良くしていけたのではないかと思っています。 昨日の記事で紹介したParameterizing rulesの実装も着々と進んでいて、parse.yをより読みやすく理解しやすいものにしていくというゴールに向けて、着実に進んでいると感じています。 （また、個人的にはLramaのLexerを自作のLexer generatorで自動生成したものに置き換えたいなと思っていたりします。そちらも進めていきたいです。） 来年も引き続きやっていきたいと思っているので、よろしくお願いします。

  1. 4日ほど前にまったく同じコンセプトの記事があったような...↩
  2. とはいえ実際に活発に開発をしだしたのは8月頃からなので、実質4か月ほどです。↩
  3. 金子さん(@spikeolaf)のパーサーのお話とてもよくて（語彙力）やっていきが高まるんですよね。いつもありがとうございます。↩
  4. ruby/rubyにおいては対応前のLramaでもbuildに成功していたのでブロッカーにはなっていなかったのですが、ヘッダーファイルの名前を決め打ちで書く必要がなくなるのは良いので、この対応を行いました。↩
  5. こばじゅんさん(@junk0612)の大いなる偉業です。この変更により開発がとてもやりやすくなって最高です。↩
  6. 変更行はごく僅かなのに結果としてあらわれると、とても気持ちいいですね。↩