システムソフトウェア講義の概要 計算機システムの復習:中央演算処理装置(CPU),プログラムの実行,主記憶装置,補助記憶装置

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 本日学ぶこと 文法  文字と文字列  無限集合  文法とそのクラス  オートマトン.
平成 19 年度卒業研究 PASCAL コンパイラについ て 福永研究室 山川 武志 畑中 陽介 佐藤 遼.
和田俊和 資料保存場所 /2/26 文法と言語 ー正規表現とオートマトンー 和田俊和 資料保存場所
プログラミング言語論 第10回(演習) 情報工学科 木村昌臣   篠埜 功.
文法と言語 ー字句解析とオートマトンlexー
プログラミング基礎I(再) 山元進.
コンパイラ 2011年10月17日
数値計算及び実習 第3回 プログラミングの基礎(1).
データ構造と アルゴリズム 理工学部 情報システム工学科 新田直也.
文法と言語 ー文脈自由文法とLR構文解析2ー
文法と言語 ー文脈自由文法とLL構文解析ー
プログラミング言語論 第4回 式の構文、式の評価
データ構造と アルゴリズム 知能情報学部 新田直也.
言語処理系(5) 金子敬一.
言語処理系(8) 金子敬一.
プログラミング論 II 電卓,逆ポーランド記法電卓
プログラミング演習Ⅰ 課題2 10進数と2進数 2回目.
コンパイラ 2012年10月15日
コンパイラ 2012年10月22日
コンパイラ 2011年10月24日
コンピュータの原理 1E17M053-9 奈良 皐佑 1E17M070-7 師尾 直希        1E17M078-6 渡邊 惇.
システムソフトウェア講義の概要 計算機システムの復習:中央演算処理装置(CPU),プログラムの実行,主記憶装置,補助記憶装置
システムソフトウェア講義の概要 計算機システムの復習:中央演算処理装置(CPU),プログラムの実行,主記憶装置,補助記憶装置
プログラミング言語入門 手続き型言語としてのJava
言語プロセッサ2007 平成19年9月26日(水) (Ver.2 平成19年10月3日変更)
言語プロセッサ 第7回目 平成27年11月16日.
プログラミング言語論 第3回 BNF記法について(演習付き)
正則言語 2011/6/27.
文法と言語 ー字句解析とオートマトンlexー
文法と言語 ー字句解析とオートマトンlexー
形式言語の理論 5. 文脈依存言語.
システムソフトウェア講義の概要 計算機システムの復習:中央演算処理装置(CPU),プログラムの実行,主記憶装置,補助記憶装置
プログラミング入門 電卓を作ろう・パートIV!!.
コンパイラ 第13回 上昇型構文解析(1) 38号館4階N-411 内線5459
東京工科大学 コンピュータサイエンス学部 亀田弘之
言語と文法 言語とは,ルールに従う記号列の無限集合である. 文法を与えることで言語が定義できる.
VBで始めるプログラミング こんにちは、世界。 /28 NARC.
文法と言語 ー文脈自由文法とLR構文解析2ー
平成20年10月5日(月) 東京工科大学 コンピュータサイエンス学部 亀田弘之
文法と言語 ー文脈自由文法とLR構文解析3ー
計算の理論 II 前期の復習 -有限オートマトン-
第5章 計算とプログラム 本章で説明すること ・計算の概観と記述法 ・代表的な計算モデル ・プログラムとプログラム言語.
先週の復習: CPU が働く仕組み コンピュータの構造 pp 制御装置+演算装置+レジスタ 制御装置がなければ電卓と同様
プログラムの基本構造と 構造化チャート(PAD)
東京工科大学 コンピュータサイエンス学部 亀田弘之
プログラミング言語論 第9回 情報工学科 木村昌臣 篠埜 功.
文法と言語 ー文脈自由文法とLL構文解析ー
コンパイラ 2011年10月20日
JAVAバイトコードにおける データ依存解析手法の提案と実装
計算の理論 I 決定性有限オートマトン(DFA) と 非決定性有限オートマトン(NFA)
東京工科大学 コンピュータサイエンス学部 亀田弘之
文法と言語 ー文脈自由文法とLR構文解析ー
計算の理論 I -数学的概念と記法- 火曜 12:50~14:20 大月 美佳 2004年4月20日.
情報基礎Ⅱ (第1回) 月曜4限 担当:北川 晃.
5.チューリングマシンと計算.
基本情報技術概論(第13回) 埼玉大学 理工学研究科 堀山 貴史
第5章 計算とプログラム 本章で説明すること ・計算の概観と記述法 ・代表的な計算モデル ・プログラムとプログラム言語 1.
東京工科大学 コンピュータサイエンス学部 亀田弘之
システムソフトウェア講義の概要 計算機システムの復習:中央演算処理装置(CPU),プログラムの実行,主記憶装置,補助記憶装置
計算の理論 I -数学的概念と記法- 月曜3校時 大月 美佳.
文法と言語 ー字句解析とオートマトンlexー
4.プッシュダウンオートマトンと 文脈自由文法の等価性
プログラミング基礎演習 第4回.
東京工科大学 コンピュータサイエンス学部 亀田弘之
コンパイラ 2012年10月11日
システムソフトウェア講義の概要 計算機システムの復習:中央演算処理装置(CPU),プログラムの実行,主記憶装置,補助記憶装置
文法と言語 ー文脈自由文法とLR構文解析2ー
4.2 再帰下降解析 (1)再帰下降解析とは ■再帰下降解析(Recursive Descent Parsing)
Presentation transcript:

システムソフトウェア講義の概要 計算機システムの復習:中央演算処理装置(CPU),プログラムの実行,主記憶装置,補助記憶装置 2019/7/6 システムソフトウェア講義の概要 計算機システムの復習:中央演算処理装置(CPU),プログラムの実行,主記憶装置,補助記憶装置 時分割処理:プロセス,スレッド,スケジューリング スレッド間の排他制御:フラグ,セマフォ,モニタ,デッドロック デバイス管理,HDDへのアクセス制御 記憶管理:メモリ割り当て,ページング,セグメンテーション 仮想記憶とファイルシステム 演習問題 プログラミングシステムの概要,文法とそのクラス,字句解析と正規文法 正規表現からの非決定性オートマトンの生成、決定性オートマトンへの変換 字句解析用オートマトン生成ソフトウエアの実際 構文解析と導出,文脈自由文法の構文解析法:LL構文解析 文脈自由文法の構文解析法:LR構文解析 コンパイラ-コンパイラと構文解析の実際 講義の総括と試験

高級言語

プログラムの作成から実行まで program example(output); var i, sum : integer; begin コンパイラ プログラムテキスト 実行プログラム アセンブラ リンカ program example(output); var i, sum : integer; begin sum := 0; for i :=1 to 100 do sum := sum +i; writeln(sum) end. 457f 464c 0101 0001 0000 0000 0000 0000 0002 0003 0001 0000 8080 0804 0034 0000 b43c 0000 0000 0000 0034 0020 0002 0028 0005 0004 0001 0000 0000 0000 8000 0804 8000 0804 ab00 0000 ab00 0000 0005 0000 1000 0000 0001 0000 b000 0000 3000 0805 3000 0805 0420 0000 0e00 0004 0006 0000 1000 0000 0000 0000 0000 0000 0000 0000 8959 89e3 40c8 e0c1 0102 83e0 f8e4 f8a3 053d 8908 3c0d 0534 8908 481d 0534 9b08 e3db d99b 002d 0530 3108 e8ed a9d0 0000 ... 0000 0000 000b 0000 0001 0000 0006 0000 8080 0804 0080 0000 aa80 0000 0000 0000 0000 0000 0010 0000 0000 0000 0011 0000 0001 0000 0003 0000 3000 0805 b000 0000 0420 0000 0000 0000 0000 0000 0004 0000 0000 0000 0017 0000 0008 0000 0003 0000 3420 0805 b420 0000 09e0 0004 0000 0000 0000 0000 0010 0000 0000 0000 0001 0000 0003 0000 0000 0000 0000 0000 b420 0000 001c 0000 0000 0000 0000 0000 0001 0000 0000 0000 main: .globl PASCALMAIN .type PASCALMAIN,@function PASCALMAIN: .globl program_init .type program_init,@function program_init: pushl %ebp movl %esp,%ebp subl $4,%esp call FPC_INITIALIZEUNITS movw $0,_SUM movw $1,_I .balign 4,144 .L7: movswl _SUM,%eax movswl _I,%edx addl %eax,%edx movw %dx,_SUM cmpw $100,_I jge .L6 incw _I jmp .L7

プログラムの例(Loop) program example(output); var i, sum : integer; begin 1から100までの和を求めるプログラム。 program example(output); var i, sum : integer; begin sum := 0; for i :=1 to 100 do        sum := sum +i; writeln(sum) end. 結果を格納する変数の初期化 この部分をi=1から i=100まで繰り返す 結果を画面に出力

フローチャートによる計算の記述 program example(output); var i, sum : integer; begin start program example(output); var i, sum : integer; begin sum := 0; for i :=1 to 100 do        sum := sum +i; writeln(sum) end. sum:=0; i:=1 yes i>100 no sum:=sum+i i:=i+1 writeln(sum) end

プログラムの例(if 文) 最大値を求めるプログラム。 program example(input,output); var i, x, max: integer; begin x := 0; max := 0; for i := 1 to 10 do read(x); if x > max then max := x end; writeln('maximum=',max) end. 結果を格納する変数の初期化 入力された数値をxに格納する 最大値の更新 結果を画面に出力

プログラムの例(数値計算) x12を表している

プログラムの例(数値計算)解説 の での接線の方程式 を求める 接線が 軸と交わる位置は, から              の     での接線の方程式     を求める 接線が  軸と交わる位置は, から この  を新たな   として,上の計算を繰り返すと,答えが求められる.

プログラミング言語処理系 高級言語の処理系 インタープリタ プログラムを逐次解釈実行する. コンパイラ プログラムを機械語に変換する. 2019/7/6 プログラミング言語処理系 高級言語の処理系 インタープリタ プログラムを逐次解釈実行する. コンパイラ プログラムを機械語に変換する.

コンパイラの概要

和田俊和 資料保存場所 http://vrl.sys.wakayama-u.ac.jp/SS/ 2019/7/6 文法と言語 ー正規表現とオートマトンー 和田俊和 資料保存場所 http://vrl.sys.wakayama-u.ac.jp/SS/

言語は,単なる記号の並び... ではない 言語はある規則を満足する記号列(文)の集合 ある言語に属する文は無数に存在する.(無限集合) 2019/7/6 言語は,単なる記号の並び... ではない 言語はある規則を満足する記号列(文)の集合 例: 日本語,英語,C言語,その他 「ex@p蛇Wx労z$壺-^ofD魔」 は上記言語に属さない 「while (A<100) A=A+1;」 はC言語に属する「文」 ある言語に属する文は無数に存在する.(無限集合) 文は形式的に定義可能→文法の必要性

なんで,こんなことを学ぶのか? 言語には,「文法」という規則がある. この規則を知らずに,文を書くことも読むこともできない. 2019/7/6 なんで,こんなことを学ぶのか? 言語には,「文法」という規則がある. この規則を知らずに,文を書くことも読むこともできない. 現実に,プログラミング言語の「正しい文法」を知らない学生は,許される文と許されない文の区別がつかない. プログラミング言語処理系では,実際に構文解析や字句解析が行われており,これを理解しなければ,情報の基礎を学んでいるとは言えない.

形式言語理論 文法は, の4つの組で表される. G={P,S,N,T} P:生成規則 S:出発記号 N:非終端記号の集合 T:終端記号の集合 2019/7/6 形式言語理論 文法は, P:生成規則   S:出発記号 N:非終端記号の集合 T:終端記号の集合 の4つの組で表される.  G={P,S,N,T}

文法の例1 文 S V O C A N the girl saw a dog running 生成規則 P={ 2019/7/6 文法の例1 文 S V O C A N the girl saw a dog running 生成規則 P={ 文→SV, 文→SVC, 文→SVO, 文→SVOC, A→“the”, A→ “a”, S→AN, S→N, O→AN, O→N, N→“girl”, N→“boy”, N→“dog”, V→“saw”,V→“runs”,V→“bites”,V→ “seems” C→“running”, C→“sick”} 出発記号 S=文 非終端記号 N= {A,S,N,V,O,C,} 終端記号 T= {“a”, “the”, “girl”, “boy”, “dog”, “saw”, “runs”, “bites”, “seems”, “running”, “sick”} 対応する言語の例, the girl saw a dog running the dog runs the dog bites a girl   the boy seems sick

導出,言語(ここは我慢して聞いて) を有限個の記号から成る空でない集合とする. 2019/7/6   を有限個の記号から成る空でない集合とする.   に含まれる記号        を並べた長さ1以上の記号列を  上の「語」と呼び,語全体を  で表す. また          とする.       の要素  に生成規則を何回か適用することによって が生成されることを,「導出」と呼び, と表す. で表される  の部分集合を文法            が生成する言語と呼ぶ.

但し,m,n∈(T∪N)*, t∈(T∪N)+, A ∈N 文法とそのクラス 2019/7/6 タイプ0文法 s→t 但し,s∈(T∪N)+, t∈(T∪N)* タイプ1文法(文脈依存文法) mAn→mtn 但し,m,n∈(T∪N)*, t∈(T∪N)+, A ∈N タイプ2文法(文脈自由文法) A→t 但し,t∈(T∪N)*,A ∈N

文脈自由文法の例 ( ) A × B - 5 + 4 ÷ C 算術式 生成規則 P={ 出発記号 S=算術式 2019/7/6 文脈自由文法の例 算術式 生成規則 P={     算術式 →項 加減演算子 算術式,     算術式→ 項 項 → 因子 乗除演算子 項 項 → 因子 因子→ 識別子 因子→ “(“ 算術式 “)” 識別子→変数 数値→”1”, 数値→”2”, ... ,数値→”9” 変数→”A”, 変数→”B”, 変数→”C” 加減演算子→“+”,  加減演算子→“-” 乗除演算子→“×”,  乗除演算子→“÷”} 出発記号 S=算術式 非終端記号 T= {算術式,項,因子,識別子,数値,変数,英数字,加減演算子,乗除演算子} 終端記号 T={“+”, “-”, “×”, “÷”, “0”,”1”,...,”9”, “A”,”B”,...,”Z”, “a”, “b”,...,”z”, “)”, “(“} 対応する言語の例    A×(B-5)+4÷C 項 加減演算子 算術式 因子 項 項 乗除演算子 因子 項 乗除演算子 算術式 識別子 識別子 算術式 因子 項 加減 演算子 項 変数 因子 数値 識別子 因子 識別子 識別子 変数 変数 数値 ( ) A × B - 5 + 4 ÷ C

(ちょっと脇道)何のための構文解析 →例:計算のため 2019/7/6 (ちょっと脇道)何のための構文解析 →例:計算のため 算術式 - 項 加減演算子 算術式 × ÷ 項 項 - 因子 4 C 乗除演算子 A 因子 項 B 5 乗除演算子 算術式 識別子 識別子 単一導出による分岐の無い枝を削除 分岐点にある非終端記号を葉の部分にある演算子で置き換える ↓ 構文木(演算子木) どうやって式の計算をすれば良いか?考えてみよう. 算術 式 因子 項 加減 演算子 項 変数 因子 数値 識別子 因子 識別子 識別子 変数 変数 数値 ( ) A × B - 5 - 4 ÷ C 導出木

より簡単な文脈自由文法 整数と実数を定義したい. 出発記号 S=数値 生成規則 P={ 数値→ 数字列,数値→数字列 “.” 数字列, 2019/7/6 より簡単な文脈自由文法 整数と実数を定義したい. 出発記号 S=数値 生成規則 P={      数値→ 数字列,数値→数字列 “.” 数字列,      数字列→数字列 数字, 数字列→数字,  数字→”0”, 数字→”1”, ... , 数字→”9”  } N=数値,数字列,数字 T={“0”,”1”, ... ,”9”, “.”}

但し,A,B∈N, b ∈ T, a∈(T∪{ε})* 2019/7/6 正規文法 タイプ3文法(正規文法) A→a あるいは B→bB 但し,A,B∈N, b ∈ T, a∈(T∪{ε})* 先の例の生成規則を書き換えてみる. P={      数値→ “0” 数値,数値→ “1” 数値,...      数値→”9” 数値, 数値→ “.”数値B, 数値→ε      数値B→ “0” 数値B,数値B→ “1” 数値B,...      数値B→”9” 数値B, 数値B→ε  } この生成規則だと,”.”が2回以上出てしまうことになる. どうすればよいか?

2019/7/6 字句解析と構文解析 プログラム言語処理系における構文解析では,「整数値」,「実数値」,「変数名」など正規文法で表現可能な部分は,プログラムの中から事前に種類ごとに抽出しておき,後続の構文解析の処理が軽くなるようにしている. この字句解析を行うのがオートマトンである. 字句解析 構文解析 最適化 コード生成

オートマトンを作るには,まず正規表現で字句を表現する 2019/7/6 オートマトンを作るには,まず正規表現で字句を表現する   上の正規表現とは次のようなものである. 空列  は正規表現である.     ならば,  は正規表現である.   と  が正規表現ならば   も正規表現である.   が正規表現ならば   も正規表現である. 尚,表現があいまいになる場合は括弧を用いる.

正規表現の意味 空列 は長さ0の記号列を表す. は記号 を表す. は もしくは を表す. は と がこの順番で繋がっていることを表す. 2019/7/6 正規表現の意味 空列  は長さ0の記号列を表す.  は記号  を表す.    は  もしくは  を表す.   は と がこの順番で繋がっていることを表す.   は の0回以上の繰り返しを表す. 括弧は,一まとまりの正規表現であることを示す.

正規表現による数値の表現 最初の数字は1~9までの数字であり, 引き続き0~9までの数字が0回以上繰り返される. 2019/7/6 正規表現による数値の表現 最初の数字は1~9までの数字であり, 引き続き0~9までの数字が0回以上繰り返される. これで終わりの場合もあるが, “.”が来て0~9までの数字が0回以上繰り返される場合もある.

正規表現からオートマトンへ オートマトンとは何か? 初期状態からスタートして,記号を受け取りながら状態遷移を起こし終了状態に遷移する. 2019/7/6 正規表現からオートマトンへ オートマトンとは何か?  初期状態からスタートして,記号を受け取りながら状態遷移を起こし終了状態に遷移する. 非決定性と決定性の2種類がある. 正規表現からは非決定性有限オートマトン(NFA)に変換できる. NFAから決定性の有限オートマトンに変換することができる b c i a f a a b d

2019/7/6 正規表現からオートマトンへ             i f i f i f i f i f

先ほどの数値の正規表現に対応するオートマトンを書きなさい 2019/7/6 先ほどの数値の正規表現に対応するオートマトンを書きなさい