koie blog : PEGと構文解析に関するアレコレの勉強会 Vol.1

http://connpass.com/event/16630/
2015-08-08 13:30〜18:00
ドワンゴセミナールーム (歌舞伎座タワー14F)
#peg_study: http://togetter.com/li/858028

またしても方向間違えて東銀座→銀座まで歩いてしまった。余裕もって家を出たのでそれでも13時に着いた。早すぎたけど席が自由に選べるメリット。電源タップは各席に1個(2口)ずつあるっぽい。

Introduction to PEG / @kmizu

[2015-08-08 14:04]

http://www.slideshare.net/kmizushima/introduction-to-peg

PEG: ピーイージー
構文解析友の会はいまつくった。
Cargo cult parsing: 適当につくった、それっぽく動くパーサのこと。
自然言語の場合は解釈が一意にならない可能性。
非自然言語は木構造が一意に。
構文解析いろいろ:
- CYK O(n^3) 自然言語向け
- SLR,LALR(k) O(n)
- LL(k) O(n)
- LL(*) O(n)
- GLR O(n^3) 主に自然言語向け
- GLL O(n^3) 主に非自然言語向け
- PEG O(n^k)
- Packrt parsing O(n)
つくりかた: 手書き・パーザジェネレータ・パーザコンビネータ
YACC:
- 空白の有無で意味が変わる文法は苦手。
- トークンが再帰的な構造を含むものは苦手(文字列に式をうめこむとかヒアドキュメントとか)。
- rubyのパーサはとってもきたない。まともに設計したとはおもえない。
JavaCC(LL(k)+α):
- yaccと弱点とおなじ。
LALR/LLは字句解析がある。普通は正規表現をつかう(なぜ正規表現をつかうかは丁度いいから、近年はあわなくなってきている)。
そこでPEG。
PEGは文法の表記法の側面もある(BNF)がHowまで規定しているのでアルゴリズムでもある。
PEGのe1/e2はBNFのe1|e2とはちがう。 e1/e2 ≠ e2/e1 順序に意味がある。
&e and-predicate マッチしたら成功。入力消費しない。
!e not-predicate マッチしなかったら成功。入力消費しない。 &e = !!(e)
and-pred,not-predがあることで無限に先読みできる→字句解析が不要→柔軟な文法
曖昧性がないのでconflictがない:
- if_stmt ← IF LP epr RP tmt (ELSE stmt)? shift-reduce conflictのよくある例 dangling else
PEG: 順序をいれかえると意味がかわる。if..then.. / if..then..else.. の順に書くと後ろが使われない問題。
Packrat Parsing
- PEGにbacktrackとメモ化(memoize;メモイズ;メモライズではない)
- 入力文字列の長さに比例した記憶領域が必要で大規模ファイルには向かない
- 実行効率がいまいち(ほとんどのメモは無駄に)
会場:clangのパーサについて質問 packratつかってる? つかってないとおもう。ソースコードが大きくなるとメモリ使用量が増えるのは別の問題では?
Treetopおすすめ

[2015-08-08 14:49]

Q: プリミティブは?
A: e1 e1, e1/e2, ch の3つ。
Q: PEGのプリミティブとのちがいは順序があるところ
A: 正規表現にルールと再帰ルールをつけるとPEGになるかも。(フォーマルにはPEGの方が強いので議論するまでもない)
Q: yaccとPEGとどっちが簡単?
A: どっちで書いても同じくらいでは? コンパイラを書くことを考えると文法の柔軟性はあまり必要ないし。
Q: CFGのパーザコンビネータはつくれる?
A: 複数のツリーを返すような関数にしたらいけるかも。
Q: yaccをバックエンドにするようなパーサコンビネータはどうか?
A: かんがえたことなかったけどおもしろいかも
Q: packrat parserとPEGどっちが先?
A: packrat parserを再発見したのが2002年。文法としてPEGにまとめたのが2004年。
Q: 文法のクラスがあきらかになるとなにがうれしい?
A: 正規表現で書けないことがわかっているなら「パーサ書けよ」って言えること。

[2015-08-08 15:01]

休憩

[2015-08-08 15:11]

パーザコンビネータをつくろう / もみあげ @pocketberserker

https://github.com/pocketberserker/PEGStudy
http://pocketberserker.github.io/PEGStudy/#/
smlsharpしってるひと挙手 → 30人くらい?
パーサコンビネータつかったことあるひと → 30?
パーサコンビネータつくったことあるひと → 5?
haskell maybeわからないひと → 0
Choiceって型きらいなんですが。
eitherわからないひと → 0
新しい言語を覚えるのにパーサコンビネータつくるのが習慣になっている。

[2015-08-08 15:40]

Q: manyが強欲マッチになっているがよいか?
A: PEG的にはよい。
Q: つかった例はどこに?
A: 今日の3時からつくったので、ない。JSONパーサつくろうとおもってたけど。あしたくらいにはつくる。
Q: どのくらいかかった
A: 資料+眠い状態で今日の3時→7時(4時間)くらいでできた(途中記憶はとんでるけど)。テスト作成には時間がかかるかも。

[2015-08-08 15:44]

休憩

[2015-08-08 16:02]

構文解析にまつわる小話たち / keen @blackenedgold

http://keens.github.io/slide/koubunkaisekiarekore/
文法はただの外側、ほしいのはAST。料理は食べたらおんなじ。
S式推し!
構文を考えるより先にASTを考えろ。
+と&&は二項演算子だけど、=はスペシャルフォーム (lispだと) 左辺値の特別扱いのため。
正規表現は部品化がむつかしい。
lexerは正規表現に向いている。lexerは末端部品なのでつかって問題にならない。
文法と言語は別。
演算子優先度解析 Emacs SMIE タブインデントの解析につかったり。
LRは左再帰でも表を引くだけなので問題ない。LLは困る。
言語仕様で先送りすることで言語クラスがかわったりする。
sedの s|||(区切り文字) やmarkdownのテーブル(カラム数)は文脈非自由文法。
パーサジェネレータはつかうのめんどくさい。
パーサが複雑な文法に対応できても人間が対応できない。
Cはセミコロンで文が終わるのでエラー回復しやすい。
にゅうちえんざんしはシンタックスのプラグイン
Coqしっているひと → 20人?
Coqは謎のテクで文法を拡張できる。どうやってるかわからん。(あとの発表でMix-fix operatorsだとのこと)
ASTのテストむつかしい → 根性 or 木のクエリ言語をつかう。
先読みと副作用

[2015-08-08 16:37]

メモ化は副作用があるとつかえない

[2015-08-08 16:38]

休憩

[2015-08-08 16:59]

構文拡張と構文解析 / @phenan

アイコンは妹作。
ビジュアル構文解析(超大作)は後輩に説明するめにつくった。みてね。
- http://www.slideshare.net/ichikaz3/ss-11400787
構文拡張→構文規則を変更新しい言語をつくるわけではない。
具象構文: 見た目。
抽象構文: 意味論とむすびつく本質的な構文。
S式は具象構文が括弧だけとみなせる。
問題: 具象構文を拡張→抽象構文も拡張されちゃう。
解決方法: (1)構文木の書き換え (2)ホスト言語で扱う。
構文木の書き換え: メタプログラムで書き換える。DSLの構文木に意味論がつかない問題。
ホスト言語であつかう: 単なる関数呼出にしちゃう。構文木は関数の引数に。部分式しかつかえない。
拡張できるには構文規則の曖昧性は必要 → 意味解析で構文木を選ぶ。
あいまい性があると指数関数的に選択肢が増える → 構文解析と意味解析を同時に実行して選択肢が増えないようにした。
型と非終端記号は似てる!
ProteaJ: Java + Protean operators
Mix-fix operators: Coqはこれつかってる

[2015-08-08 17:28]

Q: 構文拡張とIDEの相性
A: 内部DSLではきかない。外部DSLはツールがあるみたい。
Q: 構文木が唯一に決まるならそれがユーザ期待した構文というのは自明じゃないような?
A: コンパイラの入力はユーザはコンパイルが通るように書いてるはずなので、そんなに悪くないとおもっている。
Q: 解析のオーダーは?
A: 文脈依存なのでPEGじゃない。Packrat parserで書けているので線形だといいなぁ。
Q: Javaは型が強力じゃないけど、型が強力になるとどうなる?
A: ホスト言語の型が強力になると表現力が増すはず。計算時間がどうなるかはわからない。
Q: 構文を拡張する方法はこれから普及するか? (アスペクト指向はそうではなさそうだけど)
A: セマンティックスだけを提供しておいて、ユーザがシンタックスを定義できるようになるなるといいなぁ、という野望。ちなみにアスペクト指向は大学研究室でやってた人がいた。。。
Q: 分割コンパイルは
A: DSLモジュールをインポートするとつかえるようになる。演算子の優先度はインポート順序による。
これまでは構文解析で型チェックするものはなかったはず。