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. Sethi, J. D. Ullman. Compilers: Principles, Techniques and Tools", ddison-wesley, 1985.V. エイホ, R. セシィ, J.D. ウルマン. " I, II - 原理技法ツール -." サイエンス社, V. ho, M.S. Lam, R. Sethi, J.D. Ullman. "Compilers: Principles, Techniques, & Tools," ddison-wesley, 参考書 ( 実際的 ) 石田綾, スモールの製作で学ぶプログラムのしくみ, 技術評論社, 日向俊二, やさしいの作り方入門, カットシステム, 前橋和弥, プログラミング言語を作る, 技術評論社, 青木峰郎, ふつうのをつくろう, ソフトバンククリエイティブ, 原悠, Ruby で作る奇妙なプログラミング言語, 毎日コミュニケーションズ, Terence Parr, Language Implementation Patterns, Pragmatic Bookshelf, 採点レポート 2 回 ~ 内容方法は未定 1

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

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

3 FORTRN I 史上初の手で書いたものと殆どおなじくらい良いコード計算機科学に与えた影響はあまりに大きい膨大な理論的研究を生み出すもととなった現代のはいずれも FORTRN I の概要は持っている FORTRN II C RE OF TRINGLE WITH STNDRD SQURE ROOT FUNCTION C INPUT - CRD REDER UNIT 5, INTEGER INPUT C OUTPUT - LINE PRINTER UNIT 6, REL OUTPUT C INPUT ERROR DISPLY ERROR OUTPUT CODE 1 IN JOB CONTROL LISTING RED INPUT TPE 5, 501, I, IB, IC 501 FORMT (3I5) C I, IB, ND IC MY NOT BE NEGTIVE C FURTHERMORE, THE SUM OF TWO SIDES OF TRINGLE C IS GRETER THN THE THIRD SIDE, SO WE CHECK FOR THT, TOO IF (I) 777, 777, IF (IB) 777, 777, IF (IC) 777, 777, IF (IIB-IC) 777,777, IF (IIC-IB) 777,777, IF (IBIC-I) 777,777, STOP 1 C USING HERON'S FORMUL WE CLCULTE THE C RE OF THE TRINGLE 799 S = FLOTF (I IB IC) / 2.0 RE = SQRT( S * (S - FLOTF(I)) * (S - FLOTF(IB)) * (S - FLOTF(IC))) WRITE OUTPUT TPE 6, 601, I, IB, IC, RE 601 FORMT (4H =,I5,5H B=,I5,5H C=,I5,8H RE=,F10.2, 13H SQURE UNITS) STOP END 注 : 等幅フォントで表示する必要がありますの目的必要性は, 現代では, 自明. 高級言語 (C, Java,... ) コンパイルの過程は大きく 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! ソースプログラムを解析してを生成するソースプログラムエラーメッセージ言語 L1 で書いたプログラム絶対番地で書かれた機械語リロケータブルな機械語アセンブリ言語で書かれたプログラム他のプログラム言語で書かれたプログラムリンカー 3

4 4 アセンブリ言語への翻訳言語 L1 で書いたプログラムアセンブリ言語で書いたプログラムアセンブラリンカー T 図式トランスレータの機能の図式表現 L2 L3 L1 L 様々な技術直接開発ブートストラップクロス仮想マシン Just-in-time ブートストラップ P L L P アセンブリ言語での実装を避けるには? クロス機種非依存あるプラットホーム上で走って他のプラットホーム用のコードを生成する機種非依存可搬型仮想マシンソースコードバイトコード結果インタープリタデータ

Just-in-time コンパイルのフェーズソースコードバイトコードデータ JIT- 実行コンパイルのフェーズ ( おおまか ): 字句解析 lexical analysis 構文解析 syntax analysis 意味解析 semantic analysis 最適化 optimization コード生成 code generation 結果バイト

5 Just-in-time コンパイルのフェーズソースコードバイトコードデータ JIT- 実行コンパイルのフェーズ ( おおまか ): 字句解析 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 意味解析コード最適化 = id1 id2 id3 * 30 temp1 = int_to_real(30) temp2 = id3*temp1 temp3 = id2 temp2 id1 = temp3 意味解析 = 最適化 id1 id2 id3 * int_to_real temp1 = id3* 30.0 id1 = id2 temp1 30 5

6 コード生成 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 コード生成 MOVF id3, R2 MULF #60.0, R2 MOVF id2, R1 DDF R2, R1 MOVF R1, id1 フロントエンドとバックエンドパスコンパイルのフェーズでソース言語の方に ( ターゲット言語へと比べて ) より近いフェーズをフロントエンド (front-end) と呼ぶコンパイルのフェーズでターゲット言語の方に ( ソース言語へと比べて ) より近いフェーズをバックエンド (back-end) と呼ぶ一回のパスというのはの動作で ( 多くの場合ソース ) コード全部を対象に処理することフロントエンドのコンポーネント化字句解析 ( スキャナ ) 構文解析 ( パーザー ) 意味解析言語 -1 のソースプログラム言語 -1 のフロントエンド言語 -2 のソースプログラム言語 -2 のフロントエンド属性付きの ST (bstract Syntax Tree) 中間コード生成フロントエンド最適化されていない中間コード中間コードの最適化最適化された中間コードターゲット-1 のコード生成器ターゲット-2 のコード生成器 r エラーメッセージ最適化されていない中間コードターゲット -1 の機械語ターゲット -2 の機械語 6

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

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