Document

言語処理系（２）
金子敬一
２プログラミング言語
２．１高水準プログ
ラミング言語
２．２プログラミング
言語の定義
２．３言語の字句構
造および構文構造
２．４データ要素
２．５データ構造
２．６演算子
２．７代入
２．８文
２．９プログラム単位
２．１０データ環境
２．１１引数の転送
２．１２記憶域管理
２．１高水準プログラミング言語
• 高水準プログラミング言語の利点
理解しやすさ
読み易い，書き易い，証明し易い
自然さ
アルゴリズムを自然に記述できる
移植性
色々な計算機上で実行できる
使用効率
プログラムの生産性が高い
２．１高水準プログラミング言語
• 信頼性
データ構造
有効範囲規則
制御構造
モジュール構造
生産性の向上に役立つ
機能
２．２プログラミング言語の定義
• 表記法
言語設計者
正しいプログラムとその意味を単純かつ明快に
表現可能
プログラマ
記述可能なプログラムとその動作を決定可能
コンパイラ設計者
受理すべき原始プログラムと生成すべき目的コー
ドを決定可能
２．２プログラミング言語の定義
• 構文
プログラム：アルファベットから選択された文字列
構文：ある文字列が正しいプログラムであるか否かを知
らせる規則
正規表現，文脈自由文法：構文指定のための決まり
２．２プログラミング言語の定義
• 意味
意味：プログラムに意味を与える規則
構文の指定より難しい
for I := 1 step 10 – J until 10 * J do
J := J + 1
第1の意味：10 * JとJはループの前に1度だけ評価
第2の意味：10 * JとJをループ毎に評価
第3の意味：増分が負ならば，終了条件をI < 10 * J
２．２プログラミング言語の定義
• 意味の指定法
操作的意味：抽象機械＋実行規則
翻訳：「文→文（既知）」の規則
公理的定義：「前データー（実行）→後データ」の規則
拡張可能定義：基本操作＋その組合せ
表示的意味：「プログラム→数学的対象」の規則
２．２プログラミング言語の定義
• プログラミング言語の階層構造
プログラム
サブルーチンおよびブロック
文
式
データ参照
演算子
関数
２．３言語の字句構造および構文構造
• アルファベット
プログラミング言語で使用される記号の集合：アルファベット，
文字集合
Σ={a, b, …, z, A, B, …, Z, [, ], (, ), +, -, *, /, …}
２．３言語の字句構造および構文構造
• 字句
もっとも低水準の部分文字列
多くのプログラミング言語では以下を字句とする：
定数．1, 2.3, 4.5E6, など
識別子．A, H2035B, SPEED, など
演算子記号．+, -, **, :=, .EQ., など
手掛かり語．IF, GOTO, SUBROUTINE, など
区切り記号．(, ), {, }, ,, ;, など
２．３言語の字句構造および構文構造
• 上位レベルの構成要素
字句の集まり
→構文構造
一般に構文構造は式を含む
式，代入演算子，区切り記号，手掛かり語
→上位レベルの構成要素を形成する際の要素
２．３言語の字句構造および構文構造
• 字句解析上の約束
固定形式：文の要素を入力行の決められた位置に書く
自由形式：文の要素を入力行のどこに書いても良い
→こちらが主流
FortranやAlgol68では文字列中以外の空白は無視さ
れる→字句解析作業は複雑化
DO 10 I = 1.3
⇒ DO10I = 1.3
...
10 CONTINUE
２．４データ要素
• 基本的なデータ要素
ALGOL
FORTRAN
PASCAL
PL/I
数値データ
Ｖ
Ｖ
Ｖ
Ｖ
論理データ
Ｖ
Ｖ
Ｖ
Ｖ
文字データ
―
―
Ｖ
Ｖ
ポインタ
―
―
Ｖ
Ｖ
名札
―
―
―
Ｖ
２．４データ要素
• 識別子および名前
対象：計算機が操作したり，使用したりするデータ
要素，配列，手続き．記憶に格納される．
記憶の単位は名前をもつ．
名前は識別子によって表現．値と属性をもつ．
同じ識別子が別の名前を表現しうる．
２．４データ要素
• 識別子および名前
void proc1()
{
int x = 12;
...
}
void proc2()
{
double x = 12;
...
}
２．４データ要素
• 属性
型（とりうる値，適用可能な演算，演算の効果）
有効範囲
２．４データ要素
• 宣言
FORTRAN：暗黙の型宣言
I, …, Nで始まる識別子は，陽に宣言しなければ整数
PL/I：数値は４種類の属性―モード，スケール，進法，精
度―をもつ
DECLARE A DECIMAL FLOAT(10)
⇒浮動小数点，１０進法，１０桁精度，モードは実数（省略
値）
２．４データ要素
• 属性と名前の結合
結合：属性と名前を対応させること
静的結合：コンパイル時に結合を決定⇒強力な型検査
動的結合：実行時に結合を検査
ちょっと休憩
（雑談）
中国語編
• 日中で意味の異なる言葉
日本の意味
中国の意味
湯
お湯
スープ
愛人
愛人
伴侶
猪
いのしし
ブタ
煤
スス
石炭
走
走る
歩く
手紙
手紙
トイレットペーパー
勉強
勉強
無理強い
検討
検討
自己批判
質問
質問
詰問
中国語編
• 外来語を漢字に直す→「意味から」と「音から」
—意味編
西北航空（ノースウエスト），汽水（サイダー），電視（機）
（テレビ）
—音編
啤酒（ビール），威士忌（ウイスキー），白闌地（ブランデー）
可口可楽（コカコーラ），夏威夷（ハワイ）
休憩おわり
２．５データ構造
• 再帰的データ構造
struct cell {
int val;
「空リスト」，または「データ
struct cell *next;
要素の後にリストの続くもの」 };
リスト
木
１つの節点が根
残りの節点は，根の子で
ある部分木に分割可能
struct node {
int val;
struct node *left;
struct node *right;
};
２．５データ構造
• 一般的なデータ構造
配列，キュー，スタック，文字列，グラフなど
構成子
破壊子
選択子
共通に備わっている関数
２．５データ構造
• 配列
同じ型を持つ要素の集合
k次元の直方体状に並べられたもの
2次元
0次元
1次元
A
A[1,2,0]
添字
２．５データ構造
• 固定サイズ１次元配列
配列A
アドレス
A[LOW]
BASE
A[LOW A[LOW
+1]
+2]
...
BASE
+k
... BASE+ ...
k*(i-LOW)
BASE
+2*k
A[i]
...
２．５データ構造
• 固定サイズ多次元配列
A[1,1] A[1,2] A[1,3]
A[2,1] A[2,2] A[2,3]
A[1,1]
A[1,2]
A[1,3]
A[2,1]
A[2,2]
A[2,3]
行順
列順
A[1,1]
A[2,1]
A[1,2]
A[2,2]
A[1,3]
A[2,3]
２．５データ構造
• 固定サイズ多次元配列
行順
配列A
A[1,1] A[1,2] A[1,3] A[2,1] A[2,2] A[2,3]
アドレス
BASE
BASE
+k
BASE
+2*k
BASE
+3*k
BASE
+4*k
BASE
+5*k
A[i,j] ⇒ BASE+k*((i-LOWr)*HIGHc+(j-LOWc)
２．５データ構造
• 固定サイズ多次元配列
列順
配列A
A[1,1] A[2,1] A[1,2] A[2,2] A[1,3] A[2,3]
アドレス
BASE
BASE
+k
BASE
+2*k
BASE
+3*k
BASE
+4*k
BASE
+5*k
A[i,j] ⇒ BASE+k*((j-LOWc)*HIGHr+(i-LOWr)
２．５データ構造
• 辺ベクトルによる２次元配列
A[1,1]
A[1,2]
A[1,3]
A[2,1]
A[2,2]
A[2,3]
２．５データ構造
• 動的配列
—多くの言語で，配列の大きさを動的に指定可能
—配列の要素へアクセスするためのアドレス計算は，
固定の場合と同じ．
—添字の上下限は，データ記述子から調べる．
２．５データ構造
• レコード構造
—レコード欄を子，部分欄を孫としてもつ木構造
—郵送先名簿を以下のように格納したい：
MR. ALAN TURING
172 THE GRADUATE COLLEGE
PRINCETON, N. J. 08540
２．５データ構造
• レコード構造
1 FRIENDS(1000),
2 NAME,
3 TITLE CHARACTER(6), MR.
3 FIRST CHARACTER(15), ALAN
3 LAST CHARACTER(15), TURING
2 ADDRESS,
3 STREET CHARACTER(30), 172 THE GRADUATE COLL
3 TOWN CHARACTER(15), PRINCETON
3 STATE CHARACTER(15), N. J.
3 ZIP FIXED DECIMAL(5); 08540
２．５データ構造
• レコード構造
FRIENDS NAME
TITLE
MR.
FIRST
ALAN
LAST
TURING
ADDRESS STREET 1 7 2
THE
GRAD
TOWN
PRINCETON
STATE
N.
ZIP
08540
...
J.
X = FRIENDS(123).ADDRESS.STATE
⇒BASE + 100 * (123 - 1) + 36 + 45 = BASE + 12281
２．５データ構造
• 文字列
—文字列の長さを指定する必要なし：
SNOBOL⇒動的な記憶域の割当て
—文字列の長さの上限が規定：
PL/I⇒文字列の長さを表すデータ記述子
２．５データ構造
• リスト構造
—carとcdrという２つの欄からなるレコード構造
—各欄は，アトム，空ポインタ，他のレコード番地の
いずれか
整数や文字などの基
本的なデータ型
—さらにアトムとポインタの判別に２つの欄，ゴミか
否か判別するのに１つの欄が必要
２．５データ構造
• リスト構造
CAR CDR
’B’
1
[’A’, 2, ’B’, 1]
’A’
2
２．５データ構造
• スタック
-2.14
’B’
スタックポインタ
1024
スタックサイズの上限が決まって
いれば，その大きさの配列を使い
実現可能
’A’
２．６演算子
• 算術演算子
—演算子+, -, *, /, **（または^）が有名
—演算子-は，単項にも２項にも用いられる．
—単項演算子→前置または後置
言語Cでは，++は前置，後置いずれにも使用可
X=++Y; → Y=Y+1; X=Y;
X=Y++; → X=Y; Y=Y+1;
—２項演算子→前置，中置，または後置
２．６演算子
• 算術式
—データ参照は式
—+を２項中置演算子，E1, E2を式
⇒ E1 + E2は式
—+を単項前置演算子，Eを式
⇒ + Eは式
—+を単項後置演算子，Eを式
⇒ E +は式
—Eを式
⇒ (E)は式
２．６演算子
• 関係演算子
—２項演算子
—論理値（たとえばtrueやfalse）を返す
—代表的なものに<=, <, =, <>, >=, >がある
２．６演算子
• 論理演算子
—論理値をもつ引数，論理値を返す．
—論理積and
—論理和or
—論理否定not
—排他的論理和xor（またはeor）
２．６演算子
• 文字列演算子
—文字列を対象とする．
—連接
”abcd” + ”efg” ⇒ ”abcdefg”
—部分列の取り出し
—パタン照合
２．６演算子
• 結合性と順位
左結合的
右結合的
—a+b+c → (a+b)+cか， a+(b+c)か？
—a+b**c で，+は左結合的で **は右結合的
a+b**c → (a+b)**cか， a+(b**c)か？
+の順位＞**の順位
+の順位＜**の順位
２．６演算子
• 演算子の優先順位
単項演算子
ALGOL
FORTRAN
PI/I
^
**
** + -
+ -
* /
* /
< = > < = >
+ -
+ -
.LT. .EQ. .GT.
||
.LE. .NE. .GE.
< = > <= >=
.NOT.
<
=
.AND.
&
.OR.
|
>
２．６演算子
• 演算子の代数的性質
—可換則 x + y = y + x
a + b * c = b * c + a
—結合則 (x + y) + z = x + (y + z)
(a * 3) * 2 = a * (3 * 2) = a * 6
—分配則 (x + y) * z = x * z + y * z
a * 2 + b * 2 = (a + b) * 2
２．６演算子
• その他の演算子（代入以外）
—条件式：ALGOLのif A then B else CやCの
A ? B : Cなど．これは３項演算子
—選択子：配列の添字付け，レコード構造の欄名の
指定
A[1,2,i]
変項演算子あるいは多項演算子
２．６演算子
• 型強制
—異なる型の引数をとりうる演算子：Aが整数型で，
Bが実数型のとき，A+Bの結果の型は？
—暗黙の型変換：Aを実数型に変換してから加算を
実行するようなコードを生成
２．６演算子
• 演算子の実現
—多くの演算子→機械命令
算術演算子や論理演算子などの多くの演算子
—関係演算子→比較命令＆条件分岐命令
—その他→機械命令列やサブルーチン
よい連休を

Download Report