言語処理系（３） 金子敬一.

Presentation on theme: "言語処理系（３） 金子敬一."— Presentation transcript:

1 言語処理系（３） 金子敬一

2 ２ プログラミング言語 ２．１ 高水準プログラミング言語 ２．２ プログラミング言語の定義 ２．３ 言語の字句構造および構文構造
２　プログラミング言語 ２．１　高水準プログラミング言語 ２．２　プログラミング言語の定義 ２．３　言語の字句構造および構文構造 ２．４　データ要素 ２．５　データ構造 ２．６　演算子 ２．７　代入 ２．８　文 ２．９　プログラム単位 ２．１０　データ環境 ２．１１　引数の転送 ２．１２　記憶域管理

3 ２．７ 代入 代入演算子 A := B A = B A ← B LET A = B MOVE B TO A PASCAL, ALGOL
２．７　代入 代入演算子 A := B A = B A ← B LET A = B MOVE B TO A PASCAL, ALGOL C, FORTRAN APL BASIC COBOL 以下では，:=を代入演算子，=を等号とする．

4 ２．７ 代入 l 値と r 値 A := B 名前Aの位置へ名前Bの値を代入せよ 名前は代入演算子の左辺と右辺では意味が異なる． l 値
２．７　代入 l 値と r 値 A := B 名前Aの位置へ名前Bの値を代入せよ 名前は代入演算子の左辺と右辺では意味が異なる． l 値 r 値

5 ２．７ 代入 l 値と r 値 式の r 値 ⇒ その式の示す値 一方，式は常に l 値を持つとは限らない すべての名前
２．７　代入 l 値と r 値 式の r 値　⇒　その式の示す値 一方，式は常に l 値を持つとは限らない すべての名前 Aが配列名⇒A[I]の l 値は，配列Aの第I番目の要素の位置， r 値はA[I]に格納している値 定数は， r 値のみ持ち， l 値を持たない ポインタPの r 値は，Pの指す位置であり， l 値はPの値を格納している位置

6 ２．７　代入 l 値と r 値 ポインタPの r 値は，Pの指す位置であり， l 値はPの値を格納している位置 P := P + 1 P P

7 ２．７ 代入 代入の実現（A := Bの１つの実現法） Bの r 値を計算し，レジスタrに入れるコードを生成
２．７　代入 代入の実現（A　:=　Bの１つの実現法） Bの r 値を計算し，レジスタrに入れるコードを生成 AとBの型が不一致 ⇒ Bの r 値をAに適合するように型変換 必要があればAの l 値を計算するコードを生成 レジスタrの内容をAの l 値へ格納するためのコードを生成

8 ２．７ 代入 代入の実現例（X[I] := Y[J]） １語４バイト XおよびY： 固定位置，整数型 添え字は0から始まる
２．７　代入 代入の実現例（X[I]　:=　Y[J]） １語４バイト XおよびY：　固定位置，整数型 添え字は0から始まる 整数型の各要素は１語を占める

9 ２．７ 代入 代入の実現例（X[I] := Y[J]） Bの r 値を計算し，レジスタrに入れるコードを生成
２．７　代入 代入の実現例（X[I]　:=　Y[J]） Bの r 値を計算し，レジスタrに入れるコードを生成 LOAD J, r2 /* Jをr2にロードする */ MULT #4, r2 /* r2を4倍する */ LOAD Y(r2), r1

10 ２．７ 代入 代入の実現例（X[I] := Y[J]） AとBの型が不一致 ⇒ Bの r 値をAに適合するように型変換
２．７　代入 代入の実現例（X[I]　:=　Y[J]） AとBの型が不一致 ⇒ Bの r 値をAに適合するように型変換 X[I]とY[I]の型は一致⇒コード生成不要

11 ２．７ 代入 代入の実現例（X[I] := Y[J]） 必要があればAの l 値を計算するコードを生成
２．７　代入 代入の実現例（X[I]　:=　Y[J]） 必要があればAの l 値を計算するコードを生成 LOAD I, r2 /* Iをr2にロードする */ MULT #4, r2 /* r2を4倍する */

12 ２．７ 代入 代入の実現例（X[I] := Y[J]） レジスタrの内容をAの l 値へ格納するためのコードを生成
２．７　代入 代入の実現例（X[I]　:=　Y[J]） レジスタrの内容をAの l 値へ格納するためのコードを生成 STORE r1, X(r2) /* r1をX(r2)にロードする */

13 ２．７ 代入 代入の実現例（X[I] := Y[J]） LOAD J, r2 /* Jをr2にロードする */
２．７　代入 代入の実現例（X[I]　:=　Y[J]） LOAD J, r /* Jをr2にロードする */ MULT #4, r2 /* r2を4倍する */ LOAD Y(r2), r1 /* Y(r2)をr1にロードする */ LOAD I, r /* Iをr2にロードする */ STORE r1, X(r2) /* r1をX(r2)にロードする */

14 ２．７ 代入 演算子としての代入 代入演算子を２項中置演算子として扱う言語（Cなど） Cにおいて
２．７　代入 演算子としての代入 代入演算子を２項中置演算子として扱う言語（Cなど） Cにおいて A = (B = C + D) + (E = F + G) と書かれた式は， B = C + D, E = F + G, A = B + E と解釈可能

15 ２．７ 代入 より一般的な代入 A := B の両辺が単純でない場合
２．７　代入 より一般的な代入 A := B の両辺が単純でない場合 PL/IにおいてAを整数配列とするとA := 0と書かれた式は，配列Aの全要素を0に初期化する

16 練習問題　２．１ r 値および l 値を持つものはどれか A[I+1] *A &A &(*A) *(&A) *(&(&A)) r 値 l 値

17 ２．８ 文 単純文と複合文 単純文：その中に文を含まない文 複合文：1つ以上の文を含む文 if 条件 then 文
２．８　文 単純文と複合文 単純文：その中に文を含まない文 複合文：1つ以上の文を含む文 if 条件 then 文 if 条件 then 文 else　文 begin 文; 文; ...; 文 end while 条件 do 文 for 識別子 := 初期値 to 終値 do　文 Pascalの 複合文

18 ２．８ 文 文の型 計算文：代入文など 順序制御文：goto文，break文，call文，return文など 構造文：END文など
２．８　文 文の型 計算文：代入文など 順序制御文：goto文，break文，call文，return文など 構造文：END文など 宣言文：コード生成なし．記号表への登録 入出力文：入出力装置を制御．書式を使用

19 ２．９ プログラム単位 FORTRAN １つの主プログラム＋０個以上の副プログラム 副プログラム：サブルーチン，関数，ブロックデータ
２．９　プログラム単位 FORTRAN １つの主プログラム＋０個以上の副プログラム 副プログラム：サブルーチン，関数，ブロックデータ 分割コンパイル可能 主プログラム，サブルーチン，関数：宣言列＋実行文列 大域データ：COMMON文で参照；その他のデータは局所的となる

20 ２．９ プログラム単位 ALGOL ブロック構造化言語 名前の有効範囲 ・ブロックB中で宣言された名前は，ブロックBで のみ有効
２．９　プログラム単位 ALGOL ブロック構造化言語 名前の有効範囲 ・ブロックB中で宣言された名前は，ブロックBで 　のみ有効 ・ブロックB’がブロックB中に入れ子になっている 　ならば，Bで有効な名前は，B’でそれに対応す 　る識別子が再宣言されていなければ，B’中でも 　有効

21 ２．９ プログラム単位 begin real X, Y; real Y; real X; ... end ... X X Y Y Y
２．９　プログラム単位 begin real X, Y; real Y; real X; 　　　　　　　　　　　... end ... X X Y Y Y ブロック３ ブロック１ ブロック２ ブロック４

22 ２．９ プログラム単位 PL/I FORTRANとALGOLの折衷 プログラムは外部手続きの集合 そのうちの1つが主プログラム
２．９　プログラム単位 PL/I FORTRANとALGOLの折衷 プログラムは外部手続きの集合 そのうちの1つが主プログラム 分割コンパイル可能 ブロックや内部手続きを入れ子にできる

23 ちょっと休憩 （雑談）

24 ラテン語編 類似の言葉 スペイン語 フランス語 英語 botella bouteille bottle claro clair clear
estudiar etudier study fruta fruit importante important música musique music moderno moderne modern papel papier paper persona personne person

25 ラテン語編 日本語とスペイン語 外来語 manto （マント） velludo （びろうど） capa （合羽） carta （カルタ）
要注意 No sé.　（野瀬） Da me.　（駄目） Y caga?　（いかが？）

26 休憩おわり

27 ２．１０　データ環境 環境 識別子と名前との対応 文の環境 ブロックの環境 副ブロックの環境

28 ２．１０ データ環境 識別子と名前の結合 識別子→名前 名前→位置 静的な結合: FORTRAN, ALGOL, PL/I
２．１０　データ環境 識別子と名前の結合 識別子→名前 名前→位置 静的な結合: FORTRAN, ALGOL, PL/I 動的な結合: LISP, APL, SNOBOL

29 ２．１０ データ環境 有効範囲規則 有効範囲：その名前を使うことのできる，プログラムの部分のこと ALGOLなど：至近規則
２．１０　データ環境 有効範囲規則 有効範囲：その名前を使うことのできる，プログラムの部分のこと ALGOLなど：至近規則 LISPなど：他の規則

30 ２．１０ データ環境 有効範囲規則 LISPなど：他の規則 値をスタックに退避して，回復する．
２．１０　データ環境 有効範囲規則 LISPなど：他の規則 値をスタックに退避して，回復する． (defun f (x) (setq x (+ x 1)) (g) (print x)) (defun g () (print x) (setq x 1)) (defun h () (setq x 3) (f 1) (print x) (g) (print x)) 2 1 3 3 1

31 ２．１１ 引数の転送 手続きの主な特徴 プログラムのモジュール化設計 プログラミング作業の効率化 言語の拡張性の向上
２．１１　引数の転送 手続きの主な特徴 プログラムのモジュール化設計 プログラミング作業の効率化 言語の拡張性の向上 演算子を手続きとして定義して，式中で利用することができる

32 ２．１１ 引数の転送 引数 仮引数 integer procedure DIVIDE(X, Y) integer X, Y;
２．１１　引数の転送 引数 仮引数 integer procedure DIVIDE(X, Y) integer X, Y; if Y = 0 then return 0 else return X / Y ... A := DIVIDE(B, C) ... 実引数

33 ２．１１ 引数の転送 参照呼び 呼出し側：実引数の r 値へのポインタを渡す．実引数が l 値を持つ→ l 値
２．１１　引数の転送 参照呼び 呼出し側：実引数の r 値へのポインタを渡す．実引数が l 値を持つ→ l 値 　持たない→新しい場所を確保して，その l 値 呼び出された側：ポインタを通じての間接参照

34 ２．１１ 引数の転送 参照呼び procedure SWAP(X, Y) integer X, Y; begin integer TEMP;
２．１１　引数の転送 参照呼び procedure SWAP(X, Y) integer X, Y; begin integer TEMP; TEMP := X; X := Y; Y := TEMP end X 25 10 25 I Y 25 10 A[10] TEMP := X; X := Y; 10 TEMP := X; X := Y; Y := TEMP TEMP 10

35 ２．１１　引数の転送 値呼び 呼出し側：実引数を評価し， r 値を渡す． 呼び出された側：他の変数と同様に参照

36 ２．１１ 引数の転送 値呼び procedure SWAP(X, Y) integer X, Y; begin integer TEMP;
２．１１　引数の転送 値呼び procedure SWAP(X, Y) integer X, Y; begin integer TEMP; TEMP := X; X := Y; Y := TEMP end X 10 25 25 10 I Y 25 10 25 A[10] TEMP := X; X := Y; 10 TEMP := X; 10 X := Y; Y := TEMP TEMP

37 ２．１１　引数の転送 複写復元連係 値呼びの一般化 呼出し側：実引数の l 値を計算 呼び出された側：仮引数の値で実引数を更新

38 ２．１１ 引数の転送 複写復元連係 procedure SWAP(X, Y) integer X, Y; begin
２．１１　引数の転送 複写復元連係 procedure SWAP(X, Y) integer X, Y; begin integer TEMP; TEMP := X; X := Y; Y := TEMP end X 10 25 25 25 10 I Y 10 25 10 10 25 A[10] TEMP := X; X := Y; 10 TEMP := X; TEMP 10 X := Y; Y := TEMP Y := TEMP

39 ２．１１ 引数の転送 名前呼び 呼出し側：実引数は評価しない． l 値を r 値を計算可能なサンクを渡す．
２．１１　引数の転送 名前呼び 呼出し側：実引数は評価しない． l 値を r 値を計算可能なサンクを渡す． 呼び出された側：必要になったら実引数を評価する．

40 ２．１１ 引数の転送 名前呼び I A[I] procedure SWAP(X, Y) integer X, Y; begin
２．１１　引数の転送 I A[I] 名前呼び procedure SWAP(X, Y) integer X, Y; begin integer TEMP; TEMP := X; X := Y; Y := TEMP end X 25 10 25 I Y 25 A[10] TEMP := X; TEMP := X; X := Y; 10 10 X := Y; Y := TEMP TEMP 10 A[25]

41 ２．１２　記憶域管理 静的記憶割当て すべてのデータの大きさ固定 再帰手続きなし 名前と位置の結付けも静的に実行可能

42 ２．１２　記憶域管理 動的記憶割当て 再帰手続き→スタック割当て 可変データ構造→ヒープ割当て

43 ２．１２ 記憶域管理 記憶域のスタック割当て→活動記録 局所的な名前，配列，ポインタ 引数渡しのための一時記憶
２．１２　記憶域管理 記憶域のスタック割当て→活動記録 局所的な名前，配列，ポインタ 引数渡しのための一時記憶 翻訳時に未確定な局所的な名前と仮引数の属性に関する情報（例えば配列のサイズ） 戻り番地 呼出し側の活動記録へのポインタ

44 ２．１２ 記憶域管理 記憶域のスタック割当て→活動記録 配列 配列 活動記録 次の記録へのポインタ スタック ポインタ
２．１２　記憶域管理 記憶域のスタック割当て→活動記録 配列 配列 固定サイズのデータと可変 サイズ配列へのポインタ　　 活動記録 戻り番地 次の記録へのポインタ スタック ポインタ

45 ２．１２　記憶域管理 記憶域のスタック割当て→活動記録 ブロックＣ Ｃ Ｄ ブロックＡ ブロックＢ ブロックＤ Ｂ Ａ

46 ２．１２　記憶域管理 再帰とディスプレイ ディスプレイ P ... 活動記録の スタック B ... A

47 ２．１２ 記憶域管理 動的結合を伴う場合のスタックの割当て スタック上の最上位の識別子を探索 →時間が掛かりすぎる
２．１２　記憶域管理 動的結合を伴う場合のスタックの割当て スタック上の最上位の識別子を探索 →時間が掛かりすぎる 個々の識別子に対してスタックを用意

48 ２．１２ 記憶域管理 ヒープ割当て 実行時に可変長となるデータの処理 ゴミの識別，断片化，ゴミ集め 使用可能領域 未使用 Yの値 未使用
２．１２　記憶域管理 ヒープ割当て 実行時に可変長となるデータの処理 ゴミの識別，断片化，ゴミ集め 使用可能領域 未使用 Yの値 未使用 Xの値 未使用 Zの値 未使用

49 今後の予定 ５月１７日 講義（情コミ実験Ｉ） ５月２４日 講義（情コミ実験Ｉ） ５月３１日 創立記念日 ６月 ７日 講義 ６月１４日 講義
５月１７日　講義（情コミ実験Ｉ） ５月２４日　講義（情コミ実験Ｉ） ５月３１日　創立記念日 ６月　７日　講義 ６月１４日　講義 ６月２１日　国内出張 ６月２８日　海外出張 ７月　５日　講義 ７月１２日　講義 ７月１９日　試験