その手の平は尻もつかめるさ

ギジュツ的な事をメーンで書く予定です

トークナイザーとパーザーについて,結合するということについて

トークナイザーとパーザーについて,それに準ずる物を書いていて,その最中ふと思った事について記す.

基本的にトークナイザーは対象となる文字列を,或る最小限の意味を持つトークンに分解してトークン列を導出するというのが責務で,これのみに着目するのであれば実装は (それほどまで) 難しいものにはならない *1
厄介なのはパーザーの方で,パーザーはトークナイザーが吐き出したトークンを組み合わせてある意味のある文節というか文脈というか,そういう感じの扱うのに際して便利な単位に落としこむのが仕事なのだけれど,こちらの方は様々な組み合わせが存在するために複雑になる.伴ってコードの量も多くなる.圧倒的にトークナイザーを書くよりも実装のコストが高い.
そうした状況を解決する為に,愚鈍なトークナイザーを賢いトークナイザーにしてしまうという方法が考えられる.トークナイザーが単純な文字列の分解だけではなく,その過程で附随的な情報をトークンに付け加えたり,或いはトークナイザーのレベルでいくつかのトークンをひとまとめにしてしまうというような「賢い」処理を行い,トークナイザーの成果物をパーザーフレンドリーにすることで,パーザーの実装コストを緩和するという方法だ.
これは大抵の場合,トークナイザーとパーザーが完全に独立している時の総合コストよりも低くなる感じがするんだけど,そうなるとトークナイザーとパーザーが結合を始めてしまい,トークナイザーを別の所で使ったり,或いは逆でパーザーのトークナイズエンジンを変えたりすることがままならなくなる.
と,ここらへんトレードオフだと思っていて,まあよく考えたほうが良いですよねという話で,実際誰も使わないようなトークナイザー・パーザーだったら密結合させてエイヤで実装したほうが良いと思う.逆に超有用 (だと思われるよう) なものの場合はやっぱり双方独立させたほうが良いのだろうとも思うけど,そこまで有用なものなのだったら書かずとも既にこの世に存在している可能性が高いし,もしかしたら密結合でソイヤと実装してしまってもどこからともなく神コミッターが現れて一晩で結合をひっぺがしてくれるかも知れないのでとにかく書いてしまうというのが重要である.

*1:例外はあると思う