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

RubyでPEG使ってCのパーサ(のようなもの)書いてみた

More than 3 years have passed since last update.

RubyでCパーサのようなもの書いてみたという記事です。

Cパーサを書いたといってもPythonで実装されたpycparserのような厳密で完成度の高いCパーサではなく、実装も3日程度で済ませた雑実装なのであしからず。

リポジトリ: github.com/hsssnow23/Captain

サンプル
input:

typedef struct {
    unsigned int id;
    float x;
    float y;
} Actor;

output:

#<CTypedef:0x000000037809a8
 @from=
  #<CStruct:0x0000000376a068
   @body=
    [#<CVariable:0x000000034f0350
      @name="id",
      @type=
       #<CType:0x000000034f3780
        @const=false,
        @name="int",
        @pointer=false,
        @prefix="unsigned">,
      @value=nil>,
     #<CVariable:0x000000035b6ca8
      @name="x",
      @type=
       #<CType:0x000000035ad950
        @const=false,
        @name="float",
        @pointer=false,
        @prefix=nil>,
      @value=nil>,
     #<CVariable:0x000000036a0df8
      @name="y",
      @type=
       #<CType:0x000000036a3a30
        @const=false,
        @name="float",
        @pointer=false,
        @prefix=nil>,
      @value=nil>],
   @name=nil>,
 @to="Actor">

もともとCにアノテーションなどで付加情報を付け、コードの自動生成を行うツールのために作ったパーサなのですが、どうにも遅い。おそらく実装に使用したPEGパーサがおれおれ実装でPackrat Parsingしてないのが主な原因だと思います。なのでこの記事ではPEGパーサを実際に使ってみてどうだったかということを書きたいと思います。

先にざっくりまとめ

PEGのメリット

  • Rubyのような演算子オーバーロードができる言語ではDSLのように書けるのでわかりやすい。(lex yaccなどのパーサジェネレータはお作法が多いので若干とっつきづらいと思います)
  • 速度を度外視する単純なものならPEGパーサ自体の実装が楽。(最終的にPEGパーサ自体の実装は269行。)
  • 字句解析と構文解析を同時に行えるので手間がはぶける。よって正規表現のように手軽に使える。
  • 正規表現と違い括弧の対応付けなどのパースができる。

PEGのデメリット

  • 単純な実装だとO(n)で実行できない。
  • 左再帰ができない。

感想

楽。圧倒的に楽です。なにが楽かというと思い立ったらすぐに書き始められるというところが他のパーサに比べた大きなメリットかと思います。

字句解析すっ飛ばしてパーサ書いていきなり構文木作れるので、簡単なパーサだけど正規表現よりはリッチにやりたいなんてときには一番向いていると思います。

しかし、Cのパーサのようなすでに仕様としてあるもののパーサをPEGで書くのは少し大変かなと思いました。既存のプログラミング言語の多くはlexやyaccなどのパーサジェネレータで作られており、それらとの整合性を確保するのが大変だということと、PEGはまだ歴史が浅く、どこまでパースできるかがあまりわかっていないらしいです。(正直、隅をつつくようなC言語のソースだとパースできる自信薄い)

ただし、パースした内容によってパーサ自体が変化するようなパーサは書きやすそうと感じました。(それが必要になる場面は少ないとは思いますが)

まとめ

自分の最終的な結論としてPEGは最高におすすめのパーサです。

しかし、自分で仕様を決めることができる小さいフォーマットのパーサは間違いなく向いていると思いますが、その他に使用するのは微妙かもしれないと思いました。

参考記事:
http://kmizu.hatenablog.com/entry/20100203/1265183754

nnn-school
IT×グローバル社会を生き抜く“創造力”を身につけ、世界で活躍する人材を育成する。
https://nnn.ed.jp/
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
ユーザーは見つかりませんでした