コンパイラ資料 ４章　記号表 改訂１版（2014.5.20）

記号表とその利用 記号表は、意味解析（ASTを処理するフェーズ）において、識別子（ID）に関する情報を記録・保持する。特に インタプリタ（解釈器）では値 コンパイラでは型（次章）と配置（？章） 処理対象となる式の例： 2 + x * x 本章では意味解析の一種であるインタプリタの作成を通じてＡＳＴの処理と記号表の使い方をみていく。

意味解析と記号表 意味解析 記号表 インタプリタ 解釈 トークン AST 字句解析 構文解析 コンパイラ 型検査 属性 中間コード 値 型 配置

4,5章で取り扱う構文 kittyの構文のうち、 { int x,y; x:=3; y:=2+x*x; print y; } Statement ::= Type id (comma id)* semi | id assign Exp semi | lbrace Statement + rbrace | print Exp semi Type ::= int | bool Exp ::= 数式（前章参照） { int x,y; x:=3; 　y:=2+x*x; 　　print y; }

statementのためのAST（追加） block list<Node*> y decl assign assign print y:int x:int id num id op id list<Bucket*> x 3 y + y { int x,y; x:=3; 　y:=2+x*x; 　　print y; } num op 2 * id id x x

ノードクラスの階層 ProgramNode ArgsNode FunNode BlockNode NodeWithNodeList WhileNode IfNode Node NodeWithChildren PrintNode ReturnNode AssignNode DeclNode NopNode NumNode NotNode IDNode RelNode TruthNode OpNode CallNode

ASTを用いた意味解析の例：eval + * 2 x x Node::eval(void)はインタプリタにおいてＡＳＴの各ノードを 解釈する関数であり、 外部プログラムから 根ノードのメンバ関数を呼び出す。 各ノードの処理で子ノードのeval()を呼び その戻り値をもちいて 当該ノード固有の処理を行い、 結果を戻り値として返す。 int OpNode::eval(void) { int val; val　=　children[0]->eval()　+　children[1]->eval(); return val; } + 2 * x x

課題: 計算器 calc 1. numだけからなる数式の値を計算するプログラムを作成せよ。（とりあえずprint文のみで可） 2. Blockに対する処理を追加して複数のprint文が書けるようにせよ。 入力例）　 { print 2+3*3; print 3+4*4; }

値の登録とルックアップ calcの数式に変数が使えるようにする。 { int x; // declノード: x(初期値任意)登録 x:=3; //assignノード:xの値を3に更新 print x+4; //idノード: xの値を表から引く } assignの第１子もidであることに注意 （Exp中に現れるidとは役割が異なる）

記号表のインターフェース binding：変数名（string）と値（int）の組 記号表：bindingの集合 登録 void put（string name, int val） 表にbinding (name,val)を追加 更新 void set（string name, int val） ルックアップ Bucket* lookup(string name) 表中nameを変数名としてもつbindingを返す。

記号表の実装 バインディング class Bucket { string varname; int value; }; ハッシュ表 x,3 バインディング class Bucket { string varname; int value; }; ハッシュ表 list<Bucket*>* hash_table[HASH_SIZE]; Bucket* list<Bucket*> HASH_SIZE

hash関数、登録操作 unsignend hash(char* s) （K&R 日本語訳 p.175） { unsignend hashval; for (hashval =0; !*s =‘\0’;s++) hashval = *s + 31 * hashval; return hashval % HASH_SIZE; } 登録：　変数名に対するhash関数の値(hash値)をiとする 　　　　　hash_table[i]の先頭にbindingを挿入。 i i

課題： 変数つき計算器 varcalc 4ページの構文をもつStatementを実行するプログラムvarcalcを作成せよ。 入力例： { int x,y; x:=3; y:=2+x*x; print y-x; }

スコープ {（ブロックのはじめ）で{をスタックに積む。 宣言文で各変数を表に登録し、変数名とhash値の組をスタックに積む。 代入文で表の値書き込み。 }(ブロックのおわり)で{までをpopする。 変数をpopするとき hash_table[i] の先頭のbindingを削除 ただし、iは当該変数のhash値（popしたエントリから取得）

スコープ { int x,y; x:=3; y:=2+x*x; int x; x:=1; y:=x; } print y-x; x 43 { $

課題*：スコープつき計算器scopecalc スコープを実装して前ページのプログラムを実行できるようにせよ。 同一スコープ内での重複宣言を検出するにはどうしたらよいか？

課題：解釈器 interpreter varcalc(またはscopecalc)にif文、while文、print文を追加して 　　{ 　　　　int n, v; n:=10; v:=1; while(n>0){ v:=v*n; n:=n-1; } print v; 　　}

visitorパターン デザインパターンのひとつ。データとアルゴリズムを分離して、機能追加を容易かつ安全にする。 コンパイラ・ＡＳＴ処理の定番とされ、生成系でサポートされることが多い。 　　 cf. javacc/jjtree

prettyprinter(pp) / C OP + pp ID x NUM 3 ノードを引数として呼び出し 情報取得 処理 子供を引数に struct node{ int kind; int op_kind; union { int value; char varname[MAXSIZE]; struct node* children[2+1]; } attr; }; void pp(struct node* n) { indent(); switch(n->kind){ case(ID): printf(“%s\n”,n->attr.varname); break; ..... case(OP): printf(“%s\n”,op_name(n->op_kind)); pp(n->attr.children[0]); pp(n->attr.children[1]); } unindent(); ノードを引数として呼び出し OP + pp 情報取得 ID x NUM 3 処理 子供を引数に 再帰呼び出し + x 3

pp/C++/ポリモルフィズム + vtable 3 x ダイナミックディスパッチ 情報取得 OPNode struct Node { virtual void pp()=0; }; struct IDNode : public Node{ string varname; void pp() { indent(); cout<<n->varname<<“\n”; 　　　unindent(); } struct OpNode : public Node{ int op_kind; Node* children[2+1]; cout<<n->opname(op_kind)<<“\n”; child[0]->pp(); child[1]->pp(); unindent(); + オブジェクトメソッド照会 vtable virtual Node::pp()呼び出し ダイナミックディスパッチ 実メソッド呼び出し NumNode IDNode 3 　x 子供のメソッド 呼び出し + x 3 Nodeメンバ 無色 child[0]の具体的なクラスはコンパイル時は不明

PP/C++/Visitor “visitor.h” “pp_visitor.h” “node.h” “pp_visitor.cpp” struct Visitor { virtual void* visit(IDNode* n)=0; virtual void* visit(OpNode* n)=0; }; struct PPVisitor : public Visitor{ void* visit( IDNode* n); void* visit(OpNode* n); }; “node.h” class Visitor; struct Node { virtual void* accept(Visitor* v)=0; }; struct IDNode : public Node{ std::string varname; void* accept(Visitor* v); struct OpNode : public Node{ Operator op_kind; Node* children[2+1]; “pp_visitor.cpp” #include "node.h“ #include "visitor.h“ #include "pp_visitor.h“ using namespace std; void* PPVisitor::visit(IDNode* n) { indent(); cout<<n->varname<<“\n”; unindent(); }; void* PPVisitor::visit(OpNode* n) cout<<opname(n->op_kind)<<“\n”; n->children[0]->accept(this); n->children[1]->accept(this); “node.cpp” #include “node.h” #include "visitor.h“ void* IDNode::accept(Visitor* v) { return v->visit(this); } void* OpNode::accept(Visitor* v) { return v->visit(this); }

visit(IDNode*) vtable + accept vtable visit(OpNode*) vtable x accept Node::accpet(xx_visitor) visit(IDNode*) vtable Node::accpet(pp_visitor) PPVisitor OPNode depth + accept virtual virtual visit(IDNode*) visit(IDNode*) accept vtable virtual visit(OpNode*) visit(OpNode*) vtable visit(OpNode*) IDNode x virtual accept XXVisitor virtual visit(IDNode*) visit(IDNode*) virtual visit(OpNode*) visit(OpNode*)

Visitorパターンの利点と欠点 処理追加が容易で安全  機能改良が安全  ノードクラス追加は面倒 PPVisitor InterpreterVisitor 処理追加が容易で安全  処理ごとにvisitor追加（既存のノードクラス、処理(visitor)のコード変更不要・再コンパイル不要） 機能改良が安全  ノード引数別のvisitメンバ関数ごとに改良（派生クラスでメソッドオーバーライド） ノードクラス追加は面倒 基底クラスで追加ノードに該当するaccept（純粋）仮想関数追加 既存のvisitorは要再コンパイル（追加ノードに対するvisit） AST depth + virtual visit(IDNode*) virtual visit(IDNode*) visit(IDNode*) visit(IDNode*) virtual visit(OpNode*) virtual visit(OpNode*) x 3 visit(OpNode*) visit(OpNode*) PrettierPPVisitor ForNode virtual visit(IDNode*) PP2Visitor virtual visit(IDNode* n) accept virtual visit(ForNode*) visit(ForNode* n)

ポリモルフィズムとVisitorパターン 変更の種類 ポリモルフィズム Visitorパターン 処理の追加 面倒 メンバ関数追加・要再コンパイル 容易 ノードのコードは再コンパイル不要 ノードの追加 派生クラスで追加（既存ノードクラスは再コンパイル不要） 抽象クラスVisitor自体にaccept関数追加（既存Visitorの変更・再コンパイルが必要）

課題：pp_visitor visitorパターンを使ってkitty用ASTのためのpretty printerを実装せよ. ヒント：　21ページのコード(OpNode、IDNodeのみ)をもとにする 外部関数indent(),unindent(),op_name(int),main()を作成またはリンクして動作試験せよ。 構文解析でつくったAST用構造体に反映。 OpNodeは実際にはNodeWithChildrenから派生 ASTすべてのノードに対する、visitorのメンバ関数を追加