June 22, 2008

EBNFをRacc形式に変換

前回の記事『VHDLの可視化ができないものかと』のコメント欄に少し書きましたが、VHDLを可視化できないものかと思案中です。とりあえずプログラミング系のスキル向上も兼ねて、VHDLのパーサくらいこさえてみようと一念発起してみました。パーサジェネレータとしてはRubyベースのRaccを使うことにします。

VHDLはその定義が、定義記法の1つであるBNFを拡張したEBNFによって行われています。例えばVHDL-93のEBNF定義は『Hyperlinked VHDL-93 BNF Syntax』にあります。この定義をパーサジェネレータにうまいこと食わせられれば、パーサ生成に向けた第一歩をクリアすることができるという寸法です。

しかしながらRaccはBNFに近い形式のみでEBNFをそのまま受け付けてくれるわけではありません。特に問題となるのが、EBNFのみで可能なブレース('[', ']')やブラケット('{', '}')を使った省略可能及び繰り返しの表記で、これをBNFでも表記可能な再帰定義で書き換えなければなりません。

書き換えの例をあげると以下のようになります。EBNF、それを変換したBNFの順に示します。

VHDLクラスのまじめな言語になると、これを手動で変換というのはかなり大変です。そこでRubyでVHDLのEBNF用変換スクリプトebnf2raccy.rbを書いてみました。これで記法の問題、並びにキーワードの終端記号化を行っています。VHDLのEBNF定義ebnf.txtから、このスクリプトによって生成したRacc用入力ファイルをRaccで処理したところ、shift/reduce、reduce/reduce conflictsがいくつか出ていますが、EBNFからBNFへの記法変換についてはうまくいっているようです。

これらをもとにパーサをこさえようとしていますが、現在のところ入力文字列を意味単位(トークン)に区切ってくれるスキャナとの関係をどうしようかと思案中です。VHDLの定義自体は文字指向、つまり一文字ずつ処理するように作ってあるようですが、パーサとしては字句指向、つまりは単語単位でリテラルとしてスキャナからトークンが生成されたほうが都合がよいと思います。そこでVHDLの定義の中で、文字を結合して意味を形作っている下位部分をいくつか書き換えようと考えています。
またVHDLの定義をみたところ、いくつか不足している規則があるようです。例えばsignal_nameなどのアンダーバーがついてる規則について定義がありません。nameという規則はあるのでaliasであると考えられます。パーサとして機能させるためには、これらについても正しく関係付けを行わないといけないので少々厄介です。

※(2008/6/24)正規表現を使ってリテラル単位でスキャナからトークンが生成されるように変更してみました。リンク先のファイルも更新してあります。

※※(2008/6/25)キーワードと規則名が一部被っていたことに愕然としました。literal、range等です。BNF側を修正することで対応しました。また今後の方針ですが、VHDLの文法がなかなかお茶目のよう(定義済みの名前と定義がない名前で文法上の動作をかえる必要があるらしい、トークンの1つ先読みだけでは完全に文法が定まらない?)で、これをどうやってRaccが採用しているLALR(1)で実現するか難しいところです。おそらくアクションと組合わせて、next_tokenでスキャナからトークンを返す直前にちょっとした細工をかます必要があるのではないかと考えています。

16:52 fenrir が投稿 : 固定リンク | | | トラックバック
このエントリーのトラックバックURL: https://fenrir.naruoka.org/mt/mt-tb.cgi/646