2023/03/01
構文解析器完成
やったこと
- タイガーブック、構文解析器の実装
一日中、構文解析器を作ってた。
昨日、おおまかに ocamlyacc での文法の定義と ocamlyacc で書いた parser を実行ファイルで呼び出す部分を書いて、今日は shift/reduce conflict の除去をして構文解析器として動くところまでできた。
また lexer, parser のエラーメッセージを改善して、どの行のどこの文字で何のエラーが吐かれたかを表示するようにした。
構文解析器のエラー回復はタイガーブックに載っている ML-Yacc では Burke-Fischer のエラー修正が使われているようだが、ocamlyacc ではどのようになっているか始めはよく分からなかった。
ocamlyacc では %change 修飾子や %value 修飾子が無さそうなことや、公式に以下のような記述があることから、 error 記号を使った局所的なエラー回復をしていると思う。
In error recovery mode, the parser discards states from the stack until it reaches a place where the error token can be shifted. It then discards tokens from the input until it finds three successive tokens that can be accepted, and starts processing with the first of these. If no state can be uncovered where the error token can be shifted, then the parser aborts by raising the Parsing.Parse_error exception.
思ったこと
ocamlyacc を書いていて、エラー表示・回復まわりで気づいたことをまとめておく。
.mlyで exception を定義しても他のファイルから参照できないため、 exception はどこかでまとめて定義しておいて lex でも yacc でもそれを参照するといいかも- ocamlyacc でエラーを投げるときにデフォルトで発生する Parsing.Parse_error だと "syntax error" しか情報が渡ってこないため、 action 部で工夫してエラー情報を発生させる
- 解析がどこまで進んだかは Parsing パッケージの symbol_start などで取得できる
- error 記号を使った文法を定義してエラー回復できるようにする
- action でエラーを raise するとそこで解析が止まってしまうため、標準出力にエラー内容の文字列を出力するだけにしてエラー回復して解析を続けさせる
今日の英会話
チームラボプラネッツ TOKYO についての記事。
なんで日本国内の一イベントがデイリーニュースの記事になってるんだと思ったら、 DMM が Founding Partner になっていた。