スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

F#で入門 コンパイラ 、インタプリタ編 記号表(7)

 今回は構造体(struct)を定義できる言語を作る場合の、記号表の作り方の準備として、まずは例に使う言語を一つ定義していきます。 
次をみてください。 
 
 1:struct A { 
 2:    int x; 
 3:    struct B {int y;}; 
 4:    B b; 
 5:    struct C {int z;}; 
 6:    C c; 
 7:  }; 
 
 8:void f () 
 9:{ 
10:A a; 
11:int d = a.b.y; 
12:}; 
 
 
struct A {変数定義文もしくは構造体定義文の並び} (ただし初期化はできない)という形で構造体が定義できるようになっています。 
(10行目はaが初期化されていないので、11でエラーですが、記号表の作り方のみを考察しているので、無視してください。) 
 
struct Aはメンバーとしてint型の値(x),とB型の値(b)と、C型の値(c)を持ちます。 
3,5行目のように、入れ子としてstructが定義できるようにしてあります。 
 
前回との違いはstructのスコープが追加されるということと、ドット表記の部分の参照解決になります。 
 
とりあえず、今回はトークンルール及び、文法規則を定義して、ASTに変換するところまで行きたいと思います。 
 
ではトークンルール及び、文法規則は次のようにします。 
(追加部分は右に//追加とつけてあります。) 
 
let tnR1 = 
   [("SEMI","\;"); 
    ("EQ","="); 
    ("LPAR","\("); 
    ("RPAR","\)"); 
    ("LBRA","\{"); 
    ("RBRA","\}"); 
    ("COMMA","\,"); 
    ("DOT","\.");           //追加 
    ("STRUCT","struct");    //追加 
    ("ID","[a-zA-Z][a-zA-Z0-9]*"); 
    ("NUM","0|[1-9][0-9]*") 
      ] 
 
let grammersStrLst1 = 
   ["1:Program = DeclStmts "; 
     
    "11:DeclStmts = DeclStmt SEMI DeclStmts2"; 
    "21:DeclStmts = FuncDeclStmt SEMI DeclStmts2"; 
    "26:DeclStmts = StructDeclStmt SEMI DeclStmts2"; //追加 
 
    "31:DeclStmts2  = EPSILON"; 
    "41:DeclStmts2  = DeclStmts"; 
 
    "51:DeclStmt = ID ID InitDefs"; 
    "61:InitDefs =  EPSILON"; 
    "71:InitDefs = EQ Expression"; 
    "81:Expression = ID"; 
    "91:Expression = NUM"; 
 
    "93:Expression = DotExps";       //追加 
    "96:DotExps = ID DOT Fields"     //追加 
    "97:Fields = ID"                 //追加 
    "99:Fields = ID DOT Fields"      //追加 
 
    "101:FuncDeclStmt = ID ID LPAR ArgLists RPAR LBRA BodyStmts RBRA"; 
    "111:ArgLists = EPSILON"; 
    "121:ArgLists = ID ID ArgLists2"; 
    "131:ArgLists2 = EPSILON"; 
    "141:ArgLists2 = COMMA ID ID ArgLists2"; 
  
    "151:StructDeclStmt = STRUCT ID LBRA StructMembers RBRA";//追加 
    "161:StructMembers = StructMember SEMI StructMember2";   //追加 
    "166:StructMember2 = EPSILON";                           //追加 
    "171:StructMember2 = StructMembers";                     //追加 
    "176:StructMember = ID ID";                              //追加 
    "181:StructMember = StructDeclStmt "                     //追加 
 
    "201:BodyStmts = BodyStmt SEMI BodyStmts2"; 
    "202:BodyStmts = BlockBodyStmt BodyStmts2"; 
 
    "211:BodyStmts2  = EPSILON"; 
    "221:BodyStmts2  = BodyStmts"; 
    "231:BlockBodyStmt  = LBRA BodyStmts RBRA"; 
    "241:BodyStmt  = ID ID InitDefs"; 
    "251:BodyStmt = CallFuncStmt"; 
    "261:CallFuncStmt = ID LPAR CallFuncArgLists RPAR"; 
    "271:CallFuncArgLists = EPSILON"; 
    "281:CallFuncArgLists = Expression CallFuncArgLists2"; 
    "291:CallFuncArgLists2 = EPSILON"; 
    "301:CallFuncArgLists2 = COMMA Expression CallFuncArgLists2"; 
 
    ] 
 
AST用に次のような型を定義します 
 
type PosAST0 = int*int //ソース内の位置 
 
                 
type ExpAST0 =  
     |VarExpAST0 of string * PosAST0    
     |IntExpAST0 of string * PosAST0 
     |DotExpAST0 of string * PosAST0 * list<string * PosAST0> 
                //a.x.yのa                 [x;y]        
and 
    VarDecElesAST0 = string * PosAST0 * string * PosAST0 * option<ExpAST0>  //typeName typPos varName varPos initExp 
 
and DecAST0 = 
     |VarDecAST0  of VarDecElesAST0 
     |FuncDecAST0 of string * PosAST0 * string * PosAST0 * list<string * PosAST0 * string * PosAST0> * BodyStmtAST0               
                  //funcType * functypePos *funcName funcPos list<typeName typPos varName varPos>  //実際にはBlockStmtAST0 
     |StructDecAST0 of  string * PosAST0 * list<DecAST0> 
                      //structName pos    //実際にはFuncDecAST0は使えない 
                                          //(structの中は、変数(field名)宣言とstruct定義のみ) 
and BodyStmtAST0 = 
    |VarDecStmtAST0 of VarDecElesAST0  
    |CallFuncAST0 of string * PosAST0 * list<ExpAST0> //funcName funcPos argList 
    |BlockStmtAST0 of list<BodyStmtAST0>  
     
 
ではLR1TokenizeAndParseクラスで生成される具象構文木をASTに変換する関数を定義します。 
 
let rec embodyStToAST0 (in_eb:embodyST) : list<DecAST0> = 
    match in_eb with 
    //1:Program = DeclStmts  
    |Node(1,_,dssNd::_) 
        -> embodyStToAST0 dssNd 
    //11:DeclStmts = DeclStmt SEMI DeclStmts2 
    |Node(11,_,dsNd::_::dsNd2::_) 
        -> (embodyStToAST0 dsNd) @ ( embodyStToAST0 dsNd2) 
    //21:DeclStmts = FuncDeclStmt SEMI DeclStmts2 
    |Node(21,_,fdsNd::_::dsNd2::_) 
        ->(embodyStToAST0 fdsNd) @ ( embodyStToAST0 dsNd2) 
    //26:DeclStmts = StructDeclStmt SEMI DeclStmts2 
    |Node(26,_,strcNd::_::dsNd2::_) 
        ->(embodyStToAST0 strcNd)  @ ( embodyStToAST0 dsNd2) 
    //31:DeclStmts2  = EPSILON 
    |Node(31,_,_) 
        -> [] 
    //41:DeclStmts2  = DeclStmts 
    |Node(41,_,dssNd::_) 
        ->embodyStToAST0 dssNd 
    //51:DeclStmt = ID ID InitDefs 
    //61:InitDefs =  EPSILON 
    //71:InitDefs = EQ Expression 
    |Node(51,_,Leaf(tyTkn)::Leaf(varTkn)::initNd::_) 
        ->match initNd with 
          |Node(61,_,_)  
                ->[VarDecAST0(tyTkn.Img,(tyTkn.Row,tyTkn.Col),varTkn.Img,(varTkn.Row,varTkn.Col),None)] 
          |Node(71,_,_::expNd::_)       
                ->[VarDecAST0(tyTkn.Img,(tyTkn.Row,tyTkn.Col),varTkn.Img,(varTkn.Row,varTkn.Col),Some(embodyStToExpAST0 expNd))] 
          | _ -> failwith("unoccurable error in embodyStToAST0 ") 
    //101:FuncDeclStmt = ID ID LPAR ArgLists RPAR LBRA BodyStmts RBRA 
    |Node(101,_, Leaf(tyTkn)::Leaf(funNameTkn)::_::argListNd::_::_::bodyStmtsNd::_) 
        -> [FuncDecAST0(tyTkn.Img,(tyTkn.Row,tyTkn.Col),funNameTkn.Img,(funNameTkn.Row,funNameTkn.Col), 
             embodyStToArgAST0 argListNd, BlockStmtAST0(embodyStToBodyStmtsAST0 bodyStmtsNd))]   
    //151:StructDeclStmt = STRUCT ID LBRA StructMembers RBRA 
    |Node(151,_,_::Leaf(idTkn)::_::strctMemsNode::_) 
        ->[StructDecAST0(idTkn.Img,(idTkn.Row,idTkn.Col),embodySMNToDecAST0 strctMemsNode)] 
 
    |_ ->failwith("unoccurable error in embodyStToAST0 ")   
 
and embodySMNToDecAST0 (in_eb:embodyST) :list<DecAST0> =   
    match in_eb with     
    //161:StructMembers = StructMember SEMI StructMember2 
    //166:StructMember2 = EPSILON 
    //171:StructMember2 = StructMembers 
    //176:StructMember = ID ID 
    //181:StructMember = StructDeclStmt    
    |Node(161,_,strctMemNode::_::strctMem2Node::_) 
        ->match (strctMemNode,strctMem2Node) with 
           |Node(176,_,Leaf(tyTkn)::Leaf(varTkn)::_),Node(166,_,_) 
             ->[VarDecAST0(tyTkn.Img,(tyTkn.Row,tyTkn.Col),varTkn.Img,(varTkn.Row,varTkn.Col),None)] 
           |Node(176,_,Leaf(tyTkn)::Leaf(varTkn)::_),Node(171,_,strctMemsNode::_) 
             ->(VarDecAST0(tyTkn.Img,(tyTkn.Row,tyTkn.Col),varTkn.Img,(varTkn.Row,varTkn.Col),None))::(embodySMNToDecAST0 strctMemsNode) 
           |Node(181,_,strctDclStmNode::_),Node(166,_,_) 
             ->embodyStToAST0 strctDclStmNode 
           |Node(181,_,strctDclStmNode::_),Node(171,_,strctMemsNode::_) 
             -> (embodyStToAST0 strctDclStmNode) @ (embodySMNToDecAST0 strctMemsNode) 
           | _ -> failwith("unoccurable error in embodySMNToDecAST0 ")  
    | _ -> failwith("unoccurable error in embodySMNToDecAST0 ")  
  
 
 
and embodyStToExpAST0 (in_eb:embodyST) : ExpAST0 = //expノード部分の変換を担当 
    match in_eb with 
    //81:Expression = ID 
    |Node(81,_,Leaf(idTkn)::_) 
        ->VarExpAST0(idTkn.Img,(idTkn.Row,idTkn.Col)) 
    //91:Expression = NUM 
    |Node(91,_,Leaf(numTkn)::_) 
        ->IntExpAST0(numTkn.Img,(numTkn.Row,numTkn.Col)) 
    //93:Expression = DotExps 
    |Node(93,_,dtExpNd::_) 
        ->embodyStToDotExpAST0 dtExpNd 
 
    |_ ->failwith("unoccurable error in embodyStToExpAST0 ")   
 
and embodyStToDotExpAST0 (in_eb:embodyST) : ExpAST0 = //DotExpノード部分の最初の変数部分の変換を担当 
    match in_eb with 
    //96:DotExps = ID DOT Fields  
    |Node(96,_,Leaf(idTkn1)::_::fieldsNd::_) 
        ->DotExpAST0(idTkn1.Img,(idTkn1.Row,idTkn1.Col),embodyStToDotFieldExpAST0 fieldsNd ) 
    |_ ->failwith("unoccurable error in embodyStToDotExpAST0 ") 
 
and embodyStToDotFieldExpAST0 (in_eb:embodyST) : list<string*PosAST0> = 
    match in_eb with 
    //97:Fields = ID 
    |Node(97,_,Leaf(idTkn2)::_)  
        ->[(idTkn2.Img,(idTkn2.Row,idTkn2.Col))] 
    //99:Fields = ID DOT Fields 
    |Node(99,_,Leaf(idTkn3)::_::fieldsNd::_)   
        ->(idTkn3.Img,(idTkn3.Row,idTkn3.Col))::(embodyStToDotFieldExpAST0 fieldsNd ) 
    |_ ->failwith("unoccurable error in embodyStToDotFieldExpAST0 ") 
     
 
and embodyStToArgAST0  (in_eb:embodyST) : list<string * PosAST0 * string * PosAST0> = //関数定義の引数部分の変換を担当    
    match in_eb with 
    //111:ArgLists = EPSILON 
    |Node(111,_,_) 
        ->[] 
    //121:ArgLists = ID ID ArgLists2 
    |Node(121,_,Leaf(tyTkn)::Leaf(varTkn)::argLstNd::_) 
        ->[(tyTkn.Img,(tyTkn.Row,tyTkn.Col),varTkn.Img,(varTkn.Row,varTkn.Col))] @ (embodyStToArgAST0 argLstNd) 
    //131:ArgLists2 = EPSILON 
    |Node(131,_,_) 
        -> [] 
    //141:ArgLists2 = COMMA ID ID ArgLists2 
    |Node(141,_,_::Leaf(tyTkn)::Leaf(varTkn)::argLstNd::_) 
        ->[(tyTkn.Img,(tyTkn.Row,tyTkn.Col),varTkn.Img,(varTkn.Row,varTkn.Col))] @ (embodyStToArgAST0 argLstNd) 
    |_ ->failwith("unoccurable error in embodyStToArgAST0 ")  
 
and embodyStToBodyStmtsAST0 (in_eb:embodyST) :list<BodyStmtAST0> =  
    match in_eb with 
    //201:BodyStmts = BodyStmt SEMI BodyStmts2 
    |Node(201,_,bdstmtNd::_::bdstmtsNd2::_) 
        -> (embodyStToBodyStmtUniAST0 bdstmtNd)::(embodyStToBodyStmtsAST0 bdstmtsNd2) 
    //202:BodyStmts = BlockBodyStmt BodyStmts2 
    |Node(202,_,blockstmtNd::bdstmtsNd2::_) 
        ->(embodyStToBodyStmtUniAST0 blockstmtNd)::(embodyStToBodyStmtsAST0 bdstmtsNd2) 
    //211:BodyStmts2  = EPSILON 
    |Node(211,_,_) 
        -> [] 
    //221:BodyStmts2  = BodyStmts 
    |Node(221,_,bodyStmtsNd::_) 
        -> embodyStToBodyStmtsAST0 bodyStmtsNd 
    |_ ->failwith("unoccurable error in embodyStToBodyStmtsST0 ") 
 
and embodyStToBodyStmtUniAST0 (in_eb:embodyST) : BodyStmtAST0 = 
    match in_eb with     
    //231:BlockBodyStmt  = LBRA BodyStmts RBRA 
    |Node(231,_,_::bodyStmtsNd::_::_) 
        ->BlockStmtAST0(embodyStToBodyStmtsAST0 bodyStmtsNd) 
    //241:BodyStmt  = ID ID InitDefs 
    //"61:InitDefs =  EPSILON"; 
    //"71:InitDefs = EQ Expression"; 
    |Node(241,_,Leaf(tyTkn)::Leaf(varTkn)::initNd::_) 
        ->match initNd with 
          |Node(61,_,_)  
                ->VarDecStmtAST0(tyTkn.Img,(tyTkn.Row,tyTkn.Col),varTkn.Img,(varTkn.Row,varTkn.Col),None) 
          |Node(71,_,_::expNd::_)       
                ->VarDecStmtAST0(tyTkn.Img,(tyTkn.Row,tyTkn.Col),varTkn.Img,(varTkn.Row,varTkn.Col),Some(embodyStToExpAST0 expNd)) 
          | _ -> failwith("unoccurable error in  embodyStToBodyStmtUniAST0 ") 
    //251:BodyStmt = CallFuncStmt 
    //261:CallFuncStmt = ID LPAR CallFuncArgLists RPAR 
    |Node(251,_,callfNd::_) 
        ->match callfNd with 
          |Node(261,_,Leaf(fNameTkn)::_::callfArgListNd::_) 
            ->CallFuncAST0(fNameTkn.Img,(fNameTkn.Row,fNameTkn.Col),(embodyStToCfArgsAST0 callfArgListNd)) 
          | _ -> failwith("unoccurable error in  embodyStToBodyStmtUniAST0 ") 
    | _ -> failwith("unoccurable error in  embodyStToBodyStmtUniAST0 ") 
 
and embodyStToCfArgsAST0 (in_eb:embodyST) :list<ExpAST0> = 
    match in_eb with 
    //271:CallFuncArgLists = EPSILON 
    |Node(271,_,_) 
        ->[] 
    //281:CallFuncArgLists = Expression CallFuncArgLists2 
    |Node(281,_,expNd::cfalNd::_) 
        -> (embodyStToExpAST0 expNd) :: (embodyStToCfArgsAST0 cfalNd) 
    //291:CallFuncArgLists2 = EPSILON 
    |Node(291,_,_) 
        -> [] 
    //301:CallFuncArgLists2 = COMMA Expression CallFuncArgLists2 
    |Node(301,_,_::expNd::cfalNd::_) 
        -> (embodyStToExpAST0 expNd) :: (embodyStToCfArgsAST0 cfalNd) 
    | _ -> failwith("unoccurable error in  embodyStToCfArgsAST0 ") 
 
ではいくつかのソースとそれを変換した例をあげておきます。 
 
例1 
 
struct A {int x;}; 
 
[StructDecAST0 ("A",(1, 8),[VarDecAST0 ("int", (1, 11), "x", (1, 15), null)])] 
 
 
例2 
 
struct A {int x;}; 
void f () 
    A a; 
    int y = a.x; 
}; 
 
 
[StructDecAST0 ("A",(1, 10),[VarDecAST0 ("int", (1, 13), "x", (1, 17), null)]); 
 FuncDecAST0 
   ("void",(1, 23),"f",(1, 28),[], 
    BlockStmtAST0 
      [VarDecStmtAST0 ("A", (1, 41), "a", (1, 43), null); 
       VarDecStmtAST0 
         ("int", (1, 51), "y", (1, 55), 
          Some (DotExpAST0 ("a",(1, 59),[("x", (1, 61))])))])] 
           
           
 
例3 
 
struct A { 
  int x; 
  struct B {int y;}; 
  B z; 
  }; 
 
A k; 
int u = k.z.y; 
 
[StructDecAST0 
   ("A",(1, 10), 
    [VarDecAST0 ("int", (1, 17), "x", (1, 21), null); 
     StructDecAST0 
       ("B",(1, 34),[VarDecAST0 ("int", (1, 37), "y", (1, 41), null)]); 
     VarDecAST0 ("B", (1, 49), "z", (1, 51), null)]); 
 VarDecAST0 ("A", (1, 63), "k", (1, 65), null); 
 VarDecAST0 
   ("int", (1, 69), "u", (1, 73), 
    Some (DotExpAST0 ("k",(1, 77),[("z", (1, 79)); ("y", (1, 81))])))] 
     
 
次回は記号表を定義します。 
 
では今回のソースです。 

続きを読む

テーマ : プログラミング
ジャンル : コンピュータ

F#で入門 コンパイラ 、インタプリタ編 記号表(6)

 今回は前回までの内容(ネストされた変数の定義をもつ記号表紹介用の言語)を、Winソフト化します。  
実行画面は次の通りです。 
 
1039-1.jpg
 
まずソースを入力します。 
 
1039-2.jpg 
 
今回入力したコードはつぎのようなものです。 
 
int x ; 
void f(int k,int u){int y;{int i = y ;f(3);} {int j;}}; 
void g(int z) {int i;}; 
 
その下の「↓」ボタンを押すとASTが表示されます。 
 
[VarDecAST0 ("int", (1, 1), "x", (1, 5), null); 
 FuncDecAST0 
   ("void",(2, 1),"f",(2, 6), 
    [("int", (2, 8), "k", (2, 12)); ("int", (2, 14), "u", (2, 18))], 
    BlockStmtAST0 
      ([VarDecStmtAST0 ("int", (2, 21), "y", (2, 25), null); 
        BlockStmtAST0 
          ([VarDecStmtAST0 
              ("int", (2, 28), "i", (2, 32), Some (VarExpAST0 ("y",(2, 36)))); 
            CallFuncAST0 ("f",(2, 39),[IntExpAST0 ("3",(2, 41))])], 
           {contents = ;}); 
        BlockStmtAST0 
          ([VarDecStmtAST0 ("int", (2, 47), "j", (2, 51), null)],{contents = ;})], 
       {contents = ;}),{contents = ;}); 
 FuncDecAST0 
   ("void",(3, 1),"g",(3, 6),[("int", (3, 8), "z", (3, 12))], 
    BlockStmtAST0 
      ([VarDecStmtAST0 ("int", (3, 16), "i", (3, 20), null)],{contents = ;}), 
    {contents = ;})] 
 
今回は、広域変数部分以外のスコープも表示したいので、スコープをもつ、 
FuncDecAST0 、BlockStmtAST0にスコープ保存用の成分を付け加えています。 
例えば 
BlockStmtAST0 of list<BodyStmtAST0> * (IScope ref)  
として定義してあります。上の表示では、まだ記号表を埋めていないので、スコープ毎の辞書が空なので、 
{contents = ;}というように表示されています。 
 
この状態で、「→」ボタンを押すと、記号表が作成されて 
AST(スコープ登録後)というテキストボックスには 
[VarDecAST0 ("int", (1, 1), "x", (1, 5), null); 
 FuncDecAST0 
   ("void",(2, 1),"f",(2, 6), 
    [("int", (2, 8), "k", (2, 12)); ("int", (2, 14), "u", (2, 18))], 
    BlockStmtAST0 
      ([VarDecStmtAST0 ("int", (2, 21), "y", (2, 25), null); 
        BlockStmtAST0 
          ([VarDecStmtAST0 
              ("int", (2, 28), "i", (2, 32), Some (VarExpAST0 ("y",(2, 36)))); 
            CallFuncAST0 ("f",(2, 39),[IntExpAST0 ("3",(2, 41))])], 
           {contents =  "i" <i:int>  
;}); 
        BlockStmtAST0 
          ([VarDecStmtAST0 ("int", (2, 47), "j", (2, 51), null)], 
           {contents =  "j" <j:int>  
;})],{contents =  "y" <y:int>  
;}), 
    {contents = method:f: args ("k" <k:int> )("u" <u:int> );}); 
 FuncDecAST0 
   ("void",(3, 1),"g",(3, 6),[("int", (3, 8), "z", (3, 12))], 
    BlockStmtAST0 
      ([VarDecStmtAST0 ("int", (3, 16), "i", (3, 20), null)], 
       {contents =  "i" <i:int>  
;}),{contents = method:g: args ("z" <z:int> );})] 
 
というように、スコープの辞書も表示されるようになります。 
 
また右のLogテキストボックスにはログが次のように表示されます。 
 
"int" (1, 1) は 参照 ref:"int" として解決しました。 
変数 "x" (1, 5)を定義しました。 
"void" (2, 1) は 参照 ref:"void" として解決しました。 
関数 "f" (2, 6)を定義しました 
メソッドスコープに移動します 
"int" (2, 8) は 参照 ref:"int" として解決しました。 
変数 "k" (2, 12)を定義しました。 
"int" (2, 14) は 参照 ref:"int" として解決しました。 
変数 "u" (2, 18)を定義しました。 
ローカルスコープに移動します 
"int" (2, 21) は 参照 ref:"int" として解決しました。 
変数 "y" (2, 25)を定義しました。 
ローカルスコープに移動します 
"y" (2, 36) は 型名 intへの参照として解決しました。 
"int" (2, 28) は 参照 ref:"int" として解決しました。 
変数 "i" (2, 32)を定義しました。 
"f" (2, 39) は void型の関数への参照として解決しました。 
スコープを上に戻ります。できたscope内の登録は次の通りです  
" "i" <i:int>  
ローカルスコープに移動します 
"int" (2, 47) は 参照 ref:"int" として解決しました。 
変数 "j" (2, 51)を定義しました。 
スコープを上に戻ります。できたscope内の登録は次の通りです  
" "j" <j:int>  
スコープを上に戻ります。できたscope内の登録は次の通りです  
" "y" <y:int>  
メソッドスコープを上にもどります。できたscope内の登録は次の通りです   
"method:f: args ("k" <k:int> )("u" <u:int> )" 
"void" (3, 1) は 参照 ref:"void" として解決しました。 
関数 "g" (3, 6)を定義しました 
メソッドスコープに移動します 
"int" (3, 8) は 参照 ref:"int" として解決しました。 
変数 "z" (3, 12)を定義しました。 
ローカルスコープに移動します 
"int" (3, 16) は 参照 ref:"int" として解決しました。 
変数 "i" (3, 20)を定義しました。 
スコープを上に戻ります。できたscope内の登録は次の通りです  
" "i" <i:int>  
メソッドスコープを上にもどります。できたscope内の登録は次の通りです   
"method:g: args ("z" <z:int> )" 
 
 
右の下側のSymbolTableテキストボックスにはglobalおよび、入れ子になったスコープが表示されます。 
 
global 
 "int" int  
 "float" float  
 "void" void  
 "x" <x:int>  
 "f" method:f: args ("k" <k:int> )("u" <u:int> )  
 "g" method:g: args ("z" <z:int> )  
 
 
method:f: args ("k" <k:int> )("u" <u:int> ) 
     "y" <y:int>  
 
         "i" <i:int>  
 
         "j" <j:int>  
 
method:g: args ("z" <z:int> ) 
     "i" <i:int>  
      
今回のコードは次の通りです。 

続きを読む

テーマ : プログラミング
ジャンル : コンピュータ

F#で入門 コンパイラ 、インタプリタ編 記号表(5)

 今回は入れ子になったスコープを定義できる言語に対する記号表の作り方の一例を紹介します。 
前回の例で作った言語の関数定義は次のようでした。 
 
1:void f(int k,int u) 
2: { 
3:   int y = k ; 
4:   { 
5:      int m = y ; 
6:   } 
7:   { 
8:      int j =  u ; 
9:   } 
10 }; 
 
上の例でのスコープは、関数名fが広域スコープに属し、引数k,uが関数スコープに属し、3行のyが2~10でのブロックスコープに属し、5行のmが4~6でのブロックスコープに属し、8行のjが7~9のブロックスコープに含まれるという形になります。 
またスコープ間には包含関係があり、4~6でのブロックスコープのenclosing(包含)スコープは2~10のブロックスコープ、7~9でのブロックスコープのenclosing(包含)スコープは2~10のブロックスコープとなります。では定義を始めます。 
Symbolとスコープは次のように定義します。 
 
type Symbol(in_name:string,in_sType:option<IType>) = 
    let mutable scope = None 
    member this.Name = in_name 
    member this.SType = in_sType 
    member this.SetScope(in_scope:option<IScope>) = 
        scope <- in_scope 
    override this.ToString ()= 
        if this.SType  = None then 
            in_name 
        else 
            "<" + this.Name + ":" + this.SType.Value.GetName () + ">" 
 
//Scope概念を表すインターフェイス 
and IScope = 
    abstract getScopeName :unit -> option<string> //スコープ名を返す 
    abstract getEnclosingScope :unit -> option<IScope>     //このスコープを包含する直近のスコープを返す 
    abstract define : Symbol -> unit              //このスコープ内で引数である記号を定義する 
    abstract resolve :string -> option<Symbol>            //スコープ内で引数(name)を探す  
 
広域変数用のGlobalScopeと、局所変数用のLocalScope(上の例ではブロックスコープという言葉で説明)を準備するために、基本クラスのBaseScopeクラスを定義して、GlobalScopeとLocalScopeはこれから、派生させることにします。 
 
ではBaseScopeクラスの定義です。 
 
type BaseScope (in_enclosingScope : option<IScope>) = 
    let symbolDic = new System.Collections.Generic.Dictionary<String,Symbol> () 
    let enclosingScope = in_enclosingScope /////ここ大事//////// 
     
    interface IScope with 
        member this.getEnclosingScope () =  
            enclosingScope  
        member this.define(sym:Symbol) = 
            symbolDic.Add(sym.Name,sym);//同じ名前のものを登録しようとすると例外発生 
            sym.SetScope(Some(this :> IScope)) 
        member this.resolve(name:string) = 
            if symbolDic.ContainsKey(name) then  
                Some(symbolDic.[name]) 
             else 
                let ecs = (this :> IScope).getEnclosingScope() 
                if ecs.IsSome then 
                    (ecs.Value).resolve(name) 
                else 
                    None 
        member this.getScopeName () = //とりあえずこう定義 
            None 
     
    member this.getSymbolDic () = symbolDic 
    override this.ToString () = 
       let sb = System.Text.StringBuilder() 
       let t = Seq.zip symbolDic.Keys symbolDic.Values 
       Seq.iter (fun (key,valu) -> sb.Append(sprintf " %A %A \n" key valu) |> ignore) t 
       sb.ToString()      
 
定義の3行目に「ここ大事」とコメントをつけている部分がありますが、これがスコープ毎が持つ辞書です。 
またメンバ関数this.resolveの内容が大事で、最初に記号名解決をまかされたスコープで、記号名が見つからなければ再帰的に包含スコープをさかのぼって探していくという構造になっています。 
 
ではGlobalScopeとLocalScopeを派生させて定義しておきます。 
 
type GlobalScope () = 
    inherit BaseScope (None) 
    member this.getScopeName () = 
            Some("global") 
 
type LocalScope (in_enclosintScope:IScope) = 
    inherit BaseScope (Some(in_enclosintScope)) 
    member this.getScopeName () = 
            Some("local") 
 
またスコープとして機能するものに、関数宣言部分があります。 
 
1:void f(int k,int u) 
2: { 
3:   int y = k ; 
4:   { 
5:      int m = y ; 
6:   } 
7:   { 
8:      int j =  u ; 
9:   } 
10 }; 
 
について、この例では関数名fはGlobalScopeに属しますが、引数のk,uは関数スコープに属することになります。 
ここではMethodSymbolクラスにIScopeインターフェイスも実装させて、これが、記号(Symbol)としての役割も果たすし、スコープとしての役割も果たすようにします。では定義です。 
 
type MethodSymbol (name:string,in_sType:option<IType>,in_enclosingScope : option<IScope>) = 
    inherit Symbol(name,in_sType) 
    let argsSymbolDic = new System.Collections.Generic.Dictionary<String,Symbol> ()//argsが入る 
    let enclosingScope = in_enclosingScope 
    interface IScope with 
        member this.getEnclosingScope () =  
            enclosingScope  
        member this.define(sym:Symbol) = 
            argsSymbolDic.Add(sym.Name,sym);//同じ名前のものを登録しようとすると例外発生 
            sym.SetScope(Some(this :> IScope)) //symbol毎にスコープを登録 
        member this.resolve(name:string) = 
            if argsSymbolDic.ContainsKey(name) then  
                Some(argsSymbolDic.[name]) 
            else 
                let ecs = (this :> IScope).getEnclosingScope() 
                if ecs.IsSome then 
                    (ecs.Value).resolve(name) // これも再帰! 
                else 
                    None 
        member this.getScopeName () =  
            Some(name) 
  
    override this.ToString () = 
       let sb = System.Text.StringBuilder("method:" + name  ) 
       let t = Seq.zip argsSymbolDic.Keys argsSymbolDic.Values 
       sb.Append(": args ")|>ignore 
       Seq.iter (fun (key,valu) -> sb.Append(sprintf "(%A %A )" key valu) |> ignore) t 
       sb.ToString()     
        
 
記号表を作りだす関数は後で紹介することにして、まずは先ほどの例 
 
1:void f(int k,int u) 
2: { 
3:   int y = k ; 
4:   { 
5:      int m = y ; 
6:   } 
7:   { 
8:      int j =  u ; 
9:   } 
10 }; 
 
でどのようなsopeができあがるかを、例示しておきます。 
(int,float,voidは先に定義しておくものとします。) 
 
global 
 "int" int  
 "float" float  
 "void" void  
 "f" method:f: args ("k" <k:int> )("u" <u:int> )  
///ここまでがGlobalScope内の辞書の内容 
 
method:f: args ("k" <k:int> )("u" <u:int> ) //これは関数スコープ内の辞書の内容 
     "y" <y:int> //2から10のブロックスコープ内の辞書の内容 
 
         "m" <m:int> //4~6のブロックスコープの辞書の内容 
 
         "j" <j:int> //7~9のブロックスコープの辞書の内容 
 
また、インシデントが深くなるほど、上と包含関係にあることを示しています。 
 
もう一つ例を挙げておきます。 
 
int x ; 
void f(int k,int u){int y;{int i = y ;int s = 3;f(3);} {int j;}}; 
void g(int z) {int i;}; 
 
というソースに対し 
 
global 
 "int" int  
 "float" float  
 "void" void  
 "x" <x:int>  
 "f" method:f: args ("k" <k:int> )("u" <u:int> )  
 "g" method:g: args ("z" <z:int> )  
 
 
method:f: args ("k" <k:int> )("u" <u:int> ) 
     "y" <y:int>  
 
         "i" <i:int>  "s" <s:int>  
 
         "j" <j:int>  
 
method:g: args ("z" <z:int> ) 
     "i" <i:int>  
 
ではいよいよ、このようなスコープ群をつくる関数ですが、これを 
 
mkSymtbl (cur_scope: IScope ref) (in_decLst :list<DecAST0>)  
 
という名前で定義します。引数のcur_scopeは現在処理中のスコープを示す、ポインタのようなものです。 
ブロックを表すASTに差しかかると 
        let newLocal = new LocalScope((!cur_scope)) 
        printfn "ローカルスコープに移動します" 
        cur_scope := (newLocal :> IScope) //ローカルスコープへの移動 
というようなコードで、localスコープを生成しこれに移動し、内部の処理が終わったところで 
        printfn "スコープを上に戻ります。できたscope内の登録は次の通りです \n%A" ((!cur_scope).ToString())  
        cur_scope := ((!cur_scope).getEnclosingScope()).Value //ローカルスコープの取り外し 
というようなコードで、スコープを上に戻ります。 
 
なお今回のコードでは、スコープ群を生成しながら記号名解決をして、その結果を表示するだけなので、スコープの内容は、最後にcur_scopeの示すglobalScopeしか参照できません。(ASTを降りては登ってくるため、最後はcur_scopeは開始スコープであるglobalScopeにもどってきています。)スコープ群は子から親への参照しかできないような木構造になっているため上から下へはたどれないので、次回はASTの、ブロックノードにこれを保存するようにします。(なお、実際の言語開発プログラムでは変数ノード毎にスコープを保存します。) 
 
mkSymtbl関数部分の定義は次の通りです。 
 
let mkSymtbl (cur_scope: IScope ref) (in_decLst :list<DecAST0>) = 
     
    let checkAndResistVarDef (tyName:string) (tyPos:PosAST0) (varName:string) (varPos:PosAST0) = 
        let tyRef = (!cur_scope).resolve(tyName) 
        if tyRef.IsNone then 
            printfn "%A %A この型名が登録されていないため参照を解決できません。" tyName tyPos 
        else 
            let tyrv = tyRef.Value 
            match tyrv with 
            | :? BuiltInTypeSymbol -> 
                printfn "%A %A は 参照 ref:%A として解決しました。" tyName tyPos tyrv.Name  
                let t = (tyrv :?> BuiltInTypeSymbol) :> IType 
                (!cur_scope).define (new VariableSymbol(varName,Some(t) )) 
                printfn "変数 %A %Aを定義しました" varName varPos 
            | _ ->  
                printfn "%A %A は %Aが型名でないため解決できません。" tyName tyPos tyName 
     
    let rec mkSymtblDecLst  (decLst :list<DecAST0>) = 
        for ele in decLst do 
            mkSymtblDec ele 
     
    and mkSymtblDec  (dec : DecAST0) = 
        match dec with 
        |VarDecAST0(tyName,tyPos,varName,varPos,initExp)  
            ->  if initExp.IsSome then  mkSymtblExp (initExp.Value) 
                checkAndResistVarDef  tyName tyPos varName varPos 
 
        |FuncDecAST0(funcTypeName,functypePos,funcName,funcPos,argList,bodyStmts) 
            ->  let ftyRef = (!cur_scope).resolve(funcTypeName) 
                if ftyRef.IsNone then 
                    printfn "%A %A この型名が登録されていないため参照を解決できません。" funcTypeName functypePos 
                else 
                   let ftyrv = ftyRef.Value 
                   match ftyrv with 
                   | :? BuiltInTypeSymbol -> 
                        printfn "%A %A は 参照 ref:%A として解決しました。" funcTypeName functypePos ftyrv.Name  
                        let t = (ftyrv :?> BuiltInTypeSymbol) :> IType 
                        let newMSym = new MethodSymbol(funcName,Some(t),Some(!cur_scope)) 
                        (!cur_scope).define(newMSym)//関数symbloの登録 
                        printfn "関数 %A %Aを定義しました" funcName funcPos 
                        printfn "メソッドスコープに移動します"  
                        cur_scope := (newMSym :> IScope) //メソッドスコープへの移動 
                        for (tN,tP,vN,vP) in argList do //引数リストの処理 
                            checkAndResistVarDef  tN tP vN vP 
                        match bodyStmts with 
                        |BlockStmtAST0(blockeles) 
                            ->mkSymtblBlockStmtAST0 blockeles 
                        |_ -> failwith "unoccurrable error in  mkSymtblDec" 
                        printfn "メソッドスコープを上にもどります。できたscope内の登録は次の通りです  \n%A" ((!cur_scope).ToString())       
                        cur_scope := ((!cur_scope).getEnclosingScope()).Value //メソッドスコープの取り外し    
                   | _ ->  
                        printfn "%A %A は %Aが型名でないため解決できません。" funcTypeName functypePos funcTypeName 
     
     
    and mkSymtblExp (exp : ExpAST0) = 
        match exp with 
        |VarExpAST0(varName,varPos)  
            ->  let varRef = (!cur_scope).resolve(varName) 
                if varRef.IsNone then 
                    printfn "%A %A この変数名が登録されていないため参照を解決できません。" varName varPos 
                else 
                    let varrv = varRef.Value 
                    match varrv with 
                    | :? VariableSymbol -> 
                        printfn "%A %A は 型名 %Aへの参照として解決しました。" varName varPos varrv.SType.Value  
                    | _ ->  
                        printfn "%A %A は %Aが変数名でないため解決できません。" varName varPos varName 
        |IntExpAST0(_) 
            -> () 
 
    and mkSymtblBlockStmtAST0 (bStmtLst :list<BodyStmtAST0>) = 
        let newLocal = new LocalScope((!cur_scope)) 
        printfn "ローカルスコープに移動します" 
        cur_scope := (newLocal :> IScope) //ローカルスコープへの移動 
        for ele in bStmtLst do 
            match ele with 
            |VarDecStmtAST0(varDecEle) 
                -> mkSymtblDec (VarDecAST0(varDecEle)) 
             
            |CallFuncAST0 (funcName,funcPos,argList) 
                -> //関数の名前部分の処理 
                  let funcNameRef = (!cur_scope).resolve(funcName) 
                  if funcNameRef.IsNone then 
                    printfn "%A %A この関数名が登録されていないため参照を解決できません。" funcName funcPos 
                  else 
                    let funcnv = funcNameRef.Value 
                    match funcnv with 
                    | :? MethodSymbol -> 
                        printfn "%A %A は %A型の関数への参照として解決しました。" funcName funcPos funcnv.SType.Value  
                    | _ ->  
                        printfn "%A %A は %Aが関数名でないため解決できません。" funcName funcPos funcName 
                  //引数部分の処理 
                  for argEle in argList do 
                    mkSymtblExp argEle   
             
            |BlockStmtAST0 (bodyStmtList)  
                ->mkSymtblBlockStmtAST0 bodyStmtList 
        printfn "スコープを上に戻ります。できたscope内の登録は次の通りです \n%A" ((!cur_scope).ToString())  
        cur_scope := ((!cur_scope).getEnclosingScope()).Value //ローカルスコープの取り外し 
 
    mkSymtblDecLst in_decLst 
    (!cur_scope)  //globalScopeを返す。 
     
この関数をつかって 
int x ;void f(int k,int u){int y;{int i = y ;f(3);} {int j;}}; void g(int z) {int i;}; 
 
(AST表示) 
 
[VarDecAST0 ("int", (1, 1), "x", (1, 5), null); 
 FuncDecAST0 
   ("void",(1, 8),"f",(1, 13), 
    [("int", (1, 15), "k", (1, 19)); ("int", (1, 21), "u", (1, 25))], 
    BlockStmtAST0 
      [VarDecStmtAST0 ("int", (1, 28), "y", (1, 32), null); 
       BlockStmtAST0 
         [VarDecStmtAST0 
            ("int", (1, 35), "i", (1, 39), Some (VarExpAST0 ("y",(1, 43)))); 
          CallFuncAST0 ("f",(1, 46),[IntExpAST0 ("3",(1, 48))])]; 
       BlockStmtAST0 [VarDecStmtAST0 ("int", (1, 54), "j", (1, 58), null)]]); 
 FuncDecAST0 
   ("void",(1, 64),"g",(1, 69),[("int", (1, 71), "z", (1, 75))], 
    BlockStmtAST0 [VarDecStmtAST0 ("int", (1, 79), "i", (1, 83), null)])] 
 
を処理すると次のように表示されます。 
 
"int" (1, 1) は 参照 ref:"int" として解決しました。 
変数 "x" (1, 5)を定義しました 
"void" (1, 8) は 参照 ref:"void" として解決しました。 
関数 "f" (1, 13)を定義しました 
メソッドスコープに移動します 
"int" (1, 15) は 参照 ref:"int" として解決しました。 
変数 "k" (1, 19)を定義しました 
"int" (1, 21) は 参照 ref:"int" として解決しました。 
変数 "u" (1, 25)を定義しました 
ローカルスコープに移動します 
"int" (1, 28) は 参照 ref:"int" として解決しました。 
変数 "y" (1, 32)を定義しました 
ローカルスコープに移動します 
"y" (1, 43) は 型名 intへの参照として解決しました。 
"int" (1, 35) は 参照 ref:"int" として解決しました。 
変数 "i" (1, 39)を定義しました 
"f" (1, 46) は void型の関数への参照として解決しました。 
スコープを上に戻ります。できたscope内の登録は次の通りです 
" "i" <i:int> 
ローカルスコープに移動します 
"int" (1, 54) は 参照 ref:"int" として解決しました。 
変数 "j" (1, 58)を定義しました 
スコープを上に戻ります。できたscope内の登録は次の通りです 
" "j" <j:int> 
スコープを上に戻ります。できたscope内の登録は次の通りです 
" "y" <y:int> 
メソッドスコープを上にもどります。できたscope内の登録は次の通りです 
"method:f: args ("k" <k:int> )("u" <u:int> )" 
"void" (1, 64) は 参照 ref:"void" として解決しました。 
関数 "g" (1, 69)を定義しました 
メソッドスコープに移動します 
"int" (1, 71) は 参照 ref:"int" として解決しました。 
変数 "z" (1, 75)を定義しました 
ローカルスコープに移動します 
"int" (1, 79) は 参照 ref:"int" として解決しました。 
変数 "i" (1, 83)を定義しました 
スコープを上に戻ります。できたscope内の登録は次の通りです 
" "i" <i:int> 
メソッドスコープを上にもどります。できたscope内の登録は次の通りです 
"method:g: args ("z" <z:int> )" 
 
次回は、これのWindowsソフトを作ります。 
今回の全コードは次の通りです。 

続きを読む

テーマ : プログラミング
ジャンル : コンピュータ

F#で入門 コンパイラ 、インタプリタ編 記号表(4)

 今回は入れ子になったスコープを定義できる言語を作る場合の、記号表の作り方の準備として、まずは例に使う言語を一つ定義していきます。 
次をみてください。 
 
int i ; 
void f(int k,int u){int y = k ;{int m = y ;} {int j =  u ;}}; 
void g(int z) {int i = 7;f(3、9);}; 
 
今回はこのように、変数宣言と、関数定義の並びが許される言語を定義します。 
 
上の例では広域変数および関数名はi,f,gであり, 
特にfについて考察すると 
 
1:void f(int k,int u) 
2: { 
3:   int y = k ; 
4:   { 
5:      int m = y ; 
6:   } 
7:   { 
8:      int j =  u ; 
9:   } 
10 }; 
 
2,10の括弧内で参照解決できる名前はi,f,g,k,u 
4,6の括弧内で参照解決できる名前はi,f,g,k,u,y 
7,9の括弧内で参照解決できる名前はi,f,g,k,u,y 
となります。 
これを処理するためにブロック毎にスコープを対応させて、それぞれのスコープがdictionatyを持つ形にします。 
 
とりあえず、今回はトークンルール及び、文法規則を定義して、ASTに変換するところまで行きたいと思います。 
 
きれいでない定義ですが、トークンルール及び、文法規則は次のようにします。 
 
let tnR1 = 
   [("SEMI","\;"); 
    ("EQ","="); 
    ("LPAR","\("); 
    ("RPAR","\)"); 
    ("LBRA","\{"); 
    ("RBRA","\}"); 
    ("COMMA","\,"); 
    ("ID","[a-z][a-z0-9]*"); 
    ("NUM","0|[1-9][0-9]*") 
      ] 
 
let grammersStrLst1 = 
   ["1:Program = DeclStmts "; 
     
    "11:DeclStmts = DeclStmt SEMI DeclStmts2"; 
    "21:DeclStmts = FuncDeclStmt SEMI DeclStmts2"; 
     
    "31:DeclStmts2  = EPSILON"; 
    "41:DeclStmts2  = DeclStmts"; 
 
    "51:DeclStmt = ID ID InitDefs"; 
    "61:InitDefs =  EPSILON"; 
    "71:InitDefs = EQ Expression"; 
    "81:Expression = ID"; 
    "91:Expression = NUM"; 
 
    "101:FuncDeclStmt = ID ID LPAR ArgLists RPAR LBRA BodyStmts RBRA"; 
    "111:ArgLists = EPSILON"; 
    "121:ArgLists = ID ID ArgLists2"; 
    "131:ArgLists2 = EPSILON"; 
    "141:ArgLists2 = COMMA ID ID ArgLists2"; 
  
    "201:BodyStmts = BodyStmt SEMI BodyStmts2"; 
    "202:BodyStmts = BlockBodyStmt BodyStmts2"; 
 
    "211:BodyStmts2  = EPSILON"; 
    "221:BodyStmts2  = BodyStmts"; 
    "231:BlockBodyStmt  = LBRA BodyStmts RBRA"; 
    "241:BodyStmt  = ID ID InitDefs"; 
    "251:BodyStmt = CallFuncStmt"; 
    "261:CallFuncStmt = ID LPAR CallFuncArgLists RPAR"; 
    "271:CallFuncArgLists = EPSILON"; 
    "281:CallFuncArgLists = Expression CallFuncArgLists2"; 
    "291:CallFuncArgLists2 = EPSILON"; 
    "301:CallFuncArgLists2 = COMMA Expression CallFuncArgLists2"; 
 
    ] 
 
AST用に次のような型を定義します。 
 
type PosAST0 = int*int //ソース内の位置 
 
                 
type ExpAST0 =  
     |VarExpAST0 of string * PosAST0   //変数 
     |IntExpAST0 of string * PosAST0  //3等 
and 
    VarDecElesAST0 = string * PosAST0 * string * PosAST0 * option<ExpAST0>   
                   //typeName typPos    varName varPos       initExp 
 
and DecAST0 = 
     |VarDecAST0  of VarDecElesAST0 
     |FuncDecAST0 of string * PosAST0 * string * PosAST0 * list<string * PosAST0 * string * PosAST0> * BodyStmtAST0               
                  //funcType * functypePos *funcName funcPos list<typeName typPos varName varPos>  //BodyStmtAST0の部分は実際にはBlockStmtAST0を使う 
  
and BodyStmtAST0 = 
    |VarDecStmtAST0 of VarDecElesAST0  
    |CallFuncAST0 of string * PosAST0 * list<ExpAST0> //funcName funcPos argList 
    |BlockStmtAST0 of list<BodyStmtAST0>   
 
ではLR1TokenizeAndParseクラスで生成される具象構文木をASTに変換する関数を定義します。 
 
let rec embodyStToAST0 (in_eb:embodyST) : list<DecAST0> = 
    match in_eb with 
    //1:Program = DeclStmts  
    |Node(1,_,dssNd::_) 
        -> embodyStToAST0 dssNd 
    //11:DeclStmts = DeclStmt SEMI DeclStmts2 
    |Node(11,_,dsNd::_::dsNd2::_) 
        -> (embodyStToAST0 dsNd) @ ( embodyStToAST0 dsNd2) 
    //21:DeclStmts = FuncDeclStmt SEMI DeclStmts2 
    |Node(21,_,fdsNd::_::dsNd2::_) 
        ->(embodyStToAST0 fdsNd) @ ( embodyStToAST0 dsNd2) 
    //31:DeclStmts2  = EPSILON 
    |Node(31,_,_) 
        -> [] 
    //41:DeclStmts2  = DeclStmts 
    |Node(41,_,dssNd::_) 
        ->embodyStToAST0 dssNd 
    //51:DeclStmt = ID ID InitDefs 
    //61:InitDefs =  EPSILON 
    //71:InitDefs = EQ Expression 
    |Node(51,_,Leaf(tyTkn)::Leaf(varTkn)::initNd::_) 
        ->match initNd with 
          |Node(61,_,_)  
                ->[VarDecAST0(tyTkn.Img,(tyTkn.Row,tyTkn.Col),varTkn.Img,(varTkn.Row,varTkn.Col),None)] 
          |Node(71,_,_::expNd::_)       
                ->[VarDecAST0(tyTkn.Img,(tyTkn.Row,tyTkn.Col),varTkn.Img,(varTkn.Row,varTkn.Col),Some(embodyStToExpAST0 expNd))] 
          | _ -> failwith("unoccurable error in embodyStToAST0 ") 
    //101:FuncDeclStmt = ID ID LPAR ArgLists RPAR LBRA BodyStmts RBRA 
    |Node(101,_, Leaf(tyTkn)::Leaf(funNameTkn)::_::argListNd::_::_::bodyStmtsNd::_) 
        -> [FuncDecAST0(tyTkn.Img,(tyTkn.Row,tyTkn.Col),funNameTkn.Img,(funNameTkn.Row,funNameTkn.Col), 
             embodyStToArgAST0 argListNd, BlockStmtAST0(embodyStToBodyStmtsAST0 bodyStmtsNd))]   
    |_ ->failwith("unoccurable error in embodyStToAST0 ")   
 
and embodyStToExpAST0 (in_eb:embodyST) : ExpAST0 = //expノード部分の変換を担当 
    match in_eb with 
    //81:Expression = ID 
    |Node(81,_,Leaf(idTkn)::_) 
        ->VarExpAST0(idTkn.Img,(idTkn.Row,idTkn.Col)) 
    //91:Expression = NUM 
    |Node(91,_,Leaf(numTkn)::_) 
        ->IntExpAST0(numTkn.Img,(numTkn.Row,numTkn.Col)) 
    |_ ->failwith("unoccurable error in embodyStToExpAST0 ")   
     
and embodyStToArgAST0  (in_eb:embodyST) : list<string * PosAST0 * string * PosAST0> = //関数定義の引数部分の変換を担当    
    match in_eb with 
    //111:ArgLists = EPSILON 
    |Node(111,_,_) 
        ->[] 
    //121:ArgLists = ID ID ArgLists2 
    |Node(121,_,Leaf(tyTkn)::Leaf(varTkn)::argLstNd::_) 
        ->[(tyTkn.Img,(tyTkn.Row,tyTkn.Col),varTkn.Img,(varTkn.Row,varTkn.Col))] @ (embodyStToArgAST0 argLstNd) 
    //131:ArgLists2 = EPSILON 
    |Node(131,_,_) 
        -> [] 
    //141:ArgLists2 = COMMA ID ID ArgLists2 
    |Node(141,_,_::Leaf(tyTkn)::Leaf(varTkn)::argLstNd::_) 
        ->[(tyTkn.Img,(tyTkn.Row,tyTkn.Col),varTkn.Img,(varTkn.Row,varTkn.Col))] @ (embodyStToArgAST0 argLstNd) 
    |_ ->failwith("unoccurable error in embodyStToArgAST0 ")  
 
and embodyStToBodyStmtsAST0 (in_eb:embodyST) :list<BodyStmtAST0> =  
    match in_eb with 
    //201:BodyStmts = BodyStmt SEMI BodyStmts2 
    |Node(201,_,bdstmtNd::_::bdstmtsNd2::_) 
        -> (embodyStToBodyStmtUniAST0 bdstmtNd)::(embodyStToBodyStmtsAST0 bdstmtsNd2) 
    //202:BodyStmts = BlockBodyStmt BodyStmts2 
    |Node(202,_,blockstmtNd::bdstmtsNd2::_) 
        ->(embodyStToBodyStmtUniAST0 blockstmtNd)::(embodyStToBodyStmtsAST0 bdstmtsNd2) 
    //211:BodyStmts2  = EPSILON 
    |Node(211,_,_) 
        -> [] 
    //221:BodyStmts2  = BodyStmts 
    |Node(221,_,bodyStmtsNd::_) 
        -> embodyStToBodyStmtsAST0 bodyStmtsNd 
    |_ ->failwith("unoccurable error in embodyStToBodyStmtsST0 ") 
 
and embodyStToBodyStmtUniAST0 (in_eb:embodyST) : BodyStmtAST0 = 
    match in_eb with     
    //231:BlockBodyStmt  = LBRA BodyStmts RBRA 
    |Node(231,_,_::bodyStmtsNd::_::_) 
        ->BlockStmtAST0(embodyStToBodyStmtsAST0 bodyStmtsNd) 
    //241:BodyStmt  = ID ID InitDefs 
    //"61:InitDefs =  EPSILON"; 
    //"71:InitDefs = EQ Expression"; 
    |Node(241,_,Leaf(tyTkn)::Leaf(varTkn)::initNd::_) 
        ->match initNd with 
          |Node(61,_,_)  
                ->VarDecStmtAST0(tyTkn.Img,(tyTkn.Row,tyTkn.Col),varTkn.Img,(varTkn.Row,varTkn.Col),None) 
          |Node(71,_,_::expNd::_)       
                ->VarDecStmtAST0(tyTkn.Img,(tyTkn.Row,tyTkn.Col),varTkn.Img,(varTkn.Row,varTkn.Col),Some(embodyStToExpAST0 expNd)) 
          | _ -> failwith("unoccurable error in  embodyStToBodyStmtUniAST0 ") 
    //251:BodyStmt = CallFuncStmt 
    //261:CallFuncStmt = ID LPAR CallFuncArgLists RPAR 
    |Node(251,_,callfNd::_) 
        ->match callfNd with 
          |Node(261,_,Leaf(fNameTkn)::_::callfArgListNd::_) 
            ->CallFuncAST0(fNameTkn.Img,(fNameTkn.Row,fNameTkn.Col),(embodyStToCfArgsAST0 callfArgListNd)) 
          | _ -> failwith("unoccurable error in  embodyStToBodyStmtUniAST0 ") 
    | _ -> failwith("unoccurable error in  embodyStToBodyStmtUniAST0 ") 
 
and embodyStToCfArgsAST0 (in_eb:embodyST) :list<ExpAST0> = 
    match in_eb with 
    //271:CallFuncArgLists = EPSILON 
    |Node(271,_,_) 
        ->[] 
    //281:CallFuncArgLists = Expression CallFuncArgLists2 
    |Node(281,_,expNd::cfalNd::_) 
        -> (embodyStToExpAST0 expNd) :: (embodyStToCfArgsAST0 cfalNd) 
    //291:CallFuncArgLists2 = EPSILON 
    |Node(291,_,_) 
        -> [] 
    //301:CallFuncArgLists2 = COMMA Expression CallFuncArgLists2 
    |Node(301,_,_::expNd::cfalNd::_) 
        -> (embodyStToExpAST0 expNd) :: (embodyStToCfArgsAST0 cfalNd) 
    | _ -> failwith("unoccurable error in  embodyStToCfArgsAST0 ") 
 
 
ではいくつかのソースとそれを変換した例をあげておきます。 
 
例1 
int x; 
 
 [VarDecAST0 ("int", (1, 1), "x", (1, 5), null)] 
 
例2 
 
int x = 3; 
 
 [VarDecAST0 ("int", (1, 1), "x", (1, 5), Some (IntExpAST0 ("3",(1, 9))))] 
 
例3 
 
void f(int x,int z){ int j = x; {int m = z ;}}; 
 
 [FuncDecAST0 
     ("void",(1, 1),"f",(1, 6), 
      [("int", (1, 8), "x", (1, 12)); ("int", (1, 14), "z", (1, 18))], 
      BlockStmtAST0 
        [VarDecStmtAST0 
           ("int", (1, 22), "j", (1, 26), Some (VarExpAST0 ("x",(1, 30)))); 
         BlockStmtAST0 
           [VarDecStmtAST0 
              ("int", (1, 34), "m", (1, 38), Some (VarExpAST0 ("z",(1, 42))))]])] 
 
例4 
 
int u = 2 ;int g(int x){ int j = u;}; 
 
[VarDecAST0 ("int", (1, 1), "u", (1, 5), Some (IntExpAST0 ("2",(1, 9)))); 
   FuncDecAST0 
     ("int",(1, 12),"g",(1, 16),[("int", (1, 18), "x", (1, 22))], 
      BlockStmtAST0 
        [VarDecStmtAST0 
           ("int", (1, 26), "j", (1, 30), Some (VarExpAST0 ("u",(1, 34))))])] 
 
例5 
 
int x ;void f(int k,int u){int y;{int i = y ;f(3);} {int j;}}; void g(int z) {int i;}; 
 
  [VarDecAST0 ("int", (1, 1), "x", (1, 5), null); 
   FuncDecAST0 
     ("void",(1, 8),"f",(1, 13), 
      [("int", (1, 15), "k", (1, 19)); ("int", (1, 21), "u", (1, 25))], 
      BlockStmtAST0 
        [VarDecStmtAST0 ("int", (1, 28), "y", (1, 32), null); 
         BlockStmtAST0 
           [VarDecStmtAST0 
              ("int", (1, 35), "i", (1, 39), Some (VarExpAST0 ("y",(1, 43)))); 
            CallFuncAST0 ("f",(1, 46),[IntExpAST0 ("3",(1, 48))])]; 
         BlockStmtAST0 [VarDecStmtAST0 ("int", (1, 54), "j", (1, 58), null)]]); 
   FuncDecAST0 
     ("void",(1, 64),"g",(1, 69),[("int", (1, 71), "z", (1, 75))], 
      BlockStmtAST0 [VarDecStmtAST0 ("int", (1, 79), "i", (1, 83), null)])] 
 
次回は記号表を定義します。 
 
では今回のソースです。 

続きを読む

テーマ : プログラミング
ジャンル : コンピュータ

F#で入門 コンパイラ 、インタプリタ編 記号表(3)

 今回は前回までの内容(広域変数の定義のみをもつ記号表紹介用の言語)を、Winソフト化します。 
実行画面は次の通りです。 
 
1036-1.jpg
 
では、使用方法です。トークン化ルールと構文規則は固定ですので、表示のみです。 
まずソース欄にソースを入力します。 
 
1036-2.jpg 
 
次に「↓」ボタンを押します。すると下のASTテキストボックスにASTツリーが表示されます。 
 
1036-3.jpg 
 
次に「→」ボタンを押します。すると右のテキストボックスに、ログと記号表が表示されます。 
 
1036-4.jpg
 
次回は、ネストしたスコープをもつ場合の記号表をやりたいと思います。 
 
今回のコードは以下の通りです。 

続きを読む

テーマ : プログラミング
ジャンル : コンピュータ

プロフィール

T GYOUTEN

Author:T GYOUTEN
F#と英単語とフリーソフトと読書に興味があります。
ホームページでフリーソフトも公開しています。どぞ御贔屓に。

最新記事
最新コメント
最新トラックバック
月別アーカイブ
カテゴリ
フリーエリア
フリーエリア
blogram投票ボタン
検索フォーム
RSSリンクの表示
リンク
ブロとも申請フォーム

この人とブロともになる

QRコード
QRコード
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。