Help us understand the problem. What is going on with this article?

パーサジェネレータ"caper"の紹介

More than 3 years have passed since last update.

パーサジェネレータ caper

"caper"  (github)は拙作のパーサジェネレータです。yaccやbisonなどと同じ場所で使うツールです。

基本的にはC++コードを生成するために作ったのですが、そのほかにもJavascript, D, Java, C#などのコードを出力することができます。

特長

大きなところでは、こんな特長があります。

  • 出力コードが全部テンプレートクラスでヘッダファイル一つなので、ライブラリなどをリンクする必要がない
  • 出力コードが大変ヒューマンリーダブル(手書きで書いたと強弁できるLALRパーサ、というコンセプト)
  • PUSH型(パーサは常に受身で、トークンをポストするまで動かない)

そのほかの特長については、http://jonigata.github.io/caper/caper_more.html を御覧ください。

歴史など

このソフトは結構古いソフトで、初出は2006年です。なんで今頃また持ち出してきたかというと、とある人から「大きい文法で7分かかってたのを30秒にした」というプルリクエストを受け取ったためです。それをきっかけに、今まで戦略的なアルゴリズムの問題で遅いと思ってたのが、実は戦術的な問題で遅かっただけなのでは? と疑念を抱いていろいろ見なおしてみたところ、3秒まで縮まってしまいました。さらに、すでにほとんど忘れていたソースを読みなおすことによってほぼ把握できたため、積んでいた拡張リクエスト(C++11対応、EBNF対応)を消化する気になってしまったわけです。

新仕様

EBNF

というわけで、そこのドキュメントにはまだ書いてありませんが、githubの最新バージョンでは、EBNF対応が実装してあります。対応する機能は以下のとおりです。

  • '*' 0個以上のリスト
  • '+' 1個以上のリスト
  • '?' 0個または1個
  • '/' (オリジナル仕様) a/bの形で指定すると、a(ba)*にマッチしてbを捨てる(コンマ区切りリストなどに有用)

カッコには対応していません。caperの型付けの強い仕様だと、カッコには結局セマンティックアクションを指定しなければならず、「名前を考えなくて良い」以外のメリットが見当たらなかったためです。

EBNF拡張の文法等については https://github.com/jonigata/caper/tree/master/caper/samples/grammar にある"list0" "list1" "list2" "optional"あたりを参考にしてください。これらの文法ファイルを使う側はどうすればよいかについては、https://github.com/jonigata/caper/tree/master/caper/samples/cpp この辺りを参考にしてください。

エラーリカバリ

また、簡単なエラーリカバリを実装してあります。機能は多分yaccとだいたい同じです。

%recover error;

で"error"という識別子をリカバリ指定用識別子として利用できるようになります。

文法等についてはサンプルディレクトリの「recovery0」「recovery1」を参考にしてください。

ジェネレータをリライト

その他、この機会に書きづらかったジェネレータをヒアドキュメント的な記法で一新しました。新しいジェネレータを作るのも簡単になっていると思います。

関連情報

各言語ジェネレータ

上記出力可能な言語のうちC++, Javascript, Dについては最近書きなおしたので新しい仕様に追従していますが、C#・Javaに関しては気に入ってくださったユーザの方からいただいたコードである上、自分で使わない言語なので今でもcaperの仕様変更や言語自体の仕様変更に追従して動く状態なのかどうか自信がありません。どなたか得意な方に書きなおして貰えると嬉しいです。ジェネレータを書く場合は、現状のまま当該言語で一度hello0.cpgなどからパーサを出力しておいて、上記3つの中から近いものを選んで置き換え、最初の出力を見ながら直すのが一番ラクなのではないかと思います。

その他の言語についてもプルリクエストは大歓迎です。

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした