Peggy:
新しい時代のパーザジェネレータ
田中英行 tanaka.hideyuki@gmail.com
2011-12-16 @ Haskell忘年会
Peggy:
自己紹介
- 田中英行 (@tanakh, http://tanakh.jp)
- (株)Preferred Infrastructure 勤務
- C++ 書いてます
- Haskell愛好家 (2004～)
- Learn You a Haskell for Great Good! 翻訳中
- 来春予定
- C81関数型イカ娘本寄稿予定
- SS2篇
Peggy: 全く新しいパーザジェネレータ
Peggyとは？
- パーザジェネレータのモダンな実装
- 新しい構文解析アルゴリズム
- シンプル・簡単・強力な記法
- Quasi-Quoterである
- Haskellコードへのシームレスな組み込み
- Standalone なパーザとしても利用可能
- Quasi-Quoter生成機能
- Haskellコードのシームレスな生成
- Unquoter生成機能
- Haskellコードとシームレスにインタラクション
Why Peggy?
- 典型的なボトムアップパーザはフラストトレーティング
- コンフリクト
- 構文
- 表現力 (Scanner, Parserそれぞれ)
- 貧弱なエラーメッセージ
- HaskellにおけるQuasiQuoter機運の高まり
- 実用例増えてきた (なんとか-qq パッケージがたくさん)
- しかし、TemplateHaskellのコードを書くのは大変
- Unquoteをサポートさせると更に大変…
- そこでPeggy！
既存研究
- Yacc
- LALR(1)
- Bison
- LALR(1) / GLR
- ANTLR / JavaCC
- LL(k)
- Parsec
- LL(1|k)
PEG(Parsing Expression Grammer：解析表現文法) とは
形式言語の文法表現の一つ
CFGに似ているが、CFGとは違う
- 比較的最近定式化された [Ford 2002, 2004]
- トップダウンパージングの拡張
PEGの利点
- 曖昧さがない
- Shift/Reduce コンフリクトがない
- 無限の先読みが可能
- CFGで表せないものも表現できる
- (CFG ⊂ PEG) かどうかは未解決
- Scanner を分けて書く必要がない
- 記述がシンプルに
- (先読みを許しつつ)入力長の線形時間でパーズ可能
- しかもアルゴリズムがシンプル
PEGの欠点
- 歴史が浅く、利用例が少ない
- LALR構文解析は非常に歴史がある
- 表現可能な言語の範囲が未解決
- 例：回文はPEGか否か
Packrat Parser
- PEGを線形時間で解析するアルゴリズム
- DPによるアルゴリズム
- 詳細は別ページに譲ります
- Packrat Parsing: a Practical Linear -
Time Algorithm with Backtracking
Peggy入門
文法概要
- パーザ定義の列
- すべての非終端記号が各々型を持ったパーザになる
-- Peggy QuasiQuoter
[peggy|
parens :: Int -- パーザの型
= "(" parens ")" { $1 + 1 } -- 定義
/ "" { 0 }
hoge :: String = "aiueo" -- 空白・改行は意味を持たない
foo :: ()
= ("abc" / "def") "ghi" -- 任意の式を括弧で囲える
|]
-- main routine
main :: IO ()
main = print . parseString parens "<stdin>" =<< getContents構文一通り (1)
- 文字クラス
identChar :: Char = [_a-zA-Z0-9]- 繰り返し
ident0 :: String = identChar*
ident1 :: String = identChar+構文一通り (2)
- オプショナル
mbident :: Maybe String = ident?- セマンティクス注釈
number :: Int = [0-9]+ { read $1 }構文一通り (3)
- Predicate
foo :: String = !number ident -- 否定
bar :: String = &ident ident -- 肯定使いやすさのための工夫(1)
- 右再帰の除去
- PEGでは、LL構文解析と同様、右再帰が許されない
- Peggyでは、利便性のために自動右再帰除去を実装
- 間接右再帰は未サポートです (’>_<`)
- トークンのサポート
- Scannerが無いため、字句の区切りの処理が面倒
- 例： inta; // <- こういうのを許さないようにしたい
- デリミタのカスタマイズ
- Scannerが無いため、字句の区切りの処理が面倒
- 空白文字のカスタマイズ
- 空白文字として任意のパーザを指定できる
- C言語スタイルのコメント読み飛ばしなど
- 空白文字として任意のパーザを指定できる
- ソースロケーションを簡単に挿入する機能
使いやすさのための工夫(2)
- 値がついて欲しいところだけ値がつく
forStmt :: Stmt
= "for" "(" expr? ";" expr? ";" expr? ")" stmt
{ ForStmt $1 $2 $3 $4 }- 名前へのバインド
forStmt :: Stmt
= "for" "(" init:expr? ";" cond:expr? ";" post:expr? ")" "{" body:stmt* "}"
{ ForStmt init cond post body }使いやすさのための工夫(3)
- PEGに対する構文拡張
- セパレータ付き繰り返し
- Haskellの式によるPredicate
args :: [Expr]
= (expr, ",") -- 0 回以上
args1 :: [Expr]
= (expr; ",") -- 1 回以上トークン仕様
- 連続したアルファベットまたは数字
- 連続した記号
- デリミタでの終端は許される
構文糖衣
- ダブルクオートで囲われた文字列はトークン、 シングルクオートは単なる文字列
token :: String = "hoge" -- トークン- hoge ::: type と書くとトークンになる
number ::: Int
= [0-9]+ { read $1 }実際の例
四則演算
exp :: Double
= exp "+" fact { $1 + $2 }
/ exp "-" fact { $1 - $2 }
/ fact
fact :: Double
= fact "*" term { $1 * $2 }
/ fact "/" term { $1 / $2 }
/ term
term :: Double
= "(" exp ")"
/ number
number ::: Double
= ([1-9][0-9]*) { read $1 }Javaスタイルのネストコメント
program :: ()
= (!"/*" !"*/" . { () } / comment)* !. { () }
comment :: ()
= "/*" commentElem* "*/" { () }
commentElem :: ()
= comment
/ !"*/" . { () }これがflexとかだと意外と難しい
Unquoter
- Quoterの中で、式を評価させる
tensor :: Exp
= ident '_' ident { $$1 !! $$2 }
ident :: String
= [a-z]+ { $1 }main :: IO ()
main = do
let x = [1, 2, 3]
i = 1
print [tensor|x_i|]いろいろ例 (1)
いろいろ例 (2)
- PeggyのPeggy自身による定義
- 実際にこれを用いてブートストラップしています。
さらなる例
レポジトリの example ディレクトリに色々あります
Future works
- Peggy自体のUnquoter化
- 型推論
- Unquoterにちゃんとした型をつける
- Unquoterが多分バグバグなので何とかする
- Unquoterを生成するパーザを生成するUnquoterを生成するパーザ
- 型がややこしすぎて頭がパンクしそうです(´>_<`)
- 他の言語のパーザ生成
- Java, C++, etc...
Resources
- Homepage
- Source Repository
- Hackage and Haddock documents
Try and Fork it!!
$ cabal update
$ cabal install peggy