コンパイラ 2011年10月24日 酒居敬一@A468(sakai.keiichi@kochi-tech.ac.jp) http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/COMP/2011/index.html.

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ー
コンパイラ 2012年10月25日
Problem by D. Mikurube Slides by Y. Izumi
言語処理系(7) 金子敬一.
コンパイラ 2011年10月17日
言語体系とコンピュータ 第6回.
言語処理系(6) 金子敬一.
文法と言語 ー文脈自由文法とLR構文解析2ー
文法と言語 ー文脈自由文法とLL構文解析ー
計算の理論 II 文脈自由文法と プッシュダウンオートマトン
アルゴリズムとデータ構造 2011年6月13日
言語処理系(5) 金子敬一.
言語プロセッサ ー第8回目ー.
コンパイラ 2012年10月15日
コンパイラ 2012年10月22日
言語プロセッサ2013 ー 第7回目 ー Tokyo University of Technology
コンパイラ(9) 情報工学科5年 担当 河田 進.
東京工科大学 コンピュータサイエンス学部 亀田弘之
コンパイラ 2011年10月27日
システムソフトウェア講義の概要 計算機システムの復習:中央演算処理装置(CPU),プログラムの実行,主記憶装置,補助記憶装置
コンパイラ 第14回 上昇型構文解析(2) 38号館4階N-411 内線5459
東京工科大学 コンピュータサイエンス学部 亀田弘之
言語プロセッサ 第7回目 平成27年11月16日.
プログラミング言語論 第3回 BNF記法について(演習付き)
正則言語 2011/6/27.
文法と言語 ー字句解析とオートマトンlexー
形式言語の理論 5. 文脈依存言語.
コンパイラ 第13回 上昇型構文解析(1) 38号館4階N-411 内線5459
言語プロセッサ2012 ー 第6回目 ー Tokyo University of technology
言語と文法 言語とは,ルールに従う記号列の無限集合である. 文法を与えることで言語が定義できる.
文法と言語 ー文脈自由文法とLR構文解析2ー
言語プロセッサ ー第9回目ー 構文解析(続き).
平成20年10月5日(月) 東京工科大学 コンピュータサイエンス学部 亀田弘之
言語プロセッサ2016 ー 第5回目(10月31日) ー Tokyo University of Technology
文法と言語 ー文脈自由文法とLR構文解析3ー
計算の理論 II 前期の復習 -有限オートマトン-
東京工科大学 コンピュータサイエンス学部 亀田弘之
東京工科大学 コンピュータサイエンス学部 亀田弘之
プログラミング言語論 第9回 情報工学科 木村昌臣 篠埜 功.
文法と言語 ー文脈自由文法とLL構文解析ー
コンパイラ 2011年10月20日
プログラミング基礎a 第6回 C言語によるプログラミング入門 配列と文字列(その2)
文法と言語 ー文脈自由文法とLR構文解析ー
言語プロセッサ2015 ー 第5回目(11月2日) ー Tokyo University of Technology
アルゴリズムとデータ構造 2012年6月11日
アルゴリズムとデータ構造1 2009年6月15日
計算の理論 I -数学的概念と記法- 月曜3校時 大月 美佳.
文法と言語 ー字句解析とオートマトンlexー
東京工科大学 コンピュータサイエンス学部 亀田 弘之
4.プッシュダウンオートマトンと 文脈自由文法の等価性
情報処理Ⅱ 第7回 2004年11月16日(火).
システムソフトウェア講義の概要 計算機システムの復習:中央演算処理装置(CPU),プログラムの実行,主記憶装置,補助記憶装置
コンパイラ 2012年10月11日
アルゴリズムとデータ構造 2010年6月17日
言語プロセッサ ー第9回目ー 構文解析(続き).
言語プロセッサ ー第7回目ー 構文解析(続き).
東京工科大学 コンピュータサイエンス学部 亀田 弘之
東京工科大学 コンピュータサイエンス学部 亀田 弘之
システムソフトウェア講義の概要 計算機システムの復習:中央演算処理装置(CPU),プログラムの実行,主記憶装置,補助記憶装置
文法と言語 ー文脈自由文法とLR構文解析2ー
情報処理Ⅱ 2005年11月25日(金).
情報処理Ⅱ 小テスト 2005年2月1日(火).
オブジェクト指向言語論 第六回 知能情報学部 新田直也.
4.2 再帰下降解析 (1)再帰下降解析とは ■再帰下降解析(Recursive Descent Parsing)
Presentation transcript:

コンパイラ 2011年10月24日 酒居敬一@A468(sakai.keiichi@kochi-tech.ac.jp) http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/COMP/2011/index.html

構文解析 前回の内容 今回の内容 下向き構文解析法 LL(k)構文解析法。 LL(1)構文解析法 左再帰性の問題と、その除去 バックトラックの問題 今回の内容 LL(k)構文解析法。 動機付けとして、下向き構文解析におけるバックトラックをなくしたい。 LLは Left to right scan, Left most derivation より。 k個の字句を先読みすることでバックトラックなし構文解析を実現する。 LL(1)構文解析法 字句をひとつだけ先読みすることで、決定的に構文解析可能。

LL構文解析 下向き構文解析では、解析木を根から生成する。 根にある非終端記号(=字句の列の先頭)がどの生成規則 に適合するか、それが初めにわかればバックトラック不要。       の例では、αとβのどちらかを一意に決めたい、ということ。 字句をひとつ読んだとき、それが生成規則を決める 手がかりであるかどうかがわかればよい??? 入力記号aがαの先頭記号になりうるか? そしてバックトラック不要にするために、 βの先頭記号ではないこと。 入力記号aがAの直後の終端記号になりうるか? 入力記号aがαの先頭記号でなければ、 の場合。 そこで、First集合、Follow集合というものを考えることにする。 このようなaを含む集合をDirector集合という。

First集合 αの先頭記号になりうる入力記号をFirst(α)とする。 ただし、εに展開してもいいかどうか一意に決定できないので、 そういうときは後述のFollow集合とともに決定する。 入力記号をひとつ読んだ場合を議論しているのに、入力記号を一切読まなくてもいいと生成規則が言ってる場合には議論の前提がずれてることになる。もちろんこれ単独で答えが出ないということ。

First集合を求めるアルゴリズム α,βを記号列、A,Yを非終端記号、aを終端記号とする。 αが非終端記号Aのとき:Aを左辺に持つすべての 生成規則A→βについてFirst(β)を求め、その要素を First(α)に加える。 αが長さ2以上の記号列(α=Yβ)のとき

Follow集合 という生成規則からはAをεに展開してもよい。 そこでFollow(A)という集合を考える。         という生成規則からはAをεに展開してもよい。 このときは、        でもある。しかし、εは字句ではない。 入力からは、前ページのようには、一意に決定できない。 そこでFollow(A)という集合を考える。 これはAの直後の終端記号に成りうる記号の集合。        ならばαに展開できた。ところが、aがFirst集合に 含まれず        である場合でも         であれば、 ここはαに展開できる。 つまり       という生成規則に一意に決定できるということ。

Follow集合を求めるアルゴリズム Sを開始記号、α,βを記号列、A,Bを非終端記号、 aを終端記号、$を入力の最後を表す特殊な記号とする。 Sが開始記号のとき:Follow(S)に$を加える。 A→αBβなる生成規則のとき: Follow(B)にFirst(β)ー{ε}を加える。 A→αBβなる生成規則において、 First(β)にεが含まれているとき: Follow(B)にFollow(A)を加える。

Director集合 First集合とFollow集合を合わせて、Aをαに展開すべき かどうかを決定するための集合をDirector集合として 定義する。

LL(1)文法 LL(1)文法の定義 先頭の字句をひとつ読めば展開すべき生成規則が 一意に決まるということを意味している。 そのような文法をLL(1)文法といっている。

再帰的下向き構文解析1 LL(1)文法であれば、バックトラックしない 再帰的下向き構文解析器が作成できる。 しかしながら、この文法G1では、左再帰性をもつため、 このままでは再帰的下向き構文解析ができない。 【文法G1】 (1)式 → 式+項 (2)式 項 (3)項 項*因子 (4)項 因子 (5)因子 (式) (6)因子 i

再帰的下向き構文解析2 左再帰性を除去した文法G2 正規右辺文法もしくは拡張BNFによる文法G3 【文法G2】 (1)式 → 項 式端 項 式端 (2)式端 +項 式端|ε (3)項 因子 項端 (4)項端 *因子 項端|ε (5)因子 (式)|i 【文法G3】 (1)式 → 項 {+項} (2)項 因子 {*因子} (3)因子 (式)|i

形式言語による言語と文法の定義1 アルファベット 文字・記号 語・文字列・記号列 空語・空文字列・空記号列 語彙 空でない有限集合。 ABC…Zのような英語のアルファベットと混同しないように。 文字・記号 アルファベットの要素。 語・文字列・記号列 アルファベットの要素を有限個並べたもの。 空語・空文字列・空記号列 アルファベットの要素をひとつも含まないもの。εで表す。 語彙 生成規則に現れる記号(全部)の集合。

形式言語による言語と文法の定義2 四つ組G=(N,T,P,S)を文法という。 文法G上の言語L(G)とは、 N,T,Pは空ではない有限集合。 N,T,P の要素はそれぞれ非終端記号,終端記号,生成規則。 NとTに共通部分はない。 Pの要素(生成規則)は「左辺→右辺」の形をとる。 左辺と右辺は(N∪T)*の要素とする。 開始記号SはS∈Nとする。 文法G上の言語L(G)とは、 開始記号Sから出発し、生成規則(Pの要素)を有限回適用して 得られた、終端記号列(文)の集合。

形式言語による言語と文法の定義3 句構造文法 タイプ0(制限なし) タイプ1(文脈依存文法) タイプ2(文脈自由文法) タイプ3(正規文法) 1950年代後半に言語学者チョムスキーによって考案された。 タイプ0(制限なし) タイプ1(文脈依存文法) アセンブリ言語はこのタイプ。 タイプ2(文脈自由文法) 生成規則の左辺がひとつの非終端記号だけからなる。 C言語やJavaなど高級言語はたいていこのタイプ。 タイプ3(正規文法)

予習・復習 C言語では次のような宣言もしくは定義ができる。 これらの文に対応する生成規則を考えてみよう! 複雑な宣言や定義をそのまま書くと複雑で読みにくいので、 通常はtypedefを使って段階的に宣言や定義する。 これらの文に対応する生成規則を考えてみよう! int *f(); /* fはintへのポインタを返す関数 */ int (*f)(); /* fはintを返す関数へのポインタ */ char **argv; /* charへのポインタのポインタ */ int (*daytab)[13]; /* daytabはintを要素とする要素数13の配列へのポインタ */ int *daytab[13]; /* daytabはintへのポインタを要素とする要素数13の配列 */ char (*(*x())[])(); /* xはcharを返す関数へのポインタの配列へのポインタを返す関数 */ char (*(*x[3])())[5];/* xはcharを要素とする要素数5の配列へのポインタを返す関数 へのポインタを要素とする要素数3の配列 */ 出典: "プログラミング言語C 第2版", 共立出版, 149ページ, 2001年.