Microsoft PowerPoint - 01Intro.ppt [互換モード]

Size: px

Start display at page:

Download "Microsoft PowerPoint - 01Intro.ppt [互換モード]"

ちかこまるこ
5 years ago
Views:

1 目的理論の基礎 ( 理論と実際 ) をツールを使って小さいを作りながら学ぶ櫻井彰人講義内容 1. の基礎 2. 言語理論から 3. 構文解析と Yacc 4. 再帰下降型構文解析と LR 構文解析 5. 演算子優先順位と結合性 6. 字句解析と lex 7. 意味解析と記号表 8. 制御文の翻訳 9. 関数呼び出しとメモリ管理 10. 流れ解析 11. 命令選択参考書 ( 理論寄り ) 原田賢一, 構成法, 共立出版, 1999 中田育男,, オーム社, А.V. Аho, R. ethi, J. D. Ullman. Compilers: Principles, echniques and ools", Addison-Wesley, 1985 A.V. エイホ, R. セシィ, J.D. ウルマン. " I, II - 原理技法ツール -." サイエンス社, A.V. Aho,.. Lam, R. ethi, J.D. Ullman. "Compilers: Principles, echniques, & ools," Addison-Wesley, 参考書 ( 実際的 ) 石田綾, スモールの製作で学ぶプログラムのしくみ, 技術評論社, 日向俊二, やさしいの作り方入門, カットシステム, 前橋和弥, プログラミング言語を作る, 技術評論社, 青木峰郎, ふつうのをつくろう, ソフトバンククリエイティブ, 原悠, Ruby で作る奇妙なプログラミング言語, 毎日コミュニケーションズ, erence Parr, Language Implementation Patterns, Pragmatic Bookshelf, 採点レポート 2 回 ~ 内容方法は未定 1

重ねるまとめる assembler: 組み立てる人 Assemble: 組み立てる高級 (high-level) 言語の誕生 1953 年 IB は 701 を作るプログラミングはすべてアセンブラで Ronald Reagan and Watson Laboratory's Herb Grosch at an IB 701 in 1954 http://www.columbia.

2 プログラムはどう処理されるか? 2 つの代表的方法 : スクリプト言語として蘇ったインタプリタ ( より古い, 研究は少ない ) ( より新しい, かなり広く研究されている ) インタプリタはプログラムをそのまま実行する前処理はほんの少しか殆ど行わないは徹底した前処理といえる非常に多くの場合語源 interpreter: 翻訳者 Interpret: 翻訳する compiler: まとめる人 Compile: 重ねるまとめる assembler: 組み立てる人 Assemble: 組み立てる高級 (high-level) 言語の誕生 1953 年 IB は 701 を作るプログラミングはすべてアセンブラで Ronald Reagan and Watson Laboratory's Herb Grosch at an IB 701 in プログラムの始まり von Neuman tored program のアイデアを出した人問題 : ソフトウェアコストはハードウェアコスト以上 John Backus: peedcoding インタプリタ手で書いたアセンブラより倍遅い! FORRAN I 1954 年 IB は 704 を開発 John Backus アイデア : 高級コードをアセンブラに翻訳しよう! 不可能だと考えた人は多い 1954 年 ~7 年 FORRAN I プロジェクト 1958 年には, ソフトウェアの 50% 以上が FORRAN で書かれる開発期間の大幅短縮 (2 週間 2 時間 ) メモリ容量 PB = 1024 B, 1000B B = 1024 GB, 1000GB GB = 1024 B, 1000B B = 1024 KB, 1000KB KB = 1024 B, 1000B GB = 10^9 B, 1024^3 B 2

脱線 PC-9801V (1985 ごろ ) V30/10Hz 640KB 5 インチ FDD 30~40 万円 FORRAN I 史上初の手で書いたものと殆どおなじくらい良いコード計算機科学に与えた影響はあまりに大きい膨大な理論的研究を生み出すもととなった現代のはいずれも FORRAN I の概要は持っている http://time-space.kddi.

3 脱線 PC-9801V (1985 ごろ ) V30/10Hz 640KB 5 インチ FDD 30~40 万円 FORRAN I 史上初の手で書いたものと殆どおなじくらい良いコード計算機科学に与えた影響はあまりに大きい膨大な理論的研究を生み出すもととなった現代のはいずれも FORRAN I の概要は持っている FORRAN II C AREA OF A RIANGLE WIH A ANDARD QUARE ROO FUNCION C INPU - CARD READER UNI 5, INEGER INPU C OUPU - LINE PRINER UNI 6, REAL OUPU C INPU ERROR DIPLAY ERROR OUPU CODE 1 IN JOB CONROL LIING READ INPU APE 5, 501, IA, IB, IC 501 FORA (3I5) C IA, IB, AND IC AY NO BE NEGAIVE C FURHERORE, HE U OF WO IDE OF A RIANGLE C I GREAER HAN HE HIRD IDE, O WE CHECK FOR HA, OO IF (IA) 777, 777, IF (IB) 777, 777, IF (IC) 777, 777, IF (IA+IB-IC) 777,777, IF (IA+IC-IB) 777,777, IF (IB+IC-IA) 777,777, OP 1 C UING HERON' FORULA WE CALCULAE HE C AREA OF HE RIANGLE 799 = FLOAF (IA + IB + IC) / 2.0 AREA = QR( * ( - FLOAF(IA)) * ( - FLOAF(IB)) * + ( - FLOAF(IC))) WRIE OUPU APE 6, 601, IA, IB, IC, AREA 601 FORA (4H A=,I5,5H B=,I5,5H C=,I5,8H AREA=,F10.2, + 13H QUARE UNI) OP END 注 : 等幅フォントで表示する必要がありますの目的必要性は, 現代では, 自明. 高級言語 (C,,... ) コンパイルの過程は大きく 2 つに分かれる : ソースプログラムの解析との生成 int main(int argc, char** argv) { puts("hello, world!"); }.LC0:.string "Hello, world!" main: pushl %ebp movl %esp, %ebp subl $8, %esp andl $-16, %esp subl $28, %esp pushl $.LC0 call puts leave ret インタープリタソースプログラムを解析して即座に実行してしまうソースプログラムを解析してを生成するソースコードインタープリタ実行結果ソースプログラム puts "Hello World!" Hello World! エラーメッセージエラーメッセージ 3

4 アセンブリ言語への翻訳言語 L1 で書いたプログラム絶対番地で書かれた機械語リロケータブルな機械語アセンブリ言語で書かれたプログラム他のプログラム言語で書かれたプログラムリンカー言語 L1 で書いたプログラムリンカーアセンブリ言語で書いたプログラムアセンブラ図式トランスレータの機能の図式表現 L1 L3 L2 図式原始言語で書いたプログラムを目的言語で書かれたプログラムに変換する言語 L で記述された原始言語目的言語 L A A L 図式記述言語図式図式原始プログラム ( 言語で記述 ) ( 言語 L で記述 ) 目的プログラム ( 言語で記述 ) 例 : を JBC( byte code) に変換する機械語で記述された javac f f 機能プログラム名記述言語 L f Hello. java code code javac Hello. class Bytecode Bytecode 4

5 図式 ( インタプリタの場合 ) 原始プログラム f ( 言語で記述 ) インタプリタ ( 言語 L で記述 ) 図式 ( の場合 ) 原始プログラム javac 目的プログラムインタプリタ bytecode java f インタプリタ L Hello. java code code javac Hello. class Bytecode Bytecode java 様々な技術直接開発ブートストラップクロス仮想マシン Just-in-time ブートストラップアセンブリ言語での実装を避けるには? L A L A P P A A A の作成計算機上で動く高水準言語のが欲しい必要なしかし機械語でプログラムは難しい既存の高水準言語を利用の作成計算機上で動く高水準言語のが欲しい計算機上で動く高水準言語のを利用作成する既存の目的のの作成は高水準言語で行える 5

クロス機種非依存仮想マシンあるプラットホーム上で走って他のプラットホーム用のコードを生成する機種非依存可搬型ソースコードバイトコードインタープリタデータ結果 Just-in-time コンパイルのフェーズソースコードバイトコードデータ JI- 実行コンパイルのフェーズ ( おおまか ): 字句解析 lexical analysis 構文解析 syntax

6 クロス機種非依存仮想マシンあるプラットホーム上で走って他のプラットホーム用のコードを生成する機種非依存可搬型ソースコードバイトコードインタープリタデータ結果 Just-in-time コンパイルのフェーズソースコードバイトコードデータ JI- 実行コンパイルのフェーズ ( おおまか ): 字句解析 lexical analysis 構文解析 syntax analysis 意味解析 semantic analysis 最適化 optimization コード生成 code generation 結果バイトコードを実行時に動的に機械語に変換 ( コンパイル ) する字句解析構文解析 id1 = id2 + id3*30; tomorrow = today + rate*30; 構文解析字句解析 = id1 = id2 + id3*30; id1 id2 + * id3 30 6

7 意味解析 id1 = id2 + id3 * 30 コード最適化 temp1 = int_to_real(30) temp2 = id3*temp1 temp3 = id2 + temp2 id1 = temp3 id1 意味解析 = + id2 id3 * int_to_real 30 最適化 temp1 = id3* 30.0 id1 = id2 + temp1 コード生成 temp1 = id3* 60.0 id1 = id2 + temp1 コード生成 loada id3 loadbi 60. mul store temp loada id2 loaddb temp add store id1 position := initial + rate * 60 字句解析 id 1 := id 2 + id 3 * 60 構文解析 := id 1 + id 2 * id 3 60 意味解析 := id 1 + id 2 * id 3 inttoreal 60 のフェーズ中間コード生成 temp1 := inttoreal (60) temp2 := id 3 * temp1 temp3 := id 2 + temp2 id1 := temp3 コード最適化 temp1 := id 3 * 60.0 id1 := id 2 + temp1 コード生成 OVF id3, R2 ULF #60.0, R2 OVF id2, R1 ADDF R2, R1 OVF R1, id1 フロントエンドとバックエンドパスコンパイルのフェーズでソース言語の方に ( ターゲット言語へと比べて ) より近いフェーズをフロントエンド (front-end) と呼ぶコンパイルのフェーズでターゲット言語の方に ( ソース言語へと比べて ) より近いフェーズをバックエンド (back-end) と呼ぶ一回のパスというのはの動作で ( 多くの場合ソース ) コード全部を対象に処理すること 7

8 フロントエンドのコンポーネント化字句解析 ( スキャナ ) + 構文解析 ( パーザー ) + 意味解析言語 -1 のソースプログラム言語 -1 のフロントエンド言語 -2 のソースプログラム言語 -2 のフロントエンド属性付きの A (Abstract yntax ree) 中間コード生成フロントエンド最適化されていない中間コード中間コードの最適化最適化された中間コードターゲット-1 のコード生成器ターゲット-2 のコード生成器 r エラーメッセージ最適化されていない中間コードターゲット -1 の機械語ターゲット -2 の機械語中間言語を用いることのよさ 1. リターゲッティング新規の機械用のを作るとき既存のフロントエンドに新規のコード生成器を作る. 2. 最適化コード最適化部分を再利用することにより様々な言語や機械に対してを作ることができる. 注 : 中間コード, 中間言語, and 中間表現はいずれも区別なく用いられる. 8

Microsoft PowerPoint - 01intro.ppt [互換モード]

Microsoft PowerPoint - 01intro.ppt [互換モード] 目的理論の基礎 ( 理論と実際 ) をツールを使って小さいを作りながら学ぶ櫻井彰人講義内容 1. の基礎 2. 言語理論から 3. 構文解析と Yacc 4. 再帰下降型構文解析と LR 構文解析 5. 演算子優先順位と結合性 6. 字句解析と lex 7. 意味解析と記号表 8. 制御文の翻訳 9. 関数呼び出しとメモリ管理 10. 流れ解析 11. 命令選択参考書 ( 理論寄り