Peggy - 構文

Peggyの構文

Peggyは文法としてPEGを採用しています。 記法はWikipediaのエントリのものをベースにしています。

PeggyによるPeggyの文法の定義

ここ に完全なPeggyの文法の定義があります。 これはPeggy自身のパーザのブートストラップに用いられています。

字句ルール

Peggyの識別子は小文字から始まり、英字、数字、アンダースコアからなる文字列です。

ident ::: String = [a-z] [0-9a-zA-Z_]* { $1 : $2 }

空白およびコメントは無視されます。 スペースは単にデリミタとしての働きをします。 ソースコードのレイアウトは自由です。

コメント

Haskellライクなコメントが利用できます。

-- これはコメントです
hoge = ...
{- 範囲コメント {- および、ネストされたコメント -} も使えます -}
moge = ...

非終端記号の定義

Peggyの構文は、非終端記号の定義の集合です。 それぞれの定義は次のような形をしています。

<name> :: <Type> = <expr>

もしくは、次の形です。

<name> ::: <Type> = <expr>

は非終端記号の名前です。 はその非終端記号のパーズ結果の（Haskellの）型です。型は必ず指定しなければいけません。 型は double-colon (::)、あるいは triple-colon (:::) で区切られます。 triple-colonは特別な意味があります。 その非終端記号が token として扱われるようになります （token の詳しい振る舞いはこちらを参照）。 定義の右辺は幾つかの代替部からなります。それらは ‘/’ によって区切られます。 各代替部は式の列です。

典型的な非終端記号の定義は次のような形をしています。

<name> :: <Type>
  = sequence ...
  / sequence ...
  ...

左再帰

Peggyは左再帰を許しています。 これは文法を自動的に左再帰を含まない形に変換することによって実現されています。

式

式の構文とセマンティクスはPEGのものベースにしています。 式は次のルールから構成されます。

文字列リテラル

文字列リテラルは、正確にその文字列にマッチします。

'hoge' -- 文字の列
"hoge" -- 文字列"トークン"

シングルクオート (’) で囲われたリテラルは“rawリテラルです”。 正確にその文字列にマッチします。 ダブルクオート (") で囲われたリテラルは 文字列 token です。 この文字列は前後の空白を読み飛ばし、かつ前後がデリミタでなければマッチしません。 token の振る舞いの詳細はこちらを参照。

文字列リテラルは値を持ちません。

文字クラス

正規表現でおなじみの文字クラスが利用できます。

[a-zA-Z0-9_] -- 小文字、大文字、数字、そしてアンダースコア
[^0-9] -- 数字以外の文字

文字クラスはマッチした文字を値として返します。

順序付き選択

順序付き選択 は ‘/’ で区切られた式の列です。

<e1> / <e2> /  ...

これはいずれかの代替部とマッチします。 文脈自由文法 (CFG) とは異なり、PEGは一番左のマッチを常に選択します。 ゆえに式の順番は重要です。 また、すべての部分式の型は同じである必要があります。

列

列 は式の列です。

<e1> <e2> ...

これら部分式の列にマッチします。

セマンティクスの注釈

各 列 にはセマンティクスの注釈をつけることができます。 各ルールに対して、それが返す値を（Haskellの式で）指定します。

<e1> <e2> ... { Haskellの式 ... }

Haskellの式、にはひとつのHaskellの式を記述します。 例えば次のような例です。

expr :: Int
  = expr "+" term { $1 + $2 }

Haskellの式には プレースホルダ を含めることができます。 これは $<num> の形をしており、n番目の部分式の値がバインドされています。 リテラル と 先読み述語 に対しては値がバインドされません。 その項は番号をスキップされます（上の例を参照）。

セマンティクスのアノテーションを持たない 列 は、部分式の値のタプルを返します。

hoge :: (Int, Int, Int)
  = integer "," integer "," integer

ソースコードの位置情報

プレースホルダとして、更に次の2つが利用できます。

$p -- returns SrcPos
$s -- returns SrcLoc

前者はこの 列 がマッチした位置の先頭を表す位置情報に、 後者はマッチした位置の範囲に、 それぞれバインドされます。

部分式への名前付け

部分式の値に対して、プレースホルダを使うほか、名前をつけることもできます。 名前付けは、:expr の形で行います。

for :: Stmt
  = "for" "(" init:expr? ";" cond:expr? ";" post:expr? ")" "{" body:stmt* "}"
      { ForStmt init cond post body }

0個以上の繰り返し、1個以上の繰り返し

後置演算子 ‘*’ は0個以上の繰り返しを表します。

<e>*

後置演算子 ‘+’ は1個以上の繰り返しを表します。

<e>+

後置演算子 ’?’ は1個または0個の出現を表します。

<e>?

CFGとは異なり、これらの演算子は常に“貪欲”に、 つまり可能な限り多くマッチするように振る舞います。

‘*’ と ‘+’ は値のリストを返します。 ’?’ は Maybe a を返します。

And述語、Not述語

前置演算子 ‘&’ は、先読み述語です。 引数の式のパーズを試み、成功すれば成功、失敗すれば失敗になりますが、 いずれの場合も入力文字を消費しません。

&<e>

前置演算子 ’!’ は ‘&’ と似ていますが、 こちらは引数のパーズが失敗したときに成功、成功したときに失敗という振る舞いです。

!<e>

先読み述語の簡単な例として、 C++風のネスト可能コメントのパーザを挙げておきます。

regionComment :: ()
  = '/*' (regionComment / (!"*/" . { () }))* '*/' { () }

トークンの振る舞い

Peggyは（暗黙的に） token を扱います。 token は、デリミタによって区切られた文字の列です。 これは前後の空白を読み飛ばし、また文字列の前後にデリミタを期待します （例えば、token “for” は 文字列 “foreach” にはマッチしない）。

空白およびデリミタの挙動は、それぞれに対応する非終端記号、“space”、“delimiter” を定義することによって変更することができます。

space :: () = [ \r\n\t] { () } / lineComment / recionComment
delimiter :: () = [()[]{}<>;:,./\] { () }

これらが与えられない場合、デフォルトの挙動が利用されます。