計算機科学実験及演習3 SW 課題6の説明 吉川・⾺馬研究室 正元修平(Shuhei Shogen) 2014/06/12 内容 • まずはじめに - 課題3, 4(, 5)までの説明は最⼩小限に留留める • 課題6の補⾜足説明 - 構⽂文⽊木とその作り⽅方 - 構⽂文⽊木の作成時における lexファイル,yaccファイルの変更更点 - 構⽂文⽊木の表⽰示⼿手法 計算機科学実験及演習3 ソフトウェア 2014/06/12 2 まずはじめに 何がしたいのかを思い出そう! 計算機科学実験及演習3 ソフトウェア 2014/06/12 3 コンパイラ • プログラミング⾔言語のソースファイルを アセンブリ⾔言語のファイルに変換するプログラム • 今回の実験では,Tiny Cのファイルを読み込んで, それをアセンブリ⾔言語に変換するプログラムを作る func int func(int x)! {! while(x > 1) {! x = x – 2;! }! return x;! } ! L1 今回作る プログラム L2 Tiny Cのファイル func.tc !GLOBAL func! !push !ebp! !mov !ebp, esp! !mov !eax, [ebp+8]! !cmp !eax, 1! !setg !a1! !movzx !eax, a1! !cmp !eax, 0! !je !L2! !mov !eax, [ebp+8]! !sub !eax, 2! !mov ![ebp+8], eax! !jmp !L1! !mov !eax, [ebp+8]! !mov !esp, ebp! !pop !ebp! !ret! アセンブリ⾔言語のファイル func.asm 計算機科学実験及演習3 ソフトウェア 2014/06/12 4 コンパイラ作成の流流れ 字句句解析 構⽂文解析 意味解析 コード⽣生成 計算機科学実験及演習3 ソフトウェア 2014/06/12 5 コンパイラ作成の流流れ 字句句解析 構⽂文解析 意味解析 コード⽣生成 計算機科学実験及演習3 ソフトウェア 2014/06/12 6 コンパイラ作成の流流れ 字句句解析 構⽂文解析 意味解析 コード⽣生成 計算機科学実験及演習3 ソフトウェア 2014/06/12 7 課題6 計算機科学実験及演習3 ソフトウェア 2014/06/12 9 課題3(または課題5)まで • yacc(bison) とlex(flex)を⽤用いて, Tiny Cの構⽂文解析器を作った - ⼊入⼒力力がTiny Cの⽂文法に合っていれば何もせず終了了 間違っていれば,”Syntax Error”を出⼒力力して停⽌止 ü 課題5ではエラーリカバリ処理理を⾏行行う - ここでバグを残すと後がつらいのでちゃんとテストしましょう… int func(int n)! {! int result;! result = 4 + n * n;! return result;! }! int func(in n)! {! int result;! result = 4 n * n;! return result! ○ × ! 計算機科学実験及演習3 ソフトウェア 2014/06/12 10 課題3(または課題5)まで • 構⽂文的に正しいかどうかを判定するだけでは, その後の意味解析・コード⽣生成が出来ない - 下記の関数funcについて,課題3の解析器でも, これが構⽂文的に正しいことを⾔言うことはできる - しかし,このままだと, 例例えば3⾏行行⽬目のresultが4, 5⾏行行⽬目のresultと同じものであることは 判定できない - コンパイラの内部でこれらの計算をするための準備が必要 int func(int n)! {! int result;! result = 4 + n * n;! return result;! }! 計算機科学実験及演習3 ソフトウェア 2014/06/12 11 構⽂文⽊木 • 今後の処理理に使うためにコンパイラが使う内部表現 - ⽊木構造を持つ • 各ノードは,⾃自⾝身がどの種類のノードかを表す値 (FUNDEF, CONSなど)と,⼦子要素へのポインタを持っている - これらはyaccファイル内の%token(または%type)部で宣⾔言すると 使えるようになる 読み込んだ ソースファイル 構⽂文⽊木 計算機科学実験及演習3 ソフトウェア 2014/06/12 12 C⾔言語で構⽂文⽊木を表現する • 構造体と共⽤用体を⽤用いる typedef struct c { /* 定数ノード */! int op;! int v;! } *constant;! ! typedef struct tk { /* トークンノード(識別子を表す) */! int op;! char *name;! } *token;! ! typedef struct tp { /* N組(今回はN=4とする) */! int op;! union nd *a[4];! } *tuple;! ! typedef union nd { /* 構文木 */! struct {! int op;! } n;! struct tp tp;! struct tk tk;! struct c c;! } *tree;! 計算機科学実験及演習3 ソフトウェア 2014/06/12 13 C⾔言語で構⽂文⽊木を表現する • 構⽂文⽊木(のノード)⽣生成⽤用の関数 /* N組生成用の関数 */! tree make_tuple(int, tree, tree, tree, tree);! ! /* トークンノード生成用の関数 */! tree make_token_node(char *);! ! /* 定数ノード生成用の関数 */! tree make_constant_node(int);! • tree型は,⽊木のノード型(nd)へのポインタ型 • これらの関数を定義する際には,mallocなどを 使ってtree型変数⽤用のメモリ領領域を確保してから, そこに適切切な値を代⼊入し, ポインタを返す必要がある 計算機科学実験及演習3 ソフトウェア 2014/06/12 14 共通の型定義/関数宣⾔言をまとめる util.h typedef struct c { /* 定数ノード */! int op;! int v;! } *constant;! … /* 省略 */! typedef union nd { /* 構文木 */! struct {! int op;! } n;! struct tp tp;! struct tk tk;! struct c c;! } *tree;! ! /* N組生成用の関数 */! tree make_tuple(int, tree, tree, tree, tree);! ! /* トークンノード生成用の関数 */! tree make_token_node(char *);! ! /* 定数ノード生成用の関数 */! tree make_constant_node(int);! kadai6.l %{! …! /* インクルードの順序に注意 */! #include “util.h”! #include “kadai6.tab.h”! %}! …! kadai6.y %{! …! #include “util.h”! %}! …! • これらの関数宣⾔言と構⽂文⽊木の型定義は, yaccファイル,lexファイルの両⽅方で使うので, ヘッダファイルにまとめて書いてからインクルードするとよい - 必要に応じてインクルードガードを⾏行行う 計算機科学実験及演習3 ソフトウェア 2014/06/12 15 構⽂文⽊木のイメージ ノードの種類を表す (CONS, FUNDEFなども可) ⼦子が存在しない時は NULLを⼊入れる tree make_tuple(‘+’, tree, tree, NULL, NULL)! N組を返す 定数ノードを 返す N組を返す tree make_constant_node(4)! tree make_tuple(‘*’, tree, tree, NULL, NULL)! トークン ノードを返す tree make_token_node(“n”)! トークン ノードを返す tree make_token_node(“n”)! • tree型はN組,トークンノード,定数ノード のすべて(へのポインタ)を表現することが できることに注意 計算機科学実験及演習3 ソフトウェア 2014/06/12 16 yaccファイルにおけるアクションの記述 • $$: 構⽂文規則の左辺の式に対応する構⽂文⽊木を記述 • $n: ルールのn番⽬目の終端/⾮非終端記号の値に 対応する構⽂文⽊木を記述 add_expr:! mult_expr! { $$ = $1; }! /* mult_exprに対応する構文木を(そのまま)add_exprに渡す */! | add_expr ‘+’ mult_expr! { $$ = make_tuple(‘+’, $1, $3, NULL, NULL); }! /* add_exprとmult_exprに対応する構文木についてN組を作ってadd_exprに渡す */! | add_expr ‘-’ mult_expr! { $$ = make_tuple(‘-’, $1, $3, NULL, NULL); }! /* 同上 */! ;! 計算機科学実験及演習3 ソフトウェア 2014/06/12 17 終端/⾮非終端記号の扱い • ⼤大域変数yylval: 終端記号の値に相当 • yaccファイルにおける$$, $nなどの変数 - これらはデフォルトだとint型 • 構⽂文⽊木を作る際には, 終端/⾮非終端記号の値としてtree型を扱う必要がある • 2種類の対応策 1. マクロYYSTYPEを再定義し,記号をtree型にする 2. %union宣⾔言によって,記号が複数の型を持てるようにする 計算機科学実験及演習3 ソフトウェア 2014/06/12 18 YYSTYPEの再定義 yaccファイル %{! …! #define YYSTYPE tree /* 記号の型をtree型にする */! …! }%! …! primary_expr:! Identifier! { $$ = $1; } ! | Integer! { $$ = $1; }! | ‘(‘ expression ‘)’! { $$ = $2; }! ;! …! • 記号の型は,葉葉/⾮非葉葉ノードともにtree型となる 計算機科学実験及演習3 ソフトウェア 2014/06/12 19 YYSTYPEの再定義 lexファイル %{! …! #define YYSTYPE tree /* 記号の型をtree型にする */! …! }%! …! {識別子を表す正規表現} {! yylval = make_token_node(strdup(yytext)); ! return Identifier;! }! ! {定数を表す正規表現} {! yylval = make_constant_node(atoi(yytext));! return Integer;! }! …! • lexファイル側で トークンノードと定数ノードを作り,yylvalに代⼊入 計算機科学実験及演習3 ソフトウェア 2014/06/12 20 %union宣⾔言による記号の複数型対応 yaccファイル /* YYSTYPEの再定義は不要 */! …! %union {! int i;! char *str;! tree n;! }! %token <i> Integer /* Integerは整数 */! %token <str> Identifier /* Identifierは文字列 */! %token INT …! %type <n> add_expr mult_expr … /* 構文木の非葉ノードはtree型*/! …! primary_expr:! Identifier! { $$ = make_token_node($1); } /* make_token_nodeの引数$1はchar*型 */! | Integer! { $$ = make_constant_node($1); } /* make_constant_nodeの引数$1はint型 */! | ‘(‘ expression ‘)’! { $$ = $2; }! ;! …! • 記号の型として,int型,char*型,tree型のすべてが認められる • %union宣⾔言した時は,⼀一部の記号の型を宣⾔言しておく必要がある 計算機科学実験及演習3 ソフトウェア 2014/06/12 21 %union宣⾔言による記号の複数型対応 lexファイル …! {識別子を表す正規表現} {! yylval.str = strdup(yytext); /* yylvalに文字列を代入 */! return Identifier;! }! ! {定数を表す正規表現} {! yylval.i = atoi(yytext); /* yylvalに整数を代入 */! return Integer;! }! …! • ⽂文字列列の代⼊入に関数strdupを使うことで, 別のトークンを読み込んでyytextの値が更更新されても, 元の(正しい)⽂文字列列を代⼊入することができる - 直接yytextの値を代⼊入すると,yylvalの値がおかしくなる 計算機科学実験及演習3 ソフトウェア 2014/06/12 22 構⽂文⽊木の表⽰示 • 構⽂文⽊木が正しく出来ているかの確認 ((int gcd) ((int a) (int b))! (! (IF (== a b)! (RETURN a)! (IF (> a b)! (RETURN (FCALL gcd (- a b) b))! (RETURN (FCALL gcd a (- b a)))! }! }! }}! • スペース・インデント等は気にしなくてよい 計算機科学実験及演習3 ソフトウェア 2014/06/12 23 構⽂文⽊木の表⽰示 …! main:! program ! { if(yynerrs == 0) print_program($1); }! /* 構文解析が終了し,エラーがない場合に構文木を表示する(引数$1は生成された構文木を表す) */! ;! program:! external_declaration { $$ = $1; }! | program external_declaration { $$ = make_tuple(CONS, $1, $2, NULL, NULL); }! ;! …! }! …! %%! …! /* print_programなどのプロトタイプ宣言は,別のヘッダファイルなどでするとよい */! …! /* 根から順に構文木をたどり,その中身を表示していく関数print_program */! void print_program(tree p) {! if(p->n.op != CONS) { /* 構文木pのop(トークンの種類)がCONSでない(つまり1番目の生成規則)なら */! print_external_declaration(p); /* 非終端記号external_declarationに対応する構文木表示用の関数を実行 */! printf(“\n”);! } else { /* opがCONS(2番目の生成規則)なら */! print_program(p->tp.a[0]); /* 構文木pの1番目の子要素について,もう一度print_programを実行 */ ! print_external_declaration(p->tp.a[1]); /* pの2番目の子要素について,print_external_declarationを実行 */! printf(“\n”);! }! }! /* 以下,関数print_external_declarationなどの定義が続く */! …! 計算機科学実験及演習3 ソフトウェア 2014/06/12 24 構⽂文⽊木の表⽰示 • どの構⽂文が適⽤用されたかわかるような 構⽂文⽊木にすること - わかりやすい⾮非葉葉ノードの命名を⼼心がける - 複数の⾮非葉葉ノードでCONSを使うことを避ける • 変数へのアクセス⽅方法に気をつける - tree型は共⽤用体へのポインタ型 - 不不正なメモリ領領域へのアクセス (セグメンテーション違反)に注意 計算機科学実験及演習3 ソフトウェア 2014/06/12 25 まとめ • 構⽂文⽊木を実装する • 実装した構⽂文⽊木を表⽰示する • 早め早めの開発を⼼心がける - 後になればなるほど〆切切が苦しくなる - わからない所があれば,教員・TAに聞いてください 計算機科学実験及演習3 ソフトウェア 2014/06/12 26
© Copyright 2024 ExpyDoc