top page > computer > haskell > packages > papillon > features.html
更新日:
文責: 重城良国

papillonの特徴

PEGの特徴

理解しやすい表記

文脈自由文法を表記するEBNF記法は人間にとってわかりやすい。それに比べて、機械が解釈するための文法の多くは、実行効率のためわかりやすさや、書きやすさが犠牲になる。PEG文法は「選択」が「試行」となる以外はEBNF記法に近いため、読み書きが比較的簡単となる。

表現できる文法が広い

pappyの論文(英語)

文脈自由文法の大部分と、その範囲を越える文脈依存文法の一部を表現することができる。任意のLL(k), LR(k)言語を解析することができ、無限先読みが必要でshift/reduce解析器では解析できない言語も解析することができる。

曖昧性のない解析

PEGでは「選択」の代わりに「試行」を使っている。つまり、選択肢の左から順に試していって、一致すればそれ以上の試行は行わない。これによって、ひとつの並びが複数の解析結果となることがなくなる。

線形時間で解析できる

解析に曖昧性がないため、バックトラックの範囲を小さくしぼることができる。ある入力に対して、それぞれの規則は単一の値しか持たない。よって解析結果をメモ化することにより、線形時間での解析が可能となる。

papillonの特徴

二通りの使用方法

papillonは二通りの使用方法がある。peggy同様にQuasiQuotes拡張を利用してコード内に文法定義をうめこむ方法と、pappyのようにHaskellコードを生成する方法だ。

統一的な文法

構終端記号の定義内のそれぞれの葉は「パターン:表現[ガード]」という形で表現されるため、出来上がるHaskellコードの予測がしやすい。つまり、以下のようなコードをイメージすることができる。

case 表現 of
	パターン | ガード -> ...

略記法

表現は省略可能

表現を省略するとトークンひとつを指定したのと同じことになる。トークンがCharの場合、例えばd:[isDigit d]のように記述することができる。

ガードは省略可能

ガードを省略することもできる。普通にx:someのような形で表現できるということ。

両方を省略すると

表現とガードの両方を省略することもできる。つまり、パターンのみを表記するということ。トークンがCharの場合で考えると、cのように書けば、任意の一文字が表現できる。それだけでなくHaskellでは文字もパターンとなれるので、'x'のようにすれば文字'x'にマッチするルールとなる。これを使うことで、以下のような書きかたが可能になる。

papillon :: () = 'p' 'a' 'p' 'i' 'l' 'l' 'o' 'n'

特別な略記法

<guard>のように表記することで、(c:[guard c] { c })を表すことができる。

トークン列が指定可能

指定することで文字列以外のトークン列を指定することができる。トークン列はトークンと関係づけられた型である必要がある。たとえば今のところByteStringはCharと関係づけられている(本当はByteStringはWord8と関係づけるべきかもしれない)。

モナドが指定可能

基礎となるモナドを指定することができる。とくにStateモナドを指定することで、状態付きのパーサを作成することができる。IOモナドを基礎とすれば、時間によってパースのしかたを変えるとかもできる。

プレフィックスが指定可能

プレフィックスを指定することで、コード内の他の変数との競合を避けることができる。

左再帰の自動変換はしない

任意の左再帰の自動変換は難しい。特定のタイプの左再帰のみ自動変換が簡単にできる。そのうえ、規則の数が多くなってくると、左再帰の自動変換にはひどく時間がかかる処理となってくる。部分的にしかできないうえに時間がかかるので、左再帰の自動変換はしないことにした。PEGを理解していれば左再帰の問題について知っているはずだし、逆に左再帰の問題を知らないでPEGをまともに書くとこはできないと判断した。

「作られた経緯」へもどる 「到るまでの道 (工事中 20%)」へ

正当なCSSです! HTML5 Powered with CSS3 / styling, and Semantics