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

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

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

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

3 ２．１ 高水準プログラミング言語 高水準プログラミング言語の利点 理解しやすさ 自然さ 移植性 使用効率 読み易い，書き易い，証明し易い
２．１　高水準プログラミング言語 高水準プログラミング言語の利点 理解しやすさ 自然さ 移植性 使用効率 読み易い，書き易い，証明し易い アルゴリズムを自然に記述できる 色々な計算機上で実行できる プログラムの生産性が高い

4 ２．１　高水準プログラミング言語 信頼性 データ構造 有効範囲規則 制御構造 モジュール構造 生産性の向上に役立つ機能

5 ２．２ プログラミング言語の定義 表記法 言語設計者 正しいプログラムとその意味を単純かつ明快に表現可能 プログラマ コンパイラ設計者
２．２　プログラミング言語の定義 表記法 　　言語設計者 プログラマ コンパイラ設計者 正しいプログラムとその意味を単純かつ明快に表現可能 記述可能なプログラムとその動作を決定可能 受理すべき原始プログラムと生成すべき目的コードを決定可能

6 ２．２ プログラミング言語の定義 構文 プログラム：アルファベットから選択された文字列 構文：ある文字列が正しいプログラムであるか否かを知
２．２　プログラミング言語の定義 構文 プログラム：アルファベットから選択された文字列 構文：ある文字列が正しいプログラムであるか否かを知 　　　　らせる規則 正規表現，文脈自由文法：構文指定のための決まり

7 ２．２ プログラミング言語の定義 意味 意味：プログラムに意味を与える規則 構文の指定より難しい
２．２　プログラミング言語の定義 意味 意味：プログラムに意味を与える規則 　　　　構文の指定より難しい 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

8 ２．２ プログラミング言語の定義 意味の指定法 操作的意味：抽象機械＋実行規則 翻訳：「文→文（既知）」の規則
２．２　プログラミング言語の定義 意味の指定法 操作的意味：抽象機械＋実行規則 翻訳：「文→文（既知）」の規則 公理的定義：「前データー（実行）→後データ」の規則 拡張可能定義：基本操作＋その組合せ 表示的意味：「プログラム→数学的対象」の規則

9 ２．２　プログラミング言語の定義 プログラミング言語の階層構造 プログラム サブルーチンおよびブロック 文 式 データ参照 演算子 関数

10 ２．３ 言語の字句構造および構文構造 アルファベット
２．３　言語の字句構造および構文構造 アルファベット プログラミング言語で使用される記号の集合：アルファベット，文字集合 Σ={a, b, …, z, A, B, …, Z, [, ], (, ), +, -, *, /, …}

11 ２．３ 言語の字句構造および構文構造 字句 もっとも低水準の部分文字列 多くのプログラミング言語では以下を字句とする：
２．３　言語の字句構造および構文構造 字句 もっとも低水準の部分文字列 多くのプログラミング言語では以下を字句とする： 定数．1, 2.3, 4.5E6, など 識別子．A, H2035B, SPEED, など 演算子記号．+, -, **, :=, .EQ., など 手掛かり語．IF, GOTO, SUBROUTINE, など 区切り記号．(, ), {, }, ,, ;, など

12 ２．３ 言語の字句構造および構文構造 上位レベルの構成要素 字句の集まり →構文構造 一般に構文構造は式を含む
２．３　言語の字句構造および構文構造 上位レベルの構成要素 字句の集まり →構文構造 一般に構文構造は式を含む 式，代入演算子，区切り記号，手掛かり語 →上位レベルの構成要素を形成する際の要素

13 ２．３ 言語の字句構造および構文構造 字句解析上の約束 固定形式：文の要素を入力行の決められた位置に書く
２．３　言語の字句構造および構文構造 字句解析上の約束 固定形式：文の要素を入力行の決められた位置に書く 自由形式：文の要素を入力行のどこに書いても良い →こちらが主流 FortranやAlgol68では文字列中以外の空白は無視される→字句解析作業は複雑化 DO 10 I = 1.3 ... 10 CONTINUE ⇒　　DO10I = 1.3

14 ２．４ データ要素 基本的なデータ要素 ALGOL FORTRAN PASCAL PL/I 数値データ Ｖ 論理データ 文字データ ―
２．４　データ要素 基本的なデータ要素 ALGOL FORTRAN PASCAL PL/I 数値データ Ｖ 論理データ 文字データ ― ポインタ 名札

15 ２．４ データ要素 識別子および名前 対象：計算機が操作したり，使用したりするデータ要素，配列，手続き．記憶に格納される．
２．４　データ要素 識別子および名前 対象：計算機が操作したり，使用したりするデータ要素，配列，手続き．記憶に格納される． 記憶の単位は名前をもつ． 名前は識別子によって表現．値と属性をもつ． 同じ識別子が別の名前を表現しうる．

16 ２．４ データ要素 識別子および名前 void proc1() { int x = 12; ... } void proc2()
２．４　データ要素 識別子および名前 void proc1() { int x = 12; ... } void proc2() double x = 12;

17 ２．４　データ要素 属性 型（とりうる値，適用可能な演算，演算の効果） 有効範囲

18 ２．４ データ要素 宣言 FORTRAN： 暗黙の型宣言 I, …, Nで始まる識別子は，陽に宣言しなければ整数
２．４　データ要素 宣言 FORTRAN：　暗黙の型宣言 　I, …, Nで始まる識別子は，陽に宣言しなければ整数 PL/I：　数値は４種類の属性―モード，スケール，進法，精度―をもつ DECLARE A DECIMAL FLOAT(10) ⇒浮動小数点，１０進法，１０桁精度，モードは実数（省略値）

19 ２．４ データ要素 属性と名前の結合 結合：属性と名前を対応させること 静的結合：コンパイル時に結合を決定⇒強力な型検査
２．４　データ要素 属性と名前の結合 結合：属性と名前を対応させること 静的結合：コンパイル時に結合を決定⇒強力な型検査 動的結合：実行時に結合を検査

20 ちょっと休憩 （雑談）

21 中国語編 日中で意味の異なる言葉 日本の意味 中国の意味 湯 お湯 スープ 愛人 伴侶 猪 いのしし ブタ 煤 スス 石炭 走 走る 歩く
手紙 トイレットペーパー 勉強 無理強い 検討 自己批判 質問 詰問

22 中国語編 外来語を漢字に直す→「意味から」と「音から」 意味編 西北航空（ノースウエスト），汽水（サイダー），電視（機） （テレビ） 音編
　西北航空（ノースウエスト），汽水（サイダー），電視（機） 　（テレビ） 音編 　啤酒（ビール），威士忌（ウイスキー），白闌地（ブランデー） 　可口可楽（コカコーラ），夏威夷（ハワイ）

23 休憩おわり

24 ２．５ データ構造 再帰的データ構造 リスト struct cell { int val; 「空リスト」，または「データ
２．５　データ構造 再帰的データ構造 リスト 　「空リスト」，または「データ 　要素の後にリストの続くもの」 木 　１つの節点が根 　残りの節点は，根の子で 　ある部分木に分割可能 struct cell { int val; struct cell *next; }; struct node { struct node *left; struct node *right;

25 ２．５　データ構造 一般的なデータ構造 配列，キュー，スタック，文字列，グラフなど 構成子 破壊子　　　共通に備わっている関数 選択子

26 ２．５　データ構造 配列 同じ型を持つ要素の集合 k次元の直方体状に並べられたもの A[1,2,0] 2次元 A 添字 0次元 1次元

27 ２．５ データ構造 固定サイズ１次元配列 A[LOW +1] A[LOW +2] 配列A A[LOW] ... A[i] ... BASE
２．５　データ構造 固定サイズ１次元配列 A[LOW +1] A[LOW +2] 配列A A[LOW] ... A[i] ... BASE BASE +k BASE +2*k BASE+ k*(i-LOW) アドレス ... ...

28 ２．５ データ構造 固定サイズ多次元配列 A[1,1] A[1,2] A[1,3] A[2,1] A[2,2] A[2,3] A[1,1]
２．５　データ構造 固定サイズ多次元配列 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] 行順 列順

29 A[i,j] ⇒ BASE+k*((i-LOWr)*HIGHc+(j-LOWc)
２．５　データ構造 固定サイズ多次元配列 行順 配列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)

30 A[i,j] ⇒ BASE+k*((j-LOWc)*HIGHr+(i-LOWr)
２．５　データ構造 固定サイズ多次元配列 列順 配列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)

31 ２．５　データ構造 辺ベクトルによる２次元配列 A[1,1] A[1,2] A[1,3] A[2,1] A[2,2] A[2,3]

32 ２．５ データ構造 動的配列 多くの言語で，配列の大きさを動的に指定可能 配列の要素へアクセスするためのアドレス計算は， 固定の場合と同じ．
２．５　データ構造 動的配列 多くの言語で，配列の大きさを動的に指定可能 配列の要素へアクセスするためのアドレス計算は， 　固定の場合と同じ． 添字の上下限は，データ記述子から調べる．　

33 ２．５ データ構造 レコード構造 レコード欄を子，部分欄を孫としてもつ木構造 郵送先名簿を以下のように格納したい：
２．５　データ構造 レコード構造 レコード欄を子，部分欄を孫としてもつ木構造 郵送先名簿を以下のように格納したい： MR. ALAN TURING 172 THE GRADUATE COLLEGE PRINCETON, N. J

34 ２．５ データ構造 レコード構造 1 FRIENDS(1000), 2 NAME, 3 TITLE CHARACTER(6),
２．５　データ構造 レコード構造 1 FRIENDS(1000), 2 NAME, 3 TITLE CHARACTER(6), 3 FIRST CHARACTER(15), 3 LAST CHARACTER(15), 2 ADDRESS, 3 STREET CHARACTER(30), 3 TOWN CHARACTER(15), 3 STATE CHARACTER(15), 3 ZIP FIXED DECIMAL(5); MR. ALAN TURING 172 THE GRADUATE COLLEGE PRINCETON N. J. 08540

35 ２．５ データ構造 ... レコード構造 M R . A L N T U I G 1 7 2 H E D P C O J 8 5 4
２．５　データ構造 レコード構造 M R . A L N T U I G 1 7 2 H E D ... P C O J 8 5 4 FRIENDS NAME TITLE FIRST LAST ADDRESS STREET TOWN STATE ZIP X = FRIENDS(123).ADDRESS.STATE ⇒BASE * ( ) = BASE

36 ２．５ データ構造 文字列 文字列の長さを指定する必要なし： SNOBOL⇒動的な記憶域の割当て 文字列の長さの上限が規定：
２．５　データ構造 文字列 文字列の長さを指定する必要なし： 　SNOBOL⇒動的な記憶域の割当て 文字列の長さの上限が規定： 　PL/I⇒文字列の長さを表すデータ記述子

37 ２．５ データ構造 リスト構造 carとcdrという２つの欄からなるレコード構造 各欄は，アトム，空ポインタ，他のレコード番地の いずれか
２．５　データ構造 リスト構造 carとcdrという２つの欄からなるレコード構造 各欄は，アトム，空ポインタ，他のレコード番地の 　いずれか さらにアトムとポインタの判別に２つの欄，ゴミか 　否か判別するのに１つの欄が必要 整数や文字などの基本的なデータ型

38 ２．５　データ構造 CAR CDR ’B’ 1 ’A’ 2 リスト構造 [’A’, 2, ’B’, 1]

39 ２．５ データ構造 -2.14 ’B’ スタック 1024 ’A’ スタックポインタ スタックサイズの上限が決まって
２．５　データ構造 -2.14 ’B’ 1024 ’A’ スタック スタックポインタ スタックサイズの上限が決まって いれば，その大きさの配列を使い 実現可能

40 ２．６ 演算子 算術演算子 演算子+, -, *, /, **（または^）が有名 演算子-は，単項にも２項にも用いられる．
２．６　演算子 算術演算子 演算子+, -, *, /, **（または^）が有名 演算子-は，単項にも２項にも用いられる． 単項演算子→前置または後置 　言語Cでは，++は前置，後置いずれにも使用可 X=++Y;　→　Y=Y+1; X=Y; X=Y++;　→　X=Y; Y=Y+1; ２項演算子→前置，中置，または後置

41 ２．６ 演算子 算術式 データ参照は式 +を２項中置演算子，E1, E2を式 ⇒ E1 + E2は式 +を単項前置演算子，Eを式
２．６　演算子 算術式 データ参照は式 +を２項中置演算子，E1, E2を式 　⇒　E1 + E2は式 +を単項前置演算子，Eを式 　⇒　+ Eは式 +を単項後置演算子，Eを式 　⇒　E +は式 Eを式 　⇒　(E)は式

42 ２．６ 演算子 関係演算子 ２項演算子 論理値（たとえばtrueやfalse）を返す
２．６　演算子 関係演算子 ２項演算子 論理値（たとえばtrueやfalse）を返す 代表的なものに<=, <, =, <>, >=, >がある

43 ２．６　演算子 論理演算子 論理値をもつ引数，論理値を返す． 論理積and 論理和or 論理否定not 排他的論理和xor（またはeor）

44 ２．６　演算子 文字列演算子 文字列を対象とする． 連接 　”abcd” + ”efg”　⇒　”abcdefg” 部分列の取り出し パタン照合

45 ２．６ 演算子 結合性と順位 左結合的 右結合的 a+b+c → (a+b)+cか， a+(b+c)か？
２．６　演算子 左結合的 右結合的 結合性と順位 a+b+c　→ (a+b)+cか，　a+(b+c)か？ a+b**c　で，+は左結合的で　**は右結合的 　a+b**c　→　(a+b)**cか，　a+(b**c)か？ +の順位＞**の順位 +の順位＜**の順位

46 ２．６ 演算子 演算子の優先順位 単項演算子 ALGOL FORTRAN PI/I ^ ** ** + - + - * /
２．６　演算子 単項演算子 演算子の優先順位 ALGOL FORTRAN PI/I ^ ** ** + - + - * / < = > < = > .LT. .EQ. .GT. || .LE. .NE. .GE. < = > <= >= .NOT. < = > .AND. & .OR. |

47 ２．６ 演算子 演算子の代数的性質 可換則 x + y = y + x a + b * c = b * c + a
２．６　演算子 演算子の代数的性質 可換則 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

48 ２．６ 演算子 その他の演算子（代入以外） 条件式：ALGOLのif A then B else CやCの
２．６　演算子 その他の演算子（代入以外） 条件式：ALGOLのif A then B else CやCの 　A ? B : Cなど．これは３項演算子 選択子：配列の添字付け，レコード構造の欄名の 　指定 A[1,2,i] 変項演算子あるいは多項演算子

49 ２．６ 演算子 型強制 異なる型の引数をとりうる演算子：Aが整数型で， Bが実数型のとき，A+Bの結果の型は？
２．６　演算子 型強制 異なる型の引数をとりうる演算子：Aが整数型で， 　Bが実数型のとき，A+Bの結果の型は？ 暗黙の型変換：Aを実数型に変換してから加算を 　実行するようなコードを生成

50 ２．６ 演算子 演算子の実現 多くの演算子→機械命令 算術演算子や論理演算子などの多くの演算子 関係演算子→比較命令＆条件分岐命令
２．６　演算子 演算子の実現 多くの演算子→機械命令 　算術演算子や論理演算子などの多くの演算子 関係演算子→比較命令＆条件分岐命令 その他→機械命令列やサブルーチン

51 よい連休を