コンパイラ 2011年10月17日 酒居敬一@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
和田俊和 資料保存場所 /2/26 文法と言語 ー正規表現とオートマトンー 和田俊和 資料保存場所
プログラミング言語論 第10回(演習) 情報工学科 木村昌臣   篠埜 功.
文法と言語 ー字句解析とオートマトンlexー
12.3,E,-15, 12.3,E5,+,=, >,<,…,
計算の理論 I 決定性有限オートマトン(DFA) と 非決定性有限オートマトン(NFA)
5.チューリングマシンと計算.
5.チューリングマシンと計算.
計算の理論 I ー DFAとNFAの等価性 ー 月曜3校時 大月 美佳.
授業展開#11 コンピュータは 何ができるか、できないか.
文法と言語 ー文脈自由文法とLR構文解析2ー
文法と言語 ー文脈自由文法とLL構文解析ー
プログラミング言語論 第4回 式の構文、式の評価
言語処理系(5) 金子敬一.
コンパイラ 2012年10月15日
コンパイラ 2012年10月22日
東京工科大学 コンピュータサイエンス学部 亀田弘之
コンパイラ 2011年10月24日
形式言語とオートマトン2013 ー有限オートマトンー 第5日目
システムソフトウェア講義の概要 計算機システムの復習:中央演算処理装置(CPU),プログラムの実行,主記憶装置,補助記憶装置
形式言語とオートマトン2008 ー有限オートマトンー
プログラミング言語論 第3回 BNF記法について(演習付き)
文法と言語 ー字句解析とオートマトンlexー
文法と言語 ー字句解析とオートマトンlexー
東京工科大学 コンピュータサイエンス学部 亀田弘之
計算の理論 I ー 正則表現(今度こそ) ー 月曜3校時 大月 美佳.
計算の理論 I ー 正則表現 ー 月曜3校時 大月 美佳.
形式言語とオートマトン Formal Languages and Automata 第4日目
プログラミング演習I 2003年5月7日(第4回) 木村巌.
オートマトンとチューリング機械.
言語と文法 言語とは,ルールに従う記号列の無限集合である. 文法を与えることで言語が定義できる.
コンパイラ 2011年10月6日
文法と言語 ー文脈自由文法とLR構文解析2ー
平成20年10月5日(月) 東京工科大学 コンピュータサイエンス学部 亀田弘之
計算の理論 II 前期の復習 -有限オートマトン-
計算の理論 I ε-動作を含むNFA 月曜3校時 大月 美佳.
東京工科大学 コンピュータサイエンス学部 亀田弘之
東京工科大学 コンピュータサイエンス学部 亀田弘之
2007年度 情報数理学.
プログラミング言語論 第9回 情報工学科 木村昌臣 篠埜 功.
文法と言語 ー文脈自由文法とLL構文解析ー
コンパイラ 2011年10月20日
コンパイラ 2012年10月4日
形式言語とオートマトン 中間試験解答例 2016年11月15実施 中島毅.
平成26年4月22日(火) 東京工科大学 コンピュータサイエンス学部 亀田弘之
計算の理論 I 決定性有限オートマトン(DFA) と 非決定性有限オートマトン(NFA)
東京工科大学 コンピュータサイエンス学部 亀田弘之
コンパイラ 2012年10月1日
文法と言語 ー文脈自由文法とLR構文解析ー
計算の理論 I 非決定性有限オートマトン(NFA)
計算の理論 I -数学的概念と記法- 火曜 12:50~14:20 大月 美佳 2004年4月20日.
5.チューリングマシンと計算.
計算の理論 I -数学的概念と記法- 月曜3校時 大月 美佳.
形式言語とオートマトン 第14回 プッシュダウンオートマトンと全体のまとめ
文法と言語 ー字句解析とオートマトンlexー
4.プッシュダウンオートマトンと 文脈自由文法の等価性
計算の理論 I NFAとDFAの等価性 火曜3校時 大月 美佳 平成16年5月18日 佐賀大学理工学部知能情報システム学科.
東京工科大学 コンピュータサイエンス学部 亀田弘之
システムソフトウェア講義の概要 計算機システムの復習:中央演算処理装置(CPU),プログラムの実行,主記憶装置,補助記憶装置
計算の理論 I ー 正則表現 ー 月曜3校時 大月 美佳.
コンパイラ 2012年10月11日
計算の理論 I ε-動作を含むNFA 火曜3校時 大月 美佳 平成16年5月25日 佐賀大学知能情報システム学科.
非決定性有限オートマトン 状態の有限集合 入力記号の有限集合 注意 動作関数 初期状態 受理状態の有限集合.
システムソフトウェア講義の概要 計算機システムの復習:中央演算処理装置(CPU),プログラムの実行,主記憶装置,補助記憶装置
形式言語とオートマトン Formal Languages and Automata 第5日目
文法と言語 ー文脈自由文法とLR構文解析2ー
計算の理論 I ー ε-動作を含むNFA ー 月曜3校時 大月 美佳.
情報処理Ⅱ 第2回 2004年10月12日(火).
計算の理論 I プッシュダウンオートマトン 月曜3校時 大月 美佳 平成15年7月7日 佐賀大学知能情報システム学科.
Presentation transcript:

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

字句解析(Lexical Analysis) 文字や文字の並びを、意味の有る字句として認識する。 自然言語では単語に分解することに相当する。 文法に基づき、予約語・識別子・演算子などに分解する。 識別子が関数名なのか変数名なのかは区別しない。 あくまで、単語に分解するだけである。 分解されたものは、文法上の構成単位である。 構文解析器の要求により動作する。 字句の要求に対する、字句への分解と字句の出力。 ソースプログラムからの文字の読み取り。 ファイルからのソースプログラムの読み込み。 読み込んだソースプログラムのバッファリング。

[条件式] 式 == != > < >= <= [加減演算子] [乗除演算子] + - * / 要素型 void [数字]と[英字]は非終端記号なので、 本来はそれらも終端記号に至るまでの 定義が必要。しかし、省略されている。 前回のBNFの例でも省略されている。 [返戻型] 数字 英字 [識別子] [整数] 数字 int [要素型]

バッカス記法(Backus Naur Form, BNF) <>で囲まれたものを構文要素と呼ぶ。 例では字句を定義しているが、字句解析済みの場合もある。 Javaのように名前に日本語文字集合が使える場合は、 こんなに単純に記述できない。ASCII文字集合なら簡単。 →の左側の要素は右側で構成される。 |は「または」を意味する。 <数字>→0|1|2|3|4|5|6|7|8|9 <英字>→a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z       |A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z <名前>→<英字>|<名前><英字>|<名前><数字>

有限オートマトン 名前などの字句は正規表現で定義できる。 つまり、正規言語で表せる。 入力の文字列が正規言語に含まれるかどうか? 名前などの字句は正規表現で定義できる。 つまり、正規言語で表せる。 入力の文字列が正規言語に含まれるかどうか? それを判定する仮想機械を有限状態オートマトンと呼んでいる。 開始状態から出発し、文字列を1文字ずつ読んでいきながら、 状態遷移関数によって状態を変化させていく。 最終的に最終状態に到達すれば、受理された、ということになる。

非決定性有限オートマトン(NFA) ある状態で、ある入力に対して、複数の遷移先がある。 正規表現からNFAを作る例。 入力によらない遷移もある。 遷移してもしなくてもいい。ε遷移 正規表現からNFAを作る例。 (3)a|b (1)ε空列記号 a b ε (2)アルファベットの集合Aの要素a (4)ab a b a ε a (5)a*

a(b|c)* の例 ε 4 3 2 1 a 1 0 a a 3 2 b これら3つを合成する。 ε 3 2 1 b c 0 a 4

決定性有限オートマトン(DFA) NFAではε遷移など、考えうるすべての状態遷移を 考慮して字句解析するのは効率が悪い。 NFAではε遷移など、考えうるすべての状態遷移を 考慮して字句解析するのは効率が悪い。 NFAから非決定的な遷移を取り除いたものがDFA。 ある状態から、入力によって遷移する先はたかだか一つ。 NFAからDFAへ変換するアルゴリズムが存在する。

NFAからDFAへの変換 同じ状態から遷移する状態をまとめた状態集合を作成。 εでたどれる先もまとめること。 状態の集合からの遷移を作成。ここでも、同じ状態 からの遷移先が複数ある場合は、遷移先をまとめる。 a ε 1 2 1,2 a ε 1 2 3 4 5 a b c 1,2 a 4 3,5 b c

a(b|c)*の、NFAからDFAへの変換例 ε 3 2 1 b c 0 a 4 1,2, 4 0 2,3,4 a b c

b a c b a 詳しくは、参考文献を見ること。 c 「コンパイラの構成と最適化」 中田育男著 オーム社 院の講義で使う教科書なので、 1,2, 4 0 2,3,4 a b c 0 1,2,3,4 a b c 詳しくは、参考文献を見ること。 「コンパイラの構成と最適化」 中田育男著 オーム社 院の講義で使う教科書なので、 図書館にある。

字句読み取りの例 簡単な浮動小数点数を定義する。 [浮動少数数点定数の構文規則] [浮動小数点定数の正規表現] 〈浮動小数点数〉→ ((ε|dd*).dd*|dd*.)(ε|e(ε|+|-|)dd*)|dd*e(ε|+|-)dd* 〈浮動小数点定数〉 → 〈小数点定数〉(ε|〈指数部〉)|〈数字列〉〈指数部〉 〈小数点定数〉 (ε|〈数字列〉).〈数字列〉|〈数字列〉. 〈指数部〉 e(ε|〈符号〉)〈数字列〉 〈符号〉 +|- 〈数字列〉 〈数字〉|〈数字列〉〈数字〉 〈数字〉 0|1|2|3|4|5|6|7|8|9

浮動小数点定数のNFA 1 f d ε 0 + . - 2 3 4 5 6 7 8 9 10 11 12 13 e

浮動小数点定数のDFA 0,2 12 3,5,f d 1,2, 6,10 3 13,f . e + - 8 4,5,f 9,f 11,12 7,8

状態数を最小にした浮動小数点定数のDFA 5 6 d 0 . e 4 2 1 3 - +