Document

言語処理系（３）
金子敬一
２プログラミング言語
２．１高水準プログ
ラミング言語
２．２プログラミング
言語の定義
２．３言語の字句構
造および構文構造
２．４データ要素
２．５データ構造
２．６演算子
２．７代入
２．８文
２．９プログラム単位
２．１０データ環境
２．１１引数の転送
２．１２記憶域管理
２．７代入
• 代入演算子
A := B
A = B
A ← B
LET A = B
MOVE B TO A
PASCAL, ALGOL
C, FORTRAN
APL
BASIC
COBOL
以下では，:=を代入演算子，=を等号とする．
２．７代入
• l 値と r 値
A := B
名前Aの位置へ名前Bの値を代入せよ
名前は代入演算子の左辺と右辺では意味が異なる．
l値
r値
２．７代入
• l 値と r 値
式の r 値 ⇒ その式の示す値
一方，式は常に l 値を持つとは限らない
• すべての名前
• Aが配列名⇒A[I]の l 値は，配列Aの第I番目の要素
の位置， r 値はA[I]に格納している値
• 定数は， r 値のみ持ち， l 値を持たない
• ポインタPの r 値は，Pの指す位置であり， l 値はPの値
を格納している位置
２．７代入
• l 値と r 値
• ポインタPの r 値は，Pの指す位置であり， l 値はPの値
を格納している位置
P
P := P + 1
P
２．７代入
•
代入の実現（A := Bの１つの実現
法）
1. Bの r 値を計算し，レジスタrに入れる
コードを生成
2. AとBの型が不一致 ⇒ Bの r 値をAに適
合するように型変換
3. 必要があればAの l 値を計算するコード
を生成
4. レジスタrの内容をAの l 値へ格納する
ためのコードを生成
２．７代入
•
代入の実現例（X[I] := Y[J]）
１語４バイト
XおよびY：固定位置，整数型
添え字は0から始まる
整数型の各要素は１語を占める
２．７代入
•
代入の実現例（X[I] := Y[J]）
1. Bの r 値を計算し，レジスタrに入れる
コードを生成
LOAD J, r2
/* Jをr2にロードする */
MULT #4, r2
/* r2を4倍する */
LOAD Y(r2), r1
２．７代入
•
代入の実現例（X[I] := Y[J]）
2. AとBの型が不一致 ⇒ Bの r 値をAに適
合するように型変換
X[I]とY[I]の型は一致⇒コード生成不要
２．７代入
•
代入の実現例（X[I] := Y[J]）
3. 必要があればAの l 値を計算するコード
を生成
LOAD I, r2
MULT #4, r2
/* Iをr2にロードする */
/* r2を4倍する */
２．７代入
•
代入の実現例（X[I] := Y[J]）
4. レジスタrの内容をAの l 値へ格納するた
めのコードを生成
STORE r1, X(r2) /* r1をX(r2)にロードする */
２．７代入
•
代入の実現例（X[I] := Y[J]）
LOAD J, r2
MULT #4, r2
/* Jをr2にロードする */
/* r2を4倍する */
LOAD Y(r2), r1
LOAD I, r2
/* Y(r2)をr1にロードする */
/* Iをr2にロードする */
MULT #4, r2
/* r2を4倍する */
STORE r1, X(r2) /* r1をX(r2)にロードする */
２．７代入
•
演算子としての代入
— 代入演算子を２項中置演算子として扱う
言語（Cなど）
Cにおいて
A = (B = C + D) + (E = F + G)
と書かれた式は，
B = C + D, E = F + G, A = B + E
と解釈可能
２．７代入
•
より一般的な代入
— A := B の両辺が単純でない場合
PL/IにおいてAを整数配列とするとA := 0と書かれ
た式は，配列Aの全要素を0に初期化する
練習問題２．１
•
r 値および l 値を持つものはどれか
A[I+1]
r値
l値
*A
&A
&(*A)
*(&A)
*(&(&A))
２．８文
•
単純文と複合文
— 単純文：その中に文を含まない文
— 複合文：1つ以上の文を含む文
if 条件 then 文
if 条件 then 文 else 文
begin 文; 文; ...; 文 end
while 条件 do 文
for 識別子 := 初期値 to 終値 do 文
Pascalの
複合文
２．８文
•
文の型
— 計算文：代入文など
— 順序制御文：goto文，break文，call文，
return文など
— 構造文：END文など
— 宣言文：コード生成なし．記号表への登録
— 入出力文：入出力装置を制御．書式を使用
２．９プログラム単位
• FORTRAN
— １つの主プログラム＋０個以上の副プロ
グラム
— 副プログラム：サブルーチン，関数，ブロッ
クデータ
— 分割コンパイル可能
— 主プログラム，サブルーチン，関数：宣言
列＋実行文列
— 大域データ：COMMON文で参照；その他の
データは局所的となる
２．９プログラム単位
• ALGOL
— ブロック構造化言語
— 名前の有効範囲
・ブロックB中で宣言された名前は，ブロックBで
のみ有効
・ブロックB’がブロックB中に入れ子になっている
ならば，Bで有効な名前は，B’でそれに対応す
る識別子が再宣言されていなければ，B’中でも
有効
２．９プログラム単位
ブ
ロ
ッ
ク
１
begin
real X, Y;
begin
real Y;
ブ begin
ロ
real X;
ッ
...
ク
ブ
ロ
３ end
ッ
...
ク
２
ブ begin
ロ
real Y;
ッ
...
ク
４ end
end
end
X
X
Y
Y
Y
２．９プログラム単位
• PL/I
— FORTRANとALGOLの折衷
— プログラムは外部手続きの集合
— そのうちの1つが主プログラム
— 分割コンパイル可能
— ブロックや内部手続きを入れ子にできる
ちょっと休憩
（雑談）
ラテン語編
• 類似の言葉
スペイン語
フランス語
英語
botella
bouteille
bottle
claro
clair
clear
estudiar
etudier
study
fruta
fruit
fruit
importante
important
important
música
musique
music
moderno
moderne
modern
papel
papier
paper
persona
personne
person
ラテン語編
• 日本語とスペイン語
外来語
—manto （マント）
—velludo （びろうど）
—capa （合羽）
—carta （カルタ）
要注意
—No sé. （野瀬）
—Da me. （駄目）
—Y caga? （いかが？）
休憩おわり
２．１０データ環境
• 環境
– 識別子と名前との対応
– 文の環境
– ブロックの環境
– 副ブロックの環境
２．１０データ環境
• 識別子と名前の結合
– 識別子→名前
– 名前→位置
– 静的な結合: FORTRAN, ALGOL, PL/I
– 動的な結合: LISP, APL, SNOBOL
２．１０データ環境
• 有効範囲規則
– 有効範囲：その名前を使うことのできる，プロ
グラムの部分のこと
– ALGOLなど：至近規則
– LISPなど：他の規則
２．１０データ環境
• 有効範囲規則
– LISPなど：他の規則
値をスタックに退避して，回復する．
(defun f (x) (setq x (+ x 1)) (g) (print x))
(defun g () (print x) (setq x 1))
(defun h ()
2 1
3
3
1
(setq x 3) (f 1) (print x) (g) (print x))
２．１１引数の転送
• 手続きの主な特徴
– プログラムのモジュール化設計
– プログラミング作業の効率化
– 言語の拡張性の向上
演算子を手続きとして定義して，式中で利用す
ることができる
２．１１引数の転送
• 引数
仮引数
integer procedure DIVIDE(X, Y) integer X, Y;
if Y = 0 then return 0
else return X / Y
実引数
... A := DIVIDE(B, C) ...
２．１１引数の転送
• 参照呼び
– 呼出し側：実引数の r 値へのポインタを渡す．
実引数が l 値を持つ→ l 値
持たない→新しい場所を確保して，その l 値
– 呼び出された側：ポインタを通じての間接参
照
２．１１引数の転送
• 参照呼び
procedure SWAP(X, Y) X
integer X, Y;
begin
Y
integer TEMP;
TEMP := X;
TEMP
X := Y;
Y := TEMP
end
10
25
10
I
25
10
A[10]
２．１１引数の転送
• 値呼び
– 呼出し側：実引数を評価し， r 値を渡す．
– 呼び出された側：他の変数と同様に参照
２．１１引数の転送
• 値呼び
procedure SWAP(X, Y) X
integer X, Y;
begin
Y
integer TEMP;
TEMP := X;
TEMP
X := Y;
Y := TEMP
end
25
10
10
I
25
A[10]
25
10
10
２．１１引数の転送
• 複写復元連係
– 値呼びの一般化
– 呼出し側：実引数の l 値を計算
– 呼び出された側：仮引数の値で実引数を更
新
２．１１引数の転送
• 複写復元連係
procedure SWAP(X, Y) X
integer X, Y;
begin
Y
integer TEMP;
TEMP := X;
TEMP
X := Y;
Y := TEMP
end
25
10
10
25
I
25
10
A[10]
25
10
10
２．１１引数の転送
• 名前呼び
– 呼出し側：実引数は評価しない． l 値を r 値
を計算可能なサンクを渡す．
– 呼び出された側：必要になったら実引数を評
価する．
２．１１引数の転送
I
A[I]
• 名前呼び
procedure SWAP(X, Y) X
integer X, Y;
begin
Y
integer TEMP;
TEMP := X;
TEMP
X := Y;
Y := TEMP
end
25
10
I
25
A[10]
10
A[25]
10
２．１２記憶域管理
• 静的記憶割当て
– すべてのデータの大きさ固定
– 再帰手続きなし
– 名前と位置の結付けも静的に実行可能
２．１２記憶域管理
• 動的記憶割当て
– 再帰手続き→スタック割当て
– 可変データ構造→ヒープ割当て
２．１２記憶域管理
• 記憶域のスタック割当て→活動記録
– 局所的な名前，配列，ポインタ
– 引数渡しのための一時記憶
– 翻訳時に未確定な局所的な名前と仮引数の
属性に関する情報（例えば配列のサイズ）
– 戻り番地
– 呼出し側の活動記録へのポインタ
２．１２記憶域管理
• 記憶域のスタック割当て→活動記録
配列
配列
固定サイズのデータと可変
サイズ配列へのポインタ
戻り番地
スタック
ポインタ
次の記録へのポインタ
活動記録
２．１２記憶域管理
• 記憶域のスタック割当て→活動記録
ブ
ロ
ッ
ク
Ａ
ブ
ロ
ッ
ク
Ｂ
ブ
ロ
ッ
ク
Ｃ
ブ
ロ
ッ
ク
Ｄ
Ｃ
Ｄ
Ｂ
Ａ
２．１２記憶域管理
• 再帰とディスプレイ
ディスプレイ
P
...
B
...
A
活動記録の
スタック
２．１２記憶域管理
• 動的結合を伴う場合のスタックの割当て
– スタック上の最上位の識別子を探索
→時間が掛かりすぎる
– 個々の識別子に対してスタックを用意
２．１２記憶域管理
• ヒープ割当て
– 実行時に可変長となるデータの処理
– ゴミの識別，断片化，ゴミ集め
使用可能領域
未使用 Yの値未使用 Xの値未使用 Zの値未使用
今後の予定
•
•
•
•
•
•
•
•
•
•
５月１７日
５月２４日
５月３１日
６月７日
６月１４日
６月２１日
６月２８日
７月５日
７月１２日
７月１９日
講義（情コミ実験Ｉ）
講義（情コミ実験Ｉ）
創立記念日
講義
講義
国内出張
海外出張
講義
講義
試験

Download Report