アルゴリズムとデータ構造1

コンパイラ
2012年10月29日
酒居敬一＠Ａ４６８([email protected])
http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/COMP/2012/index.html
1
意味解析
前回までの内容


構文解析では表面的な形式の整合性だけを見た。

「識別子名＝識別子名＋識別子名」と推定された式があったとして、
識別子名が変数名なのか関数名なのかは関知しない、では片手落ち。
今回の内容


各字句の意味に立ち入った解析とエラーチェックを行う。



2
識別子を変数・関数・配列・定数などに区別する。
そのための名前表に要求される情報を明らかにする。
実際の例を挙げる。
名前表
何の名前か？


変数・関数・仮引数・定数・一時変数・自動変数など。
型


整数・実数・文字・文字列・配列・関数・構造型など。
語長



１バイト・２バイト・４バイト・８バイト
スカラー・ベクター。
種別


全域的・ブロックなど。永続的・一時的・自動的など。
アドレス
対応するソースプログラム中の行・桁


3
名前表を使ったエラーチェック
二重宣言のチェック


同じ名前が２度定義されてるとエラー。

ただし、通用範囲外に関してはエラーにならない場合が多い。
未定義チェック


通用範囲内に参照する名前の物がなければエラー。
左辺値チェック


代入文・代入式の左辺に代入可能な物が置かれているか？
型の整合性チェック




4
型が同一視できるかどうか？
型を自動変換してもいいかどうか？
なお、ここでできるのは静的な型チェックのみ。
名前表の探索１

名前から表中の該当エントリを探さないといけない。

線形探索

探索にＯ（ｎ）必要。アルゴリズムは単純。
二分探索


探索はＯ（n）必要。追加・削除を考え、構造型データで木を生成。
ハッシュ


開番地法


分離連鎖法

5
名前の個数が配列の大きさまでという制約を受けてしまう。
衝突が起きても使い続けることができる。一般的な方法。
スコープ（通用範囲）
ＣやJavaでは、名前の通用範囲が決まっている。





ファイルやブロックといった単位で範囲を決めている。
通用範囲の外側では、内側で定義した物は存在しない。
同じ通用範囲内で同名の物を定義するとエラー。
通用範囲の外側の物と同名の物を内側で定義することは可。

この場合、その名前で最も内側の物が見える。
名前表の名前は通用範囲と組み合わせる必要がある。


参照しようとしている場所から範囲外へ参照対象を探す。
ストレージクラスと通用範囲は別の概念。



6
ストレージクラス：自動変数・静的変数・インスタンス変数
通用範囲：全域・ファイル・クラス・ブロック
名前表の探索２
通用範囲ごとの名前表へのポインタをスタックに置く。




通用範囲に入ったら新しい名前表をスタックへプッシュ。
通用範囲から出たらポップ。
名前はスタックトップ側の名前表から、ボトム側の名前表へ
順に調べていく。
スタックボトム
全域
ファイル
関数
ブロック１
ブロック２
7
スタックトップ
例：数
Ｃの場合を取り上げる。




float
x = 1.0;としておきます。
sizeof(float)とsizeof(long)は同じ４バイトとします。
sizeof(char)は１バイトとします。
式
その値
型
1/10
0
整数
1/10.0
0.1
浮動小数点数
x+33554432
33554432.0
浮動小数点数
(long)x + 33554432
33554433
整数
*((long *)(&x))
0x3F800000
整数
0x3F800000
1065353216
整数
(char)-1
0b11111111
整数
(unsigned char)0xFF
0b11111111
整数
1==2
0
整数
8
キャストのルール(抜粋)
整数の格上げ


元の型(char, short)のすべての値がintで表せればintに、
unsigned intで表せればunsigned intに変換する。
整数と浮動小数点数



浮動小数点数を整数に変換するとき、小数部分は切り捨て。
整数を浮動小数点数に変換するとき、最も近い値に変換。
浮動小数点型



より精度の高い型に変換するとき、値は不変。
より精度の低い型に変換するとき、表現可能な近い値に変換。
算術変換



9
２項のうち大きなほうの型に変換される。
２項のうち精度の高いほうの型に変換される。
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
#include <stdio.h>
ひどいプログラムの例
extern int a, b, c;
int hoge(int x)
{
return x + 100.0;
}
int main()
{
int c;
unsigned int
i;
c = hoge(a);
hoge = b;
for(i = 6; 0 <= i; i--){
printf("Hello!\n");
}
return main;
}
[sakai@star 2011]$ gcc -Wall -Wextra hoge.c
hoge.c: In function `main':
hoge.c:16: error: invalid lvalue in assignment
hoge.c:18: warning: comparison of unsigned expression >= 0 is always true
hoge.c:21: warning: return makes integer from pointer without a cast
10
演習（予習）
学生番号：____________ 名前：______________
1.
C言語で全域的な変数を定義したとする。
int
int
2.
この定義がコンパイラにより次のように翻訳された。
a:
b:
3.
a = 20;
b[3] = {1, 2, 3};
.word
.word
これらを次のように使うとエラーになる場合があった。
どこがエラーになるでしょうか？その理由は？
int
*p = b;
a = 1;
b = 9;
p += a;
a = p[0] + b[1];
11
20
1, 2, 3

Download Report