スポンサーサイト

上記の広告は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))])))] 
     
 
次回は記号表を定義します。 
 
では今回のソースです。 

続きを読む

スポンサーサイト

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

プロフィール

T GYOUTEN

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

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

この人とブロともになる

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