5.5 構文解析 if ( Tokens->getCurType ( ) ==TOK—SYMBOL & & Tokens->getCurString( ) = Tokens—>getNextToken ( rhs=visitMultiplicativeExpression (NULL 房 if ( rhs ) { return visitAdditiveExpression ( new BinaryExprAST ( " 十 " lhs ′ rhs ) }else{ SAFE—DELETE ( lhs ) : Tokens->app1yTokenIndex ( bkup ); return NULL ー }else if ( Tokens->getCurType ( ) ==TOK—SYMBOL & & Tokens->getCurString( ) = Tokens—>getNextToken ( 房 rhs=visitMultiplicativeExpression(NULL) : if ( rhs ) { return visitAdditiveExpression( new BinaryExprAST ( " lhs, rhs ) }else{ SAFE—DELETE ( lhs Tokens->app1yT0ken 工 ndex (bkup 房 return NULL ー return lhs; 第 5 章 四則演算の解析は、 visitAssignmnetExpression から visitAdditiveExpression を呼び出すことで開始 します。 visitAdditiveExpression は引数として演算の左辺値 (lhs) を受け取りますが、初回呼び出し時は NULL を指定して呼び出されます。 lhs が NULL の場合は、 visitMuItipIicativeExpression を呼び出して 左辺値を解析します。 lhs が解析できれば演算子の種類と右辺値の解析を実施します。これで該当演算の 解析自体は完了します。しかし、この演算を左辺値とする演算がさらに続く可能性があります。そのため、 この演算を表す BinaryExprAST を引数として、 visitAdditiveExpression を再帰的に呼び出します。これ により、後続の演算についても解析可能になります (visitMultiplicativeExpression についても構造は同じ なので、その説明は省略します ) 。

第 5 章 20 22 23 24 26 27 28 29 30 32 33 フロントエンドの作成 / / 工ラーメッセージを出して NULL を返す fprintf( stderr, "Function : %s is redefined" SAFE—DELETE ( proto return NULL ー ′ prot0->getName ( ) . c—str ( ) / / ( 関数名ー引数 ) のペアをプロトタイプ宣言テーブル (Map) に追加 PrototypeTab1e [ proto->getName ( ) ] =proto->getParamNum( 房 Tokens—>getNextToken ( return proto ー }else{ SAFE—DELETE ( pro セ 0 Tokens->app1yTokenIndex ( bkup return NULL ー 34 } まず visitFunctionDeclaration では、 16 行目で PrototypeTable を参照し、新しく解析した関数がすで に宣言されているかを確認しています。 17 、 18 行目では同様に FunctionTabIe を参照しており、関数が定 義済みであるか、定義済みの場合は引数の数が合っているかを確認しています。この処理によって再定義 と判断された場合はエラーメッセージを出力して NULL を返します。新規に宣言された関数の場合は、 26 行目で PrototypeTable に関数名、引数の数のペアを追加します。 続いて visitFunctionDefinition を修正します。 visitFunctionDefinition に追加したい処理は次のとおり る処理 です。 ・関数がプロトタイプ宣言されていた場合、プロトタイプ宣言と関数定義の引数の数が同一であることを確認す ・リスト 5.26 意味解析を実装した visitFunctionDefinition に示します。 これらの処理を追加したテープルを用いて実装します。修正後の visitFunctionDefinition をリスト 5.26 ・同名の関数が複数定義されていないことを確認する処理 2 3 4 5 6 7 8 9 100 * FunctionDefinition 用構文解析メソッド * @return 解析成功 : FunctionAST 解析失敗 : NULL FunctionAST *Parser: :visitFunctionDefinition( ) { int bkup=T0kens->getCurIndex ( PrototypeAST *proto=visitprototype ( ); if( !proto){ return NULL ー

5.5 構文解析 図 5.2 の構文図からもわかるとおり、 function_declaration と function_definition は関数宣言と関数 定義を示す非終端記号です。コンパイラとしては関数宣言と定義の解析において、同名の関数が再定 義されていないかのチェックを行うべきです。しかし今回はひとまず構文解析までを目的とするので、 れらの処理を行いません。これらは後述する意味解析で実装します。ですので、構文解析の段階での visitFunctionDeclaration と visitFunctionDefinition の処理はリスト 5.14 のような形になります。 ・リスト 5.14 visitFunctionDeclaration 2 3 4 5 6 7 8 9 20 22 23 ☆ FunctionDcIaration 用構文解析メソッド * @return 解析成功 : PrototypeAST 解析失敗 : NULL PrototypeAST *Parser: :visitFunctionDeclaration( ) { int bkup=Tokens->getCur 工 ndex ( PrototypeAST *proto=visitprototype ( 房 if( ! pro セ 0 ) { return NULL ー / /prototype; if ( Tokens—>getCurString ( ) = ・・本来であればここで再定義されていないか確認・・ Tokens—>getNextToken ( ) : return proto : }else{ SAFE—DELETE ( proto ); Tokens->app1yTokenIndex ( bkup ); return NULL ー ・リスト 5.15 visitFunctionDefinition 2 3 4 5 6 7 8 9 * FunctionDefinition 用構文解析メソッド ☆ @return 解析成功 : FunctionAST 解析失敗 : NULL FunctionAST *Parser: :visitFunctionDefinition( ) { int bkup=T0kens->getCur 工 ndex ( ); PrototypeAST *proto=visitprototype ( 房 if( !proto) { return NULL ー

第 5 章フロントエンドの作成 4 4 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 / / 最後の Statement が jump—statement であるか確認 if( ! last—stmt Ⅱ ! isa く JumpStmtAST>( last—stmt) ) { SAFE—DELETE ( func—stmt 房 Tokens->app1yT0kenIndex ( bkup return NULL; if(Tokens->getCurString( ) = Tokens—>getNextToken ( return func_stmt ー }else{ SAFE—DELETE ( func—stmt ) : Tokens->app1yT0ken 工 ndex ( bkup ) : return NULL; 23 行目での find 関数で、 VariabIeTabIe に新しく読み取った変数宣言の変数名が登録されているか確認 しています。 VariabIeTabIe は解析中の関数の変数名を登録しておくべクタなので、この処理で変数が二重 宣言されないようにしています。変数名に重複があった場合は NULL を返し、そうでなければ 30 行目で VariableTable に読み取った変数名を追加します。 次に、意味解析を実装した visitAssignmentExpression はリスト 5.29 のようになります。 ■リスト 5.29 意味解析を実装した visitAssignmentExpression ☆ AssignmentExpression 用構文解析メソッド 2 ☆ @return 解析成功 : AST 解析失敗 : NULL 3 4 BaseAST *Parser: :visitAssignmentExpression( ) { 5 int bkup=Tokens->getCurIndex ( 6 7 8 9 20 BaseAST * lh if (Tokens->getCurType( )==TOK—IDENT 工 FIER) { / / 変数が宣言されているか確認 if( std: :find(Variab1eTabIe. begin( ) ′ Variab1eTab1e. end( ) ′ T0kens->getCurString( ) ) Variab1eTab1e. end( ) ) { lhs=new Variab1eAST ( Tokens->getCurString ( ) ); Tokens—>getNextToken ( ); BaseAST *rhs; if ( Tokens->getCurType ( ) ==TOK—SYMBOL & & Tokens->getCurString ( ) = Tokens—>getNextToken ( if (rhs=visitAdditiveExpression(NULL) ) { return new BinaryExprAST ( " lhs, rhs ) : }else{ 104

第 5 章フロントエンドの作成 ・リスト 5.27 意味解析を実装した visitPrototype 2 3 4 5 6 7 8 9 10 1 1 ☆ prototype 用構文解析メソッド ☆ @return 解析成功 : PrototypeAST 解析失敗 : NULL PrototypeAST *Parser: :visitPrototype( ) { / / bkup index 土 n セ bkup=T0kens->getCurIndex ( 房 std: :vector く std: :string> param—list; b001 is—first—param = true; while(true) { if ( ! is—first—param & & Tokens->getCurType ( ) ==TOK—SYMBOL & & Tokens-> getCurString( ) = Tokens—>getNextToken ( ) : if ( T0kens->getCurType ( ) ==TOK—工 NT ) { Tokens->getNextToken ( ); }else{ break; if ( Tokens->getCurType ( ) ==TOK—IDENT 工 F 工 (R) { / / 引数の変数名に重複がないか確認 if(std: :find(param—list. begin(), param—list.end( ) ′ param—list ・ end( ) ) { Tokens->app1yTokenIndex ( bkup ) : return NULL; param—list ・ push—back(T0kens->getCurString( ) ) : Tokens->getNextToken ( 房 }else{ Tokens->app1yT0kenIndex ( bkup return NULL ー Tokens->getCurString( ) ) 19 行目と 20 行目の find 関数で param 」 ist ( 引数名を格納しているリスト ) に新しく読み取った識別子が 存在しないか確認しています。同名の識別子がすでに存在する場合は NULL を返し、そうでなければリ ストに識別子を追加します。この処理を行うことで、同一の引数名の出現を防いでいます。 次に、意味解析を実装した visitFunctionStatement はリスト 5.28 のようになります。 102

5.6 意味解析 また、 expression—statement の解析メソッド visitExpressionStatement をリスト 5.23 のように定義しま す。 ーリスト 5.23 visitfExpressionStatement ☆ ExpressionStatement 用構文解析メソッド 2 ☆ @return 解析成功 : AST 解析失敗 : NULL 3 4 BaseAST *Parser: :visitExpressionStatement( ) { 5 BaseAST *assign—expr; 6 7 8 9 18 return NULL ー / / NULL Expression if (Tokens->getCurString( ) = Tokens—>getNextToken ( return new NullExprAST ( 房 }else if(assign—expr=visitAssignmentExpression( ) ) { if(Tokens->getCurString( ) = Tokens—>getNextToken ( 房 return assign—expr : 第 5 章 ー 5.6 意味解析 こまでは単に構文規則に則っているかのみを見ていましたが、本節ではさらに意味解析の機能を追加 します。 5.6.1 意味解析の実装方法 意味解析の実装方法は、次の 2 つの方法があります。 ・ AST 作成時に同時に意味解析を行う ・構文解析終了後に AST をたどり、意味解析を行う

6.6 ループの繰り返し回数のカウント llvm::Lo 叩 Base::getExitingBlock は、対象の BasicBlock が複数あった場合は NULL を返します。 NULL が返された場合は繰り返し条件以外にもループを抜ける処理があるということなのでで、こでは 解析不可とします。 次に、先ほど得た BasicBIcok 内の終端命令を取得します。 BasicBIock の終端命令は getTerminator メソッドで取得できます。 Ilvm::BasicBIock::getTerminator Terminator 工 nst ☆ BasicBlock: :getTerminator ( 今回設けた条件により、取得した終端命令は br 命令であるはずなので、返された命令を dyn-cast<> テンプレートで BranchInst にキャストできるはすです。また、第 4 章で述べたように br 命令にはいくつか のフォーマットがありますが、今回の br 命令は条件文の形式になっているはずです。これは、 BranchInst クラスの isConditional メソッドで確認できます。 lIvm::BranchInst::isConditionaI b001 IIvm::Branch 工 nst::isConditional ( ) const すなわち条件文の場合は isConditional メソッドは、その BranchInst のオペランドが 3 つであれば、 true を、そうでなければ false を返します。 こまでの処理を実装した runOnLo 叩はリスト 6.20 のようになります。 ・リスト 6.20 Loop の ExitingBlOCk と終端命令の取得 1 b001 LPCountPass : : runOnLoop ( llvm: : LOOP *L, llvm: : LPPassManager &LPM ) { / / 終了プロックを取得 2 11V 爪 : :BasicB10ck *exit—block = L->getExitingB10ck( ) : 3 if ( exit—b10ck==NULL) 4 return false; 5 6 / / 終了プロックの Terminator 工 nst を取得 7 11V 爪 : :BranchInst *branch—inst 8 getTerminator ( ) ); if ( branch—inst==NULL ) return false; 第 6 章 11V Ⅲ : :dyn—cast く 11V爪: :Branch 工 nst>(exit—block—> / / conditional か確認 / / operand 数が 3 であるか確認してるだけ if ( !branch—inst->isconditional( ) ) return false; 199

5.6 意味解析 ■リスト 5.28 意味解析を実装した visitFunctionStatement * FunctionStatement 用構文解析メソッド 2 * @param 関数名、引数を格納した p て ototype クラスのインスタンス 3 * @return 解析成功 : FunctionStmtAST 解析失敗 : NULL 4 5 FunctionStmtAST *Parser : : visitFunctionStatement ( PrototypeAST * p て 0t0 ) { 6 int bkup=Tokens->getCur 工 ndex ( ); 7 8 9 new FunctionStmtAST ( 15 FunctionStmtAST *func—stmt }else if (var—dec1=visitVariab1eDec1aration( ) ) { while (var—decl) { 20 var—dec1->setDec1Type(Variab1eDec1AST: : local); / / 変数名に重複がないか確認 22 if( std: : find(VariableTab1e ・ begin( ) ′ Variab1eTab1e. end( ) ′ var—dec1->getName( ) ) 23 Variab1eTab1e. end( ) ) { 24 SAFE—DELETE ( var—decl 房 25 SAFE—DELETE ( func—stmt 房 26 return NULL; 27 28 / / 変数名テーブルに新しく読み取った変数名を追加 29 Variab1eTab1e. push—back(var—dec1->getName( ) ); 30 func—stmt->addVariab1eDec1aration ( var—decl ); var—dec1=visitVariab1eDec1aration( ) : 32 33 34 36 37 38 39 40 42 43 44 45 46 47 if(Tokens->getCurString( ) = Tokens->getNextToken ( }else{ return NULL; 第 5 章 if(stmt=visitStatement( ) ) { while( stmt) { last—stmt=stmt ー func—stmt->addStatement ( stmt ); stmt=visitStatement ( ) : / / other }else{ SAFE—DELETE ( func—stmt ) : Tokens->app1yToken 工 ndex ( bkup ); return NULL; 103

5.5 構文解析 ・・本来ならここで関数の宣言確認・・ / / 関数名取得 std: : string Ca11ee=Tokens->getCurString( ) : Tokens—>getNextToken ( ) : / / LEFT PAREN if (Tokens->getCurType( ) !=TOK—SYMBOL Ⅱ Tokens->getCurString( ) ! Tokens->app1yToken 工 ndex ( bkup ); return NULL; Tokens—>getNextToken ( ) : std: :vector く BaseAST*> args; / / 引数を解析 BaseAST *assign—expr=visitAssignmentExpression( ); if (assign—expr) { args ・ push—back(assign—expr) : " ′ " が続く限り繰り返し while ( Tokens->getCurType ( ) ==TOK—SYMBOL & & Tokens—>getCurString( ) = Tokens—>getNextToken ( ); assign—expr=visitAssignmentExpression( 房 if( assign—expr) { args ・ push—back(assign—expr); }else{ break; }//end while 第 5 章 ・・・本来ならここで引数の数を確認・・ / / R 工 GHT PALEN if ( Tokens->getCurType ( ) ==TOK—SYMBOL & & Tokens->getCurString ( ) = Tokens—>getNextToken ( 房 return new Ca11ExprAST(Ca11ee, args); }else{ for(int 土 = の i く args ・ size( i 十十 ) SAFE—DELETE ( args は ] 房 Tokens->app1yToken 工 ndex ( bkup return NULL ー }else{ return NULL : 93

第 5 章フロントエンドの作成 ment-expression の構文図を図 5.5 に示します。 assignment_exp 「 ession identifier additive_expression additive_expression ■図 5.5 assignment_expression の構文図 assignment-expression は代入文に関する生成規則です。 assignment-expression を受け入れる構文 解析メソッド、 visitAssignmentExpression の構文解析時点での実装例をリスト 5.18 に示します。 ■リスト 5.18 visitAssignmentExpression 2 3 4 5 6 7 8 9 14 20 22 23 24 25 26 27 28 29 30 32 90 ☆ AssignmentExpression 用構文解析メソッド ☆ @return 解析成功 : AST 解析失敗 : NULL BaseAST *Parser: :visitAssignmentExpression( ) { int bkup=Tokens->getCur 工 ndex ( ) : BaseAST *lhs ー if ( Tokens->getCurType ( ) ==TOK—IDENT 工 FIER ) { ・・本来はここで変数の宣言確認・ lhs=new Variab1eAST(Tokens->getCurString( ) Tokens—>getNextToken ( BaseAST *rhs; if ( Tokens->getCurType ( ) ==TOK—SYMBOL & & Tokens->getCurString ( ) = Tokens->getNextToken ( ); if (rhs=visitAdditiveExpression(NULL) ) { return new BinaryExprAST ( " lh rhs 房 }else{ SAFE—DELETE ( lhs Tokens->app1yToken 工 ndex ( bkup ); BaseAST *add—expr=visitAdditiveExpression (NULL ) : if ( add—expr ) { return add—expr ー }else{ SAFE—DELETE ( lhs ) : Tokens->app1yT0kenIndex ( bkup