第 5 章 フロントエンドの作成 [ variable—declaration—list ] 35 36 37 39 40 43 44 45 46 47 48 50 52 53 54 55 56 60 62 63 64 66 68 69 70 72 73 74 77 78 79 80 58 38 variable—declaration—list { variable—declaration } 42 variable—declaration " int" identifier statement_list { statement } statement expression—statement ー jump—statement expression—statement assignment—expression jump—statement assignment_expression assignment_expression identifier additive—expression ー additive—expression additive—expression statement—list multiplicative_expression multiplicative—expression multiplicative—expression } ] multiplicative—expression postfix—expression postfix—expression pnmary—expressxon ー identifier postfix—expression assignment—expression ー postfix—expression } ] assignment—expresstion } ]

5.5 構文解析 return NULL ー assignment-expression は代入文の解析なので、左辺値となる識別子 ( 変数名 ) が現れます。構文解析 では意味的な部分はチェックしないので、正しい位置に識別子が出現することの確認のみを行い、それが 変数として宣言されているかの確認は行いません。 最後は primary_expression を解析する visitPrimaryExpression です。 primary—expression の構文図 は図 5.6 のようになります。 prlma 「 y_expresslon identifier intege 「 additive_exp 「 ession ■図 5.6 primary-expression の構文図 primary-expression は式の基本構成要素に関する規則で、識別子や数値、 ( ) で囲まれた式を受け入 れます。構文解析時点での visitPrimaryExpression の実装例をリスト 5.19 に示します。 ・リスト 5.19 visitPrimaryExpression * PrimaryExpression 用構文解析メソッド 2 ☆ @return 解析成功時 . AST 失敗時 : NULL 3 4 BaseAST *Parser: :visitPrimaryExpression( ) { 5 / / recored index 6 int bkup=T0kens->getCur 工 ndex ( ) : 7 8 9 20 第 5 章 / /VARIABLE—工 DENTIFIER if ( Tokens->getCurType ( ) ==TOK—工 DENTIFIER ) { ・・本来ならここで変数の宣言確認・ std: : string var—name=Tokens->getCurString( ); Tokens—>getNextToken ( return new VariableAST ( var—name ); / / integer }else if (T0kens->getCurType( )==TOK—DIG 工 T) { 91

第 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

第 5 章フロントエンドの作成 何もしない AST の追加 parser クラスの各メソッドは基本的に AST を返すようにしています。こで問題となるのが、 expression-statement の解析です。まず expression-statement の構文図を図 5.9 に示します。 expression_statement assignment_exp 「 ession ■図 5.9 expression statement の構文図 図を見て明らかなとおり、 expression_statement は「 ; 」のみの文を受け入れます。「 ; 」のみの文は何もし ない文なので NULL を返したいところですが、 NULL は今回の仕様上、エラーを意味します。そこで、 こでは特別に「 ; 」を表す NullExprAST を追加することにします。先ほど構文上意味のない記号は AST から除くという話をした手前少々ますい気もしますが、今は楽にわかりやすい実装を進めたいので、少々カ 押しで対応します。リスト 5.22 のように AstID を修正し、 NullExprAST を追加しましよう。 ・リスト 5.22 AstlD の修正と NullExprAST return base—>getValueID( )==NullExpr 工 D; static inline b001 classof (BaseAST const* base ) { static inline b001 classof (NullExprAST const* ) {return true; } BaseAST(NuIIExprID) { } NuIIExprAST ( ) public: 19 class Nu11ExprAST : public BaseAST { ☆”・“を表す AST NumberID Variab1e 工 D, JumpStmt 工 D, Ca11Expr 工 D, Nu11Expr 工ら BinaryExprID ′ Variab1eDec1 工 D, Base 工 D ′ enum AstID { * AST の種類 96 24 23 22 20 17 12 1 1 1 0 9 8 7 6 5 4 3 2

第 5 章フロントエンドの作成 visitPostfixExpression には関数呼び出しの解析が含まれます。意味的な部分を確認するのであれば、 もしくは定義された関数名であるか確認すべきですし、関数呼び出しの引数の 12 行目の識別子が宣言、 数が関数の宣言もしくは定義とあっているかどうかの確認も必要です。しかし、これまで同様に意味解析 は今は実装しないので、これらの処理は未実装とします。 四則演算の解析 次は四則演算の解析です。これは構文規則どおりに実装すればよい部分ではありますが、少々ややこ しいのでコードを載せて説明しておきます。なお、四則演算の解析メソッドは visitAdditiveExpression と visitMultiplicativeExpression に分かれますが、基本的に同様の処理を行うため、ここでは visitAdditive ーーー・一・一 - ー - 十・ multiplicative_exp 「 ession additive_exp 「 ession Expression についてのみ説明します。ます図 5.8 に additive-expression の構文図を示します。 十 ・図 5.8 additive expression の構文図 multiplicative_exp 「 ession multiplicative_expression additive-expression は加減算に関する規則で、加算および減算の繰り返しを受け入れます。 に visitAdditiveExpression の実装を示します。 ■リスト 5.21 四則演算 リスト 5.21 2 3 4 5 6 7 8 9 16 94 ま AdditiveExpression 用構文解析メソッド return NULL; if ( ! lhs ) 1hs=visitMultiplicativeExpression(NULL); if(!lhs) BaseAST *rhs; int bkup=T0kens->getCur 工 ndex ( / / bkup index BaseAST *Parser: :visitAdditiveExpression(BaseAST *lhs ) { ☆ @return 解析成功 : AST 解析失敗 : NULL ☆ @param lhs ( 左辺 ) 。初回呼び出し時は NU

第 5 章 フロントエンドの作成 int val=Tokens—>getCurNumVa1( ) : return new NumberAST ( val 房 Tokens—>getNextToken ( 房 return NULL : Tokens->getCurString( ) = } else if ( Tokens->getCurType ( ) ==TOK—SYMBOL & & / / integer ( - ) visitPrimaryExpression も、 assignment_expression と同様に 確認のみを行い、定義済みであるかの確認は行いません。 関数の宣言確認もしない 識別子が正しい場所で出現することの 構文解析では、関数呼び出し時の関数宣言の確認についても同じく実装しません。関数呼び出しの構 文解析が含まれる visitPostfixExpression の構文図と構文解析時点でのソースコード例を図 5.7 、リスト pnmary_expression postfix_exp 「 ession 5.20 に示します。 identifier assignment_expression ■図 5.7 postfix expression の構文図 ・リスト 5.20 visitPostfixExpression 2 3 4 5 6 7 8 9 9 2 ☆ PostfixExpression 用構文解析メソッド * @return 解析成功 : AST 解析失敗 : NULL BaseAST *Parser: :visitPostfixExpression( ) { / / get index int bkup=Tokens->getCur 工 ndex ( ); if ( Tokens->getCurType ( ) ==TOK—IDENT 工 F 工 ER ) { / / FUNCTION_ 工 DENTIFIER

5.5 構文解析 line—num 十十一 132 133 134 135 136 137 138 139 140 142 143 144 } / / EOF の確認 if(ifs ・ eof()){ t0kens->pushT0ken( line—num) new TOken ( token—str ′ TOK—EOF ′ / / クローズ ifs. close( return tokens ー ー 5.5 構文解析 次に構文解析を実装します。ここでは先ほど作成した TokenStream を読み込んで、 Abstract Syntax Tree( 以降 AST) を作成します。 5.5.1 AST を考える 構文解析を実装する前に、 AST の定義を行います。 AST とは抽象構文木のことで、 プログラムの意味 的に不要な部分を取り除き、木構造にしたものです。たとえば AST では、木の節に演算子が、葉には変 数や数値が当てはまります。構文解析の目的は、切り出したトークンが構文規則に則っているか確認し、 AST を作成することです。ここでは DummyC の構文規則に基づいて AST を考えます。 DummyC の構文規則では translation_unit がモジュールを表し、 translation_unit は function declaratin と function_definition によって構成されます。さらに function definition の下には variable declaration と statement カゞ並び、 statement は expression—statement と jump—statement にう上類され ます。 expression—statement はさらに「 ; 」もしくは assignment—expression に分解され、 assignment— expression には additive-expression が含まれ、・・・・・・と続きます。 これらの構文を AST にすることを考え、構成要素を C + + のクラスとして定義していきます。なお、ここ で記載する AST はあくまでも筆者の考えや好みで設計している部分も大いにあることをご承知ください。 ステートメントと工クスプレッション DummyC では、 1 つのモジュールに複数の関数が存在し、関数はステートメントの集合として表現され ます。ここでいうステートメントとは、「 ; 」で終わる一連の処理のことを指します。ここでは、ステートメント を表す AST をクラスとして定義することを目標とします。また、 DummyC でいうステートメントとは、非終 第 5 章 69

5.5 構文解析 AST の種類を表す AstID はこの時点では BaseAST を表す BaseID のみですが、今後各種 AST のク ラスを定義するごとに追加されていきます。 それでは、引き続きステートメントの AST について考えましよう。まずはステートメントの構成要素か ら考えていきます。プログラムの最小構成要素はトークンであり、予約語 (int と return) と identifier 、 integer および記号です。これは同時にステートメントの最小構成要素とも言えます。 AST として考えたと きには、「 ; 」や用、「凵などの記号は取り除くので、記号として残るのは演算子のみです。予約語はひとま す後回しにして、演算子は AST の節になるので、 identifier と integer 、つまり識別子と数値が葉ノードに なると考えられます。識別子は変数名と関数名の 2 つの可能性が考えられますが、識別子だけでは関数を 表現できないので、こではます変数から見ることにします。 というわけで、ます変数名情報を持つ VariableAST クラスと、数値情報を持つ NumberAST クラスを 定義することにしましよう。 VariabIeAST クラスと NumberAST クラスは、表 5.2 の情報をメンバ変数とし て持っことにします。 ■表 5.2 VariableAST と NumberAST のメンバ変数 VariableAST std::st 「 ing Name 変数名 数値情報 Numbe 「 AST int Val もちろんクラスとして定義する際にはこれらの変数に対する setter/getter などのメソッドを定義する必 要がありますが、こではとりあえず変数のみを掲載しています。 変数名と数値、および演算子がそろえば、二項演算および関数呼び出しが成立します。 DummyC での 一項演算としては、 assignment_expression 、 additive_expression 、 multiplicative_expression カゞありま す。これらを別々のクラスとして定義することもできますが、あまり意味はないので、すべてまとめて 1 つの クラス BinaryExprAST で表現することにします。関数呼び出しは構文規則上は postfix-expression に 記載されていますが、 CallExprAST クラスとして個別に定義することにします。 BinaryExprAST クラスと CaIIExprAST に持たせるメンバ変数を、表 5.3 に示します。 ■表 5.3 BinarExprAST と CalIExprAST のメンバ変数 BinaryExprAST クラス名 補足 メンバ変数 第 5 章 補足 メンバ変数 クラス名 演算子の文字列表現 std::string Op ニ項演算の左辺となる AST BaseAST *LHS ニ項演算の右辺となる AST BaseAST *RHS 関数名 std::string Callee std::vector<BaseAST*> Args 関数呼び出しの引数 さて、こで先ほど後回しにした予約語 (int と return) の登場です。予約語 int と変数名で variable- declaration( 変数宣言 ) を、 return と二項演算で jump-statement(return 文 ) を、それぞれ定義できます。 CallExprAST 71

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 をたどり、意味解析を行う

5.7 6 VaIue *CodeGen: :generateCa11Expression(CaIIExprAST *call_expr) { std: :vector く Va1ue*> arg_vec; BaseAST *arg; Value *arg—v; Va1ueSymb01Tab1e &vs—table = CurFunc->getVa1ueSymb01Tab1e ( 房 for ( int 土 = の if( ! (arg=ca11—expr->getArgs は ) ) ) break; return Builder->CreateCa11( Mod->getFunction(ca11—expr->getCa11ee( ) ) ′ arg—vec ′ "call—tmp" 房 / / isCa11 if(isa く Ca11ExprAST>(arg) ) arg—v=generateCa11Expression ( dyn—cast く Ca11ExprAST> ( arg ) 房 / / isBinaryExpr else if(isa<BinaryExprAST>( arg) ) { BinaryExprAST *bin—expr = dyn—cast く BinaryExprAST> ( arg ); arg—v=generateBinaryExpression ( dyn—cast く BinaryExprAST> ( arg ) if(bin—expr->getOp( ) = Variab1eAST *var= dyn—cast く Variab1eAST> ( bin—expr->getLHS ( ) ); arg—v=Bui1der->CreateLoad ( vs—table. lookup ( var->getName ( ) ) ′ "arg—val" ); / / isvar else if(isa く Variab1eAST>(arg) ) arg—v=generatevariable ( dyn—cast く Variab1eAST> ( a て 9 ) 房 / / isNumber else if( isa く NumberAST>(arg) ) { NumberAST *num=dyn—cast く NumberAST> ( arg arg—v=generateNumber ( num->getNumberVa1ue ( ) 房 arg—vec ・ push—back( arg—v); 42 } 40 39 38 37 36 35 34 33 32 30 29 28 27 26 25 24 23 22 20 10 9 8 7 5 JumpStmtAST が含む戻り値を示す AST に応じて return 文を生成します。 generateJumpStatement では return 文の生成を行います * 9 。 generateJumpStatement は、 generate 」 umpStatement コード生成 渡された return 文の生成には IRBuiIder クラスの CreateRet メソッドを使用します。 CreateRet メソッドのイン ターフェイスは次のとおりです。 * 9 一応今後の拡張で分岐命令なども考えてはいますが。 123