スポンサーサイト

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

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

 (今回からの内容はオライリーから出ている「言語実装パターン」を参考にさせていただいてます。) 
前回は広域変数のみを扱う記号表導入の為、簡単な文法を定義し、それをAST(抽象木)に変換する関数を作りました。 
トークンルールと文法は次のようなものでした。 
let tnR1 =   
    [ 
    "RPAR","\("; 
    "LPAR","\)"; 
    "SEMI","\;"; 
    "EQ","="; 
    "ADD","\+"; 
    "MUL","\*"; 
    "ID","[a-z][a-z0-9]*"; 
    "NUM","0|[1-9][0-9]*"; 
    "FNUM","(0|[1-9][0-9]*)\.([0-9]+)" 
    ] 
 
let grammersStrLst1 = 
   ["1:Program = DeclStmts "; 
     
    "11:DeclStmts = DeclStmt SEMI DeclStmts2"; 
    
    "31:DeclStmts2  = EPSILON"; 
    "41:DeclStmts2  = DeclStmts"; 
 
    "51:DeclStmt = ID ID InitDefs"; 
    "61:InitDefs =  EPSILON"; 
 
    "71:InitDefs = EQ Exp"; 
    "72:Exp = Term" 
    "73:Exp = Term ADD Term" 
    "74:Term = Fact" 
    "75:Term = Fact MUL Fact" 
     
    "81:Fact = ID"; 
    "91:Fact = NUM"; 
    "92:Fact = FNUM"; 
    "93:Fact = RPAR Exp LPAR" 
   
    ] 
     
文法ルールから分かるようにこれは初期値なしの定義(int i; 等)か初期値ありの定義(float a = 3.0 等)が許された、定義のみの並びが許される文法となっています。また初期値部分は2項のみの演算(+,*)が許されています。 
抽象構文用に 
type PosAST0 = int*int //ソース内の位置 
 
type OperAST0 = 
    |PlusOPAST0  //+ 
    |MulOPAST0   //* 
                 
type ExpAST0 =  
     |VarExpAST0 of string * PosAST0      //変数を表す。 
     |IntExpAST0 of string * PosAST0      //3などのint型の即値を表す。 
     |FloatExpAST0 of string * PosAST0    //1.0などのfloat型の即値を表す。 
     |OpExpAST0 of ExpAST0 * ExpAST0 * OperAST0  //left right op (2項演算を表す。) 
 
and DecAST0 = 
     |SimpleDecAST0 of string * PosAST0 * string * PosAST0 //int xなどの宣言を表す 
                       //typeName typPos varName varPos  
     |InitDecAST0 of string * PosAST0 * string * PosAST0 * ExpAST0  //int x = 3などの宣言を表す。 
                      //typeName typPos varName varPos initExp    
                       
という型を準備して、前回の変換関数で、 
int x = 2;float y;int k = x + 3;をASTに変換すると、 
 
[InitDecAST0 ("int",(1, 1),"x",(1, 5),IntExpAST0 ("2",(1, 9))); 
 SimpleDecAST0 ("float",(1, 11),"j",(1, 17)); 
 InitDecAST0 
   ("int",(1, 19),"k",(1, 23), 
    OpExpAST0 (VarExpAST0 ("x",(1, 27)),IntExpAST0 ("3",(1, 31)),PlusOPAST0))] 
 
となるのでした。 
さて記号表を考えるのですが、記号表にはiというような、変数名も登録しますし、intというような型名も登録します。 
記号をあるクラスのインスタンスで表したいと思います。このクラスをSymbolクラスとします。 
変数にたいしては、変数名と型が必要なので、この二つをフィールドとします。 
変数名はstring型でよいのですが、変数の型は 
 
type IType = 
  interface 
       abstract GetName : unit -> string 
  end 
 
を実装した、Symbolクラスからの派生クラスが担当することにします。 
こうしておけば、型も変数もSymbolクラスそのもののインスタンスか、その派生クラスのインスタンスになるので、記号表に登録する際に同じような扱いができるというわけです。 
記号表に登録するのは、名前とこのSymbolクラスのオブジェクトの対応です。 
ではSymbolクラスの定義です。 
 
type Symbol(in_name:string,in_sType:option<IType>) = 
    member this.Name = in_name 
    member this.SType = in_sType 
    override this.ToString ()= 
        if this.SType  = None then 
            in_name 
        else 
            "<" + this.Name + ":" + this.SType.Value.GetName () + ">" 
 
次に変数を担当するVariableSymbolクラスの定義です。 
 
type VariableSymbol (name:string,in_sType:option<IType>) = 
    inherit Symbol(name,in_sType) 
 
次に組み込み型を担当する(上の文法定義ではintとfloatに対応する2つのインスタンスを生成し、記号表のdictionaryに登録することになります。)BuiltInTypeSymboクラスの定義です。 
 
type BuiltInTypeSymbol (name:string) = 
    inherit Symbol(name,None) //型はNone 
    interface IType with 
        member this.GetName () = 
            name 
 
さて次にスコープというものを導入します。今考えているのは、広域変数のみをもつ言語なので、ここでは必要ないのですが、今後スコープつきの言語を考える際に必要になるので、ここで導入しておきます。 
 
 
//Scope概念を表すインターフェイス 
type IScope = 
    abstract getScopeName :unit -> option<string> //スコープ名を返す 
    abstract getEnclosingScope :unit -> option<IScope>     //このスコープを包含する直近のスコープを返す 
    abstract define : Symbol -> unit              //このスコープ内でSymbolを定義する 
    abstract resolve :string -> option<Symbol>            //スコープ内で引数(name)を探す  
 
では、単一スコープのための記号表を定義します。 
 
type SymbolTable () = 
    let symbolDic = new System.Collections.Generic.Dictionary<String,Symbol> () 
    interface IScope with 
        member this.getScopeName () = 
            Some("global") 
        member this.getEnclosingScope () = //単一スコープなので、これを含むスコープなし 
            None 
        member this.define  (sym:Symbol) = 
            symbolDic.Add(sym.Name,sym);//同じ名前のものを登録しようとすると例外発生(手抜き) 
        member this.resolve (name:string) = 
           if symbolDic.ContainsKey(name) then 
              Some(symbolDic.[name]) 
           else 
              None 
    override this.ToString() = 
       let sb = System.Text.StringBuilder(((this:>IScope).getScopeName ()).ToString()) 
       sb.Append("\n") |> ignore 
       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()      
 
    member this.initTypeSystem () = //組み込み型の登録 
        (this:>IScope).define(new BuiltInTypeSymbol("int")) 
        (this:>IScope).define(new BuiltInTypeSymbol("float")) 
         
 
これで、記号表の準備が整ったので、ASTをトラバースしながら、記号表に記号を登録したり、int i = j + 2とかの場合はjは何なのかの定義を記号表から探して解決したりしていく関数mkSymtblDecを定義します。 
 
let mkSymtbl (in_symTbl:IScope) (in_decLst :list<DecAST0>) = 
    let rec mkSymtblDecLst  (decLst :list<DecAST0>) = 
        for ele in decLst do 
            mkSymtblDec ele 
     
    and mkSymtblDec (dec : DecAST0) = 
        match dec with 
        |SimpleDecAST0(tyName,tyPos,varName,varPos) //int a;のような宣言 
            -> let tyRef = in_symTbl.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 
                        in_symTbl.define (new VariableSymbol(varName,Some(t) )) 
                        printfn "変数 %A %Aを定義しました" varName varPos 
                   | _ ->  
                        printfn "%A %A は %Aが型名でないため解決できません。" tyName tyPos tyName 
         
        |InitDecAST0(tyName,tyPos,varName,varPos,initExp) 
            -> mkSymtblExp initExp 
               let tyRef = in_symTbl.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 
                        in_symTbl.define (new VariableSymbol(varName,Some(t) )) 
                        printfn "変数 %A %Aを定義しました" varName varPos 
                   | _ ->  
                        printfn "%A %A は %Aが型名でないため解決できません。" tyName tyPos tyName 
  
    and mkSymtblExp (exp : ExpAST0) = 
        match exp with 
        |VarExpAST0(varName,varPos)  
            -> let varRef = in_symTbl.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(_) 
            -> () 
        |FloatExpAST0(_) 
            -> () 
        |OpExpAST0(leftExp,rightExp,_) 
            -> mkSymtblExp leftExp 
               mkSymtblExp rightExp    
 
     
    mkSymtblDecLst  in_decLst      
 
では使ってみます。 
 
> let tp1 = new LR1TokenizeAndParse (tnR1,grammersStrLst1);; 
 
val tp1 : LR1TokenizeAndParse 
 
> let src0 = ["int x = 2;float y;int k = x + 3; "];; 
 
val src0 : string list = ["int x = 2;float y;int k = x + 3; "] 
 
> let edst = tp1.GetEBASTtree(src0);; 
 
val edst : embodyST = 
  Node 
    (1, "1:Program = DeclStmts ", 
     [Node 
        (11, "11:DeclStmts = DeclStmt SEMI DeclStmts2", 
         [Node 
            (51, "51:DeclStmt = ID ID InitDefs", 
             [Leaf [ID int (1,1)] ; Leaf [ID x (1,5)] ; 
              Node 
                (71, "71:InitDefs = EQ Exp", 
                 [Leaf [EQ = (1,7)] ; 
                  Node 
                    (72, "72:Exp = Term", 
                     [Node 
                        (74, "74:Term = Fact", 
                         [Node (91, "91:Fact = NUM", [Leaf [NUM 2 (1,9)] ])])])])]); 
          Leaf [SEMI ; (1,10)] ; 
          Node 
            (41, "41:DeclStmts2  = DeclStmts", 
             [Node 
                (11, "11:DeclStmts = DeclStmt SEMI DeclStmts2", 
                 [Node 
                    (51, "51:DeclStmt = ID ID InitDefs", 
                     [Leaf [ID float (1,11)] ; Leaf [ID y (1,17)] ; 
                      Node (61, "61:InitDefs =  EPSILON", [])]); 
                  Leaf [SEMI ; (1,18)] ; 
                  Node 
                    (41, "41:DeclStmts2  = DeclStmts", 
                     [Node 
                        (11, "11:DeclStmts = DeclStmt SEMI DeclStmts2", 
                         [Node 
                            (51, "51:DeclStmt = ID ID InitDefs", 
                             [Leaf [ID int (1,19)] ; Leaf [ID k (1,23)] ; 
                              Node 
                                (71, "71:InitDefs = EQ Exp", 
                                 [Leaf [EQ = (1,25)] ; 
                                  Node 
                                    (73, "73:Exp = Term ADD Term", 
                                     [Node 
                                        (74, "74:Term = Fact", 
                                         [Node 
                                            (81, "81:Fact = ID", 
                                             [Leaf [ID x (1,27)] ])]); 
                                      Leaf [ADD + (1,29)] ; 
                                      Node 
                                        (74, "74:Term = Fact", 
                                         [Node 
                                            (91, "91:Fact = NUM", 
                                             [Leaf [NUM 3 (1,31)] ])])])])]); 
                          Leaf [SEMI ; (1,32)] ; 
                          Node (31, "31:DeclStmts2  = EPSILON", [])])])])])])]) 
 
> let ast0 = embodyStToAST0 edst;; 
 
val ast0 : DecAST0 list = 
  [InitDecAST0 ("int",(1, 1),"x",(1, 5),IntExpAST0 ("2",(1, 9))); 
   SimpleDecAST0 ("float",(1, 11),"y",(1, 17)); 
   InitDecAST0 
     ("int",(1, 19),"k",(1, 23), 
      OpExpAST0 (VarExpAST0 ("x",(1, 27)),IntExpAST0 ("3",(1, 31)),PlusOPAST0))] 
 
> let symtbl = new  SymbolTable () 
symtbl.initTypeSystem() 
mkSymtbl symtbl ast0 
printfn "%A" (symtbl.ToString());; 
 
"int" (1, 1) は 参照 ref:"int" として解決しました。 
変数 "x" (1, 5)を定義しました 
"float" (1, 11) は 参照 ref:"float" として解決しました。 
変数 "y" (1, 17)を定義しました 
"x" (1, 27) は 型名 intへの参照として解決しました。 
"int" (1, 19) は 参照 ref:"int" として解決しました。 
変数 "k" (1, 23)を定義しました 
"Some(global) 
 "int" int  
 "float" float  
 "x" <x:int>  
 "y" <y:float>  
 "k" <k:int>  
 
val symtbl : SymbolTable = 
  Some(global) 
 "int" int  
 "float" float  
 "x" <x:int>  
 "y" <y:float>  
 "k" <k:int>  
 
次回をこれをwindowsソフト化します。 
 
今回のコードは次の通りです。 

続きを読む

スポンサーサイト

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

プロフィール

T GYOUTEN

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

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

この人とブロともになる

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