PEG覚え書き.

Slides:



Advertisements
Similar presentations
プログラミング言語論 プログラミング言語の構 文 水野嘉明. 目次 1. プログラミング言語の構文 2. BNF 3. 文脈自由文法 4. 構文図式 2.
Advertisements

プログラミング言語論 第3回 BNF 記法について(演習付き) 篠埜 功. 構文の記述 プログラミング言語の構文はどのように定式化できるか? 例1 : for ループの中に for ループが書ける。 for (i=0; i
システムソフトウェア 第3回:2007年10月17日(水)   . 2 本日学ぶこと 文法  文字と文字列  無限集合  文法とそのクラス  オートマトン.
和田俊和 資料保存場所 /2/26 文法と言語 ー正規表現とオートマトンー 和田俊和 資料保存場所
プログラミング言語論 第10回(演習) 情報工学科 木村昌臣   篠埜 功.
Problem J: いにしえの数式 問題作成・解説: 北村 解答作成協力: 八森.
文法と言語 ー字句解析とオートマトンlexー
計算の理論 I 文脈自由文法 月曜3校時 大月 美佳 平成15年6月30日 佐賀大学知能情報システム学科.
Problem by D. Mikurube Slides by Y. Izumi
コンパイラ 2011年10月17日
東京工科大学 コンピュータサイエンス学部 亀田弘之
ML 演習 第 4 回 新井淳也、中村宇佑、前田俊行 2011/05/10.
言語体系とコンピュータ 第6回.
言語処理系(6) 金子敬一.
文法と言語 ー文脈自由文法とLL構文解析ー
プログラミング言語論 第4回 式の構文、式の評価
計算の理論 II 文脈自由文法と プッシュダウンオートマトン
言語処理系(5) 金子敬一.
言語プロセッサ ー第8回目ー.
スタック長の 特徴付けによる 言語の非DCFL性 証明
コンパイラ 2012年10月15日
コンパイラ 2012年10月22日
東京工科大学 コンピュータサイエンス学部 亀田弘之
コンパイラ 2011年10月24日
東京工科大学 コンピュータサイエンス学部 亀田弘之
東京工科大学 コンピュータサイエンス学部 亀田弘之
システムソフトウェア講義の概要 計算機システムの復習:中央演算処理装置(CPU),プログラムの実行,主記憶装置,補助記憶装置
コンパイラ 第14回 上昇型構文解析(2) 38号館4階N-411 内線5459
プログラミング言語論 第3回 BNF記法について(演習付き)
東京工科大学 コンピュータサイエンス学部 亀田弘之
人工知能特論II 第2回 二宮 崇.
正則言語 2011/6/27.
文法と言語 ー字句解析とオートマトンlexー
文法と言語 ー字句解析とオートマトンlexー
形式言語の理論 5. 文脈依存言語.
東京工科大学 コンピュータサイエンス学部 亀田弘之
コンパイラ 第13回 上昇型構文解析(1) 38号館4階N-411 内線5459
東京工科大学 コンピュータサイエンス学部 亀田弘之
言語と文法 言語とは,ルールに従う記号列の無限集合である. 文法を与えることで言語が定義できる.
文法と言語 ー文脈自由文法とLR構文解析2ー
言語プロセッサ ー第9回目ー 構文解析(続き).
平成20年10月5日(月) 東京工科大学 コンピュータサイエンス学部 亀田弘之
文法と言語 ー文脈自由文法とLR構文解析3ー
計算の理論 I 文脈自由文法の標準形 月曜3校時 大月美佳.
かけ算 九九.
東京工科大学 コンピュータサイエンス学部 亀田弘之
プログラミング言語論 第9回 情報工学科 木村昌臣 篠埜 功.
文法と言語 ー文脈自由文法とLL構文解析ー
コンパイラ 2011年10月20日
東京工科大学 コンピュータサイエンス学部 亀田弘之
平成26年4月22日(火) 東京工科大学 コンピュータサイエンス学部 亀田弘之
文法と言語 ー文脈自由文法とLR構文解析ー
東京工科大学 コンピュータサイエンス学部 亀田弘之
計算の理論 I -数学的概念と記法- 月曜3校時 大月 美佳.
文法と言語 ー字句解析とオートマトンlexー
東京工科大学 コンピュータサイエンス学部 亀田 弘之
4.プッシュダウンオートマトンと 文脈自由文法の等価性
計算の理論 I 文脈自由文法 月曜3校時 大月美佳.
システムソフトウェア講義の概要 計算機システムの復習:中央演算処理装置(CPU),プログラムの実行,主記憶装置,補助記憶装置
東京工科大学 コンピュータサイエンス学部 亀田弘之
東京工科大学 コンピュータサイエンス学部 亀田弘之
コンパイラ 2012年10月11日
言語プロセッサ ー第9回目ー 構文解析(続き).
言語プロセッサ ー第7回目ー 構文解析(続き).
東京工科大学 コンピュータサイエンス学部 亀田 弘之
東京工科大学 コンピュータサイエンス学部 亀田 弘之
システムソフトウェア講義の概要 計算機システムの復習:中央演算処理装置(CPU),プログラムの実行,主記憶装置,補助記憶装置
文法と言語 ー文脈自由文法とLR構文解析2ー
東京工科大学 コンピュータサイエンス学部 亀田弘之
4.2 再帰下降解析 (1)再帰下降解析とは ■再帰下降解析(Recursive Descent Parsing)
Presentation transcript:

PEG覚え書き

PEG? Parsing Expression Grammerの略 Contest Free Grammerと同等レベルの表現能力 曖昧さを許さない文法 Parsing Expression Grammars:A Recognition-Based Syntactic Foundation by Bryan Ford Page 2

PEGの活用 PEGは正規表現の強力版 Perl6にもPEGが GaucheにもPEGが Haskell, Pappy, Frisby OCaml, aurochs Page 3

PEG定義 「非終端記号 ← parsing expression」の集合(ただし、非終端記号はユニーク) ε(空文字) 終端記号 非終端記号 e1 e2(並び) e1 / e2(選択) e*(0個以上) !e (入力を消費しない存在確認) オプショナル e? = e/ ε e+ = e e* &e = ! !e Page 4

例:足し算とかけ算 PEG CFG V ← (0/1/2/3/4/5/6/7/8/9)+/”(“ E “)” %left “+” exp : exp “+” exp | exp “*” exp PEG V ← (0/1/2/3/4/5/6/7/8/9)+/”(“ E “)” P ← V (“*” V)* S ← P (“+” P)* E ← S Page 5