実装Note - ruby構文解析の難しさ

Ruby は、不必要に構文が複雑になっている。最初期からある構文がまずく (曖昧で), 実装が複雑になっている。その割に独自の利便性の高い構文があるわけではない。CommonLisp のほうが、よほどできることが大きい。

サブセットと割り切って、簡単にした。

パーサの大きさ

けっこう小さなサブセットと割り切ったつもりだが、それでも合わせて3,000行に膨らんでしまった。

  • ruby 3.1
    • parse.y Bisonファイル 14,000行. 字句解析は 行9,230 辺りから parser_yylex() 関数.
    • lex.c gperf コマンドで生成. 入力 = defs/keywords ファイル
    • node.h AST ノードを定める。104 種類, すごい多い。
  • minilang
    • parse.yy Bisonファイル 1,200 行程度
    • lexer.cpp 手書きの字句解析器。1,700行程度
    • ast.h ノードを定める。36 種類。 Ruby ではメソッド呼出しになっている include, extend, attr_accessor, attr_reader, attr_writer を予約語化

字句解析は, minilang v0.6 では Quex という字句解析器生成系を使ったが、不十分で、結局手書きした。

Rubyは文脈自由文法ではない

文脈依存キーワード contextual keywords は、今どき、どのプログラミング言語でも見られる。例えば JavaScript の async はキーワードではない。C# も互換性維持のために多い。

Ruby の難しさはそこではなく、スクリプトの字面のつながり方だけでは構文が一意に定まらず、コンパイル時に意味を併用しなければならない。C/C++ も同様。(context-free grammar ではない.) 未実装 [incompat]

例えばこの記事「あなたが理解できない，たった一行のRubyのコード（動的言語に対する静的解析の限界)」は完全に誤認しているが、それでも, "/" の曖昧性を解決するためには, f が変数かどうかを踏まえなければならない。

Ruby
[RAW]
  1. # ランダムに定義を振り分ける
  2. if rand >= 0.5
  3. # 正規表現の関数として定義する
  4. # Crystal: Error: can't declare def dynamically
  5. def f( reg_exp )
  6. str = "gggh"
  7. #return str.match( reg_exp ) != nil
  8. end
  10. # Crystal: g を定義しても, f が定義されない経路を見破る
  11. # 24 | p f /g+h/i
  12. # ^
  13. # Error: undefined method '/' for Nil (compile-time type is (Int32 | Nil))
  14. g = 5
  15. else
  16. # 変数に数値を代入
  17. f = 2 # ここをコメントアウトすると、f は関数と見做される。
  18. # 静的解析で構文が決まる。元記事は誤認している。
  19. g = 1
  20. h = 2
  21. i = 1
  22. end
  24. # 演算結果を `p` で出力する
  25. #p f(/g+h/i) .. これは曖昧ではない
  26. p( f /g+h/i )
  28. # Ruby は半々でエラー. ただ、関数の f ではなく変数の f が見つからないエラー.
  29. # -> 構文解析は除算一択になっている。構文解析が曖昧なのではない。
  30. # undefined method `/' for nil:NilClass (NoMethodError)
  31. # p( f /g+h/i )
  32. # ^

正規表現リテラルかどうかの判定は、1パス目でやらなければならない。あらゆる文字が含まれうるので、先読みして決めることはできない。

意味は同じはずが、エラーになったり通ったり

if 式と後置 if とで挙動が異なる。抽象構文木 (AST) も異なる。

Ruby
[RAW]
  1. if a # undefined local variable or method `a' for main:Object (NameError)
  2. a = 42
  3. end
  5. a = 42 if a # これは通る。意味は同じだが挙動が異なる
  6. p a
  8. code = "a = 42 if a"
  9. ast = RubyVM::AbstractSyntaxTree.parse(code)
  10. pp ast
  11. #=> (SCOPE@1:0-1:11 tbl: [:a] args: nil body: (IF@1:0-1:11 (LVAR@1:10-1:11 :a) (LASGN@1:0-1:6 :a (LIT@1:4-1:6 42)) nil))
  12. # local-variable `LVAR` に解決されている。
  14. code = <<-EOS
  15. if a
  16. a = 42
  17. end
  18. EOS
  19. ast = RubyVM::AbstractSyntaxTree.parse(code)
  20. pp ast
  21. #=> (SCOPE@1:0-3:5 tbl: [:a] args: nil body: (IF@1:2-3:5 (VCALL@1:5-1:6 :a) (LASGN@2:4-2:10 :a (LIT@2:8-2:10 42)) nil))
  22. # local-variable or method `VCALL` が解決されていない。

上のスクリプトは、単に未代入のローカル変数の評価はエラーにしたらいいのでは? という話。

それはともかく, Ruby は Lisp-2 で、変数の名前空間と関数のそれが分かれている。変数と同名の関数があってよい (定義できる)。しかし、関数呼出しのカッコを省略できる (仕様がまずい) ので、字面から変数評価か関数呼出しかが区別できない。なので, if 式の条件式のほうは AST node VCALL (未解決) になっている。

1パス目では確かに, 単に f と書いたときにどちらの意味か分からないが、構築した AST を静的解析すれば、どちらか分かる。型チェックもここで入れることができる。[[まだ未実装]]