改めて書いてみて色々気付きがあったなという記事です。
成果物リポジトリ
Lexerの改善
1トークン分を読み進めてトークンを取得する #advance を実装していましたが、自分で実装した割に呼び出した後にlexerがどういった状態になるかが曖昧になっていました。読み込み位置と、その読み込み位置に対してどのトークンが取得できるのかを改めて整理してみました。それに加えて #token で取得できるトークンに加えて、さらにその次のトークンを取得する #peek も定義しています。
ここら辺をコメントに記載した箇所: https://github.com/kozy4324/simple-json-parser/blob/0ee2c886047f04b2825db9474034fb8f5774d8de/lib/simple/json/lexer.rb#L10-L39
Parserの改善
実装時の注意点を以下のように整理して実装に取り組みました。
- 基本は1文法ルールに1パースメソッドが対応する
- 読み込み位置はパースメソッド開始時点でその文法の先頭にあり、終了時点で末尾まで進むものとする
- トークン列で考えるとメソッド開始時点でその文法の直前トークン、終了時点でその文法の最終トークンが token から取得できる
ここら辺をコメントに記載した箇所: https://github.com/kozy4324/simple-json-parser/blob/0ee2c886047f04b2825db9474034fb8f5774d8de/lib/simple/json/parser.rb#L11-L26
これにより、例えば object の1つの key & value を処理する parse_member は以下のような実装にできました。ホワイトスペースを処理するタイミングも文法通りにしています。
# member ::= ws string ws ':' element
def parse_member
parse_ws
key = parse_string
parse_ws
@lexer.advance # ':'
value = parse_element
{ key => value }
end
numberのパース処理
文法上は以下の通りです。
number ::= integer | fraction | exponent integer ::= digit | onenine digits | '-' digit | '-' onenine digits digits ::= digit | digit digits digit ::= '0' | onenine onenine ::= '1' . '9' fraction ::= "" | '.' digits exponent "" | 'E' sign digits | 'e' sign digits sign ::= "" | '+' | '-'
これは1つのメソッドで対応してみました。 Lexer#number_value がその実態です。
INTEGER_REGEXP = /-?(?:0(?![0-9])|[1-9][0-9]*)/
FRACTION_REGEXP = /\.[0-9]+/
EXPONENT_REGEXP = /[Ee][+-]?[0-9]+/
NUMBER_REGEXP = /(#{INTEGER_REGEXP})(#{FRACTION_REGEXP})?(#{EXPONENT_REGEXP})?/
# 現在読み込み位置以降の数値を取得して読み込み位置を進める
def number_value = @scan.scan(NUMBER_REGEXP).then { |s| /[.Ee]/ =~ s ? s.to_f : s.to_i }
stringのパース処理
文法はこうです。
string ::= '"' characters '"' characters ::= "" | character characters character ::= '0020' . '10FFFF' - '"' - '\' | '\' escape escape ::= '"' | '\' | '/' | 'b' | 'f' | 'n' | 'r' | 't' | 'u' hex hex hex hex hex ::= digit | 'A' . 'F' | 'a' . 'f'
バックスラッシュのエスケープを正規表現で解決するには悩ましい。ということでこちらは1文字ずつ処理する形式で実装してみました。
# 現在読み込み位置以降の文字列値を取得して読み込み位置を進める
def string_value # rubocop:disable Metrics/MethodLength,Metrics/AbcSize,Metrics/CyclomaticComplexity
string = +""
@scan.getch # "
until (c = @scan.getch) == '"'
raise "unexpected end of input." if c.nil?
raise "invalid ASCII control character in string." if c.ord < 20
if c == "\\"
c = @scan.getch # escape
case c.ord
when 34, 92, 47 # " \ /
string << c
when 98 # b
string << 8.chr # BS
when 102 # f
string << 12.chr # FF
when 110 # n
string << 10.chr # LF
when 114 # r
string << 13.chr # CR
when 116 # t
string << 9.chr # HT
when 117 # u
hex4 = @scan.scan(/[0-9a-fA-F]{4}/)
string << hex4.to_i(16).chr(Encoding::UTF_8)
else # rubocop:disable Lint/DuplicateBranch
# JSON仕様上は許可されないescape文字だがJSON.parseでは無視する振る舞いなのでそれに合わせる
string << c
end
else
string << c
end
end
string
end
結局実装しなかったこと
- 文法が崩れている時のエラー処理
- 期待したものと異なるトークンがやってきた時のケアとか
- object や array の閉じ忘れとか
- 文法エラー時の適切なエラーメッセージ
- 〇を期待したけど△がやってきたよとか
- ソース文字列中のこの場所でエラーだったよとか
ただしパース処理中のここら辺でエラー処理を実装すれば良さそうだなという感触は掴みました。
発展系？
文法的に不完全な状態でも簡単なルールであれば欠落したトークンを保管してあげることなどができそうです。つまりそれがエラートレランスな機能を持つパーサーということか？と少し思いました。
文法ありきな話ではありますが、文法エラー時にどういった戦略をとるか、またはとれるかを考えてみると面白いかもしれません。
とはいえRubyの文法に対してPrismはどんなエラートレランスが実現できているんだろうか、JSONに対して複雑性が全然違いそうなので全く想像できていないなぁともなりました。そういった観点でPrismの実装も眺められるようになるといいかもしれませんね。
