プログラミング言語処理系論 (4) Design and Implementation of Programming Language Processors

Transcription

1 プログラミング言語処理系論 (6) Design and Implementation of Programming Language Processors 佐藤周行 ( 情報基盤センター / 電気系専攻融合情報学コース )

2 の残業から Perl の吐き出すコードをながめてみる Parser Kit 中の vcc6.y をながめてみる 文法定義 パースツリーの格納 実行

3 fact.pl sub factorial { $r = 1; } while ($i>0) { $r = $r * $i; $i = $i-1; } return $r; $i = 7; print factorial();

4 $ perl -MO=Concise,factorial,-src fact.pl main::factorial: t <1> leavesub[1 ref] K/REFC,1 ->(end) - <@> lineseq KP ->t # 3: $r = 1; 1 <;> nextstate(main 1 fact.pl:3) v:{ ->2 4 <2> sassign vks/2 ->5 2 <$> const[iv 1] s ->3 - <1> ex-rv2sv skrm*/1 ->4 3 <#> gvsv[*r] s ->4 # 5: while ($i>0) { 5 <;> nextstate(main 3 fact.pl:5) v:{ ->6

5 o <2> leaveloop vkp/2 ->p 6 <{> enterloop(next->j last->o redo->7) v ->k - <1> null vk/1 ->o n < > and(other->7) vk/1 ->o m <2> gt sk/2 ->n - <1> ex-rv2sv sk/1 ->l k <#> gvsv[*i] s ->l l <$> const[iv 0] s ->m - <@> lineseq vkp ->- # 6: $r = $r * $i; 7 <;> nextstate(main 1 fact.pl:6) v:{ ->8 c <2> sassign vks/2 ->d

6 a <2> multiply[t6] sk/2 ->b - <1> ex-rv2sv sk/1 ->9 8 <#> gvsv[*r] s ->9 - <1> ex-rv2sv sk/1 ->a 9 <#> gvsv[*i] s ->a - <1> ex-rv2sv skrm*/1 ->c b <#> gvsv[*r] s ->c # 7: $i = $i-1; d <;> nextstate(main 1 fact.pl:7) v:{ ->e i <2> sassign vks/2 ->j g <2> subtract[t9] sk/2 ->h - <1> ex-rv2sv sk/1 ->f

7 e <#> gvsv[*i] s ->f f <$> const[iv 1] s ->g - <1> ex-rv2sv skrm*/1 ->i h <#> gvsv[*i] s ->i j <0> unstack v ->k # 9: return $r; p <;> nextstate(main 3 fact.pl:9) v:{ ->q s <@> return K ->t q <0> pushmark s ->r - <1> ex-rv2sv sk/1 ->s r <#> gvsv[*r] s ->s

8 Perl の Parse Tree Perl は コードセグメントはほぼ Parse Tree 実行のための最小限のヒープ スタックが用意されている B::Concise で内容を見ることができる

9 Perl の実行について ( 課題 5) Perl の B::Concise モジュールを利用して 以下についてレポートせよ (1) 適当なプログラムに対してのソースとパース木の対応 (-src) の観察 (2) 実行に際して必要となるデータ構造 ( スタック フレーム ヒープ ) の特定 (3) ループ構造を必ず含むこと

10 Perl をみると 実行まで案外簡単に見通せることがわかるので vcc6 を見てみましょう

11 課題 6 自分でプログラミング言語を定義せよ 仕様を書け そのプログラミング言語の Parser を与えよ そのプログラミング言語で書いたプログラムを評価するプログラムを書け Interpreter + 仮想マシン Compiler + 仮想マシン or ネイティブマシン

12 仕様 プログラミング言語を定義したら 仕様にまとめてみる これができない人が プログラミング言語を定義するときに必要な要素は大体以下の通り プログラム全体の構造 制御構造 データオブジェクト 式 関数 ( 手続き ) の扱い 変数のバインディング

13 では ごく簡単な例を見てみましょう P.pdf

14 今回触れないこと 処理の一単位となる トークン をうまく切り分ける必要があるので yylex はまじめにかきましょう パース時のエラー処理 非常に重要なことはわかるのだが

15 その他大切なこと : パス Def. Pass ソースプログラム ( および中間生成物 ) を処理する一単位 Def. One-Pass パス一つ ( パースを終了させるまで ) でコード生成まで済ませる Def. Multi-Pass 複数のパスから構成されるもの 一般的にはパースをした後で 解析 ( 最適化等 ) をするパスを追加する

16 複数パスの表現 ソースファイル中での表現 Node *Entry; main(int ac, char **av) { if (ac >= 2){ if (!strcmp(*++av, "-d")) debug = 1; } code = yyparse(); if (!code) exit(1); nextpass(entry); } Top: {Entry = }; /* 最初か最後に 後々の 処理のエントリーポイントを設定しておく */

17 パスの考え方 近年の考え方では パースまでと パース以後の最適化をわけています パースまででできることは高が知れていると認識が一般的になりました 最適化ルーチン インタラクティブな言語では パースまでの処理と それ以後の処理 ( 最適化等 ) のバランスが問題になっています

18 今回のテーマ 関数の実現について

19 プログラミング言語への進化 ( 復習 ) コンパイラシステムの構築 仮想マシンとマシン上の機械語の定義 仮想マシン上での実行 変数の導入 制御構文の導入 ( 複文, if, while, ) 関数の導入 (function def/call)

20 関数の出現 関数の出現につれて考えなければならない問題 コードセグメントの管理 フレームの管理 ローカル変数 グローバル変数 スコープの管理 引数の渡し方

21 変数のバインディング ( 課題 7) 変数の扱いについて 以下の点から考察し 自作の言語または vcc6 のコードを改良せよ (a) 関数には引数を渡せないのか? (b) 引数が渡されると 変数名とデータの対応がどのように変更されるか また 関数からリターンするとき どのような処理が必要か? ( ヒントキーワード : 環境 スコープ )

22 関数コールについて 呼び出し側と呼び出される側がどのように引数 ( 実引数と仮引数 ) の対応を取るかはデザイン上の問題の一つである 例えば perl では sub perr { my ($a,$b) スタック上に $a, $b の場所を確保し 大域変数 _ の値 ( 可変長 ) を 流し込む

23 一般のプログラミング言語 対象となるアーキテクチャによって大きく変わる Java on Java VM と C on ネイティブなマシン環境の二つを例にとって見る

24 C の実行環境 GCC は CPU を直に実行するコードを生成する アセンブリコードを見てみる ソースコードa.c Gcc O3 (4.8.2) アセンブリコード a.s この後に リンクが入るのだが これは省略する

25 Calling convention は一般にハードウェアとしての CPU の機能ではなく 言語処理系での 約束事 スタックにつむのは Intel 系で一般的 その他では レジスタのある部分を引数を割り当てるのに使用する言語処理系が多数 IBM POWER 上のコンパイラ SPARC 上のコンパイラ

26 Calling Convention を調べるには コンパイラの内部ドキュメントをみましょう 他のコンパイラとの連携するためには Calling Convention は公開情報でなければなりません なければ探しましょう entation/doclib/iss/2013/compiler/cpp-lin/guid- 011A435D-F8D0-46D7-B973-9B704CA5B54E.htm Intel は立派です 間違っても最初からアセンブリコードを解析してはいけません で GCC だ あなたは Wikipedia を信用するか?( 結果的に正しくても )

27 以下の簡単なプログラムで実験する a(int x0, int x1, int x2) { $ cc S a.c return x0+x1*2+x2*3; } b() { return a(1,2,3); }

28 .file "a.c".text.globl _a.def _a;.scl 2;.type 32;.endef _a: LFB0:.cfi_startproc pushl %ebp.cfi_def_cfa_offset 8.cfi_offset 5, -8 movl %esp, %ebp.cfi_def_cfa_register 5

29 movl 12(%ebp), %eax leal (%eax,%eax), %edx movl 8(%ebp), %eax leal (%edx,%eax), %ecx movl 16(%ebp), %edx movl %edx, %eax

30 addl %eax, %eax addl %edx, %eax addl %ecx, %eax popl %ebp.cfi_restore 5.cfi_def_cfa 4, 4 ret

31 .cfi_endproc LFE0: _b:.globl _b.def _b;.scl 2;.type 32;.endef LFB1:

32 .cfi_startproc pushl %ebp.cfi_def_cfa_offset 8.cfi_offset 5, -8 movl %esp, %ebp.cfi_def_cfa_register 5

33 subl $12, %esp movl $3, 8(%esp) movl $2, 4(%esp) movl $1, (%esp) call _a leave.cfi_restore 5.cfi_def_cfa 4, 4 ret.cfi_endproc LFE1:.ident "GCC: (GNU) 4.8.2"

34 GCC の calling convention esp ebp Return address スタックはこちら方向に伸びる +8( 引数ここから ) 方向

35 ( 課題 8) 手近にあるコンパイラをひとつ対象にし calling convention とフレームを解析せよ この時に以下のことに注意せよ (1) コンパイラ OS CPU を明記すること (2) 解析の手法を明らかにすること (3)calling convention は 呼び出し側と呼び出される側の約束であるが そのときに呼び出される側から呼び出し側へも約束が存在することに注意せよ

36 Java の実行環境 C と同じことを Java で調べられるだろうか? Java の Calling Convention は とりあえず JNI (Java Native Interface) はここ

37 JAVA VM Heap Thread PC Thread PC VM stack VM stack frame Method Area Heap text Segment Class instance arrays Incl. Runtime Constant pool frame

38 C と同じ事を Java でしてみる ソースファイル a.java ディスアセンブルしたコード (javap c) Compiled from "a.java" class a extends java.lang.object{ a(); Code: 0: aload_0 1: invokespecial #1; //Method java/lang/object."<init>":()v 4: return int add12and13(int,int); Code: 0: iload_1 1: iload_2 2: iadd 3: ireturn }

39 Compiling Java Program int add12and13() { return addtwostatic(12, 13); } Method bipush 12 bipush 13 invokestatic #3 ireturn

40 ( 課題 9) 実行環境としてスタックを用いたフレームを作りたい (1) 関数からのリターン情報を含む関数実行のためのフレームを設計せよ (2)Calling Convention を一つ定めよ 特に 引数へのアクセス方法を与えよ [ これで言語設計は一段落!]