スポンサーサイト

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

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ソフトを作ります。 
今回の全コードは次の通りです。 
 open System 
open System.Text.RegularExpressions    
 
//文法定義のエラー 
exception MyGramExcp of string 
 
let STR_EPS ="EPSILON" 
 
//引数分の空白文字を作る補助関数 
let spaceStr(i) =  
    let sb = new System.Text.StringBuilder() 
    let rec addSpace count = 
        if count = i then sb.ToString() 
        else 
            sb.Append(" ") |> ignore 
            addSpace (count + 1) 
    addSpace 0  
 
////////////////////////////////////////////////////////////////////////////////////////////////////////////////// 
 
type Token(kind:string,img:string,row:int,col:int) = 
    member this.Kind = kind 
    member this.Img = img 
    member this.Row = row 
    member this.Col = col 
 
    override this.ToString() = 
        sprintf "[%s %s (%d,%d)] " kind img row col 
 
//一行をトークン化したときの結果用の型 
type TokenizeOneLineResult = 
    |TOLSuccess of list<Token> 
    |TOLFail of int*int //トークン化失敗したときの行と列 
 
    member this.IsSuccess () = 
        match this with 
        |TOLSuccess(_) -> true 
        | _ -> false 
 
 
type LR0ItemType = int * int * string * string * string * string list 
//                (1,3, "Program", "RPAR", "NULL", ["LPAR"; "Seq"; "RPAR"; "@"]) 
//タプルの第二成分は同一構文規則内の通し番号、一つ大きいのがマーカーを一つ後ろにずらしたもの 
 
type LR1ItemType = LR0ItemType*Set<string> //Set<string>は先読み記号 
//例 ((3, 1, "Exp", "NULL", "Exp", ["@"; "Exp"; "ADD"; "Term"]),["EOF"]) 
 
//StateとしてはLR0と同じものを使用 
type LR0State = 
    SHIFT of int  //構文番号(オートマトンの番号) 
    |REDUCE of int*int*string //構文番号(オートマトンの番号ではない)* 還元項の右辺の要素数(@は含まない)* 構文の左辺の非終端名 
    |ACCEPT 
 
              //文法番号スタック*入力トークン種別の残り 
type anaState = list<int>*list<string> 
 
 
//具象構文木 
type embodyST = 
    |EPS_Leaf of Token //tokenは存在しないので、εの直後のtokenを与える 
    |Leaf of Token  
    |Node of (int* string * list<embodyST>) //intは構文規則番号,stringは "(1, "Program", ["DeclStmts"; "PrintStmts"])"等 
 
    //表示用 
    member this.dispStr (inc :int)  = //inc = インシデント 
            match this with 
            |EPS_Leaf (token) 
                -> spaceStr(inc) +  "ε" + (sprintf "(%d,%d)の前" token.Row token.Col ) + "\r\n" 
            |Leaf(token) 
                -> spaceStr(inc) +  token.ToString() + "\r\n"  
            |Node(index,str,lst)  
                -> spaceStr(inc) + (sprintf "(%d)" index) + str + "\r\n"  
                   + List.fold (fun state (ele:embodyST) -> state + (ele.dispStr (inc + 4)) ) "" lst  
 
///////////////////////////////// 
 
type LR1TokenizeAndParse (inDefLst:list<string*string>, inStrLst:list<string>) = 
 
    let initStrLst = "0:Z = Program EOF" :: inStrLst 
    let initDefLst =  ("EOF","EOF"):: inDefLst 
 
    let makeTokenizeRules (inDefLst:list<string*string>) = 
        inDefLst 
            |> List.map(fun (name,rgText) ->(name,(new Regex ( @"^(?<sPart>\s*)(?<parts>" + rgText + @")")))) 
 
    let tokenizeTopPart (textPart:string) (trl:list<string*Regex>) (row:int) (col:int) = 
        trl 
          |>List.fold (fun (curToken:Token,curLongestLength:int) (name,rg) -> 
                            let wholeMatch = rg.Match(textPart) 
                            let partMatch = wholeMatch.Groups.["parts"]  //必要な部分 
                            let sPartMatch = wholeMatch.Groups.["sPart"] //先頭の空白部分 
                            if wholeMatch.Value.Length > curLongestLength then //最長マッチ 
                                (new Token(name,partMatch.Value,row, col + sPartMatch.Value.Length),wholeMatch.Value.Length ) 
                            else 
                                (curToken,curLongestLength) 
                      ) 
                      (new Token("","",0,0),0) 
 
 
    let tokenizeOneLine (inDefLst:list<string*string>) (inRow:int) (inOneLineStr:string) = 
        let trs = makeTokenizeRules inDefLst 
        let rec tokenizeOneLineSub (curCol:int) (remainStr:string) res = 
            if remainStr.Trim().Length = 0 then 
                TOLSuccess(List.rev res) 
            else 
               let (slicedToken,length) = tokenizeTopPart remainStr trs inRow curCol 
               if length = 0 then 
                    let topBlankNum = remainStr.Length - remainStr.TrimStart().Length 
                    TOLFail(inRow,curCol+topBlankNum) 
               else 
                  tokenizeOneLineSub (curCol + length) (remainStr.Substring(length)) (slicedToken::res)        
        tokenizeOneLineSub 1 inOneLineStr [] 
 
    let tokenizer  (source:list<string>) = 
        let oneLineTokenizer = tokenizeOneLine initDefLst 
        let isTOLSuccess (x:TokenizeOneLineResult) = 
            match x with 
            |TOLSuccess(_) -> true 
            |_             -> false 
        let sucLst,failLst = 
            source 
            |>List.map (fun str -> str.TrimEnd()) 
            |>List.mapi (fun i str -> oneLineTokenizer (i+1) str ) 
            |>List.partition (fun tr -> tr.IsSuccess () ) 
        if failLst.Length > 0 then  
            failwith (sprintf "%A" failLst) 
        else  
            sucLst 
              |>List.map (fun tolr -> match tolr with 
                                         |TOLSuccess(tol) -> tol 
                                         | _ -> failwith "error" //これは起こらない 
                         ) 
              |>List.fold (fun s lst -> s @ lst) [] 
         
    let splitOneLineGram (inStr:string)= 
        let (lhdIndex,rhd) =  
            match inStr.Split([|':'|]) with 
            [|mlhd;mrhd|]  ->  (mlhd.Trim(),mrhd) 
            | _             ->  raise <| MyGramExcp(inStr)  
        let (lhd,rhd2) = 
            match rhd.Split([|'='|]) with 
            |[|mlhd;mrhd|]  ->  (mlhd.Trim(),mrhd) 
            | _             ->  raise <| MyGramExcp(inStr)  
        let rhdElems =  
            rhd2.Split([|' '|]) 
                |> List.ofArray 
                |> List.map (fun s -> s.Trim()) 
                |> List.filter (fun s -> s <> "") 
        (System.Int32.Parse(lhdIndex),lhd,rhdElems) 
 
 
    let getNTN_TN__Sets (inStrLst:list<string>) = 
        let (sumUpLhdSet,sumUpRhdSet) = 
            inStrLst 
                |> List.map splitOneLineGram 
                |> List.fold (fun (acclh,accrh)  (_,lhd,rhdLst) -> (lhd :: acclh,rhdLst @ accrh)) ([],[]) 
                |> (fun (hdLst,rhLst) -> (Set.ofList hdLst, Set.ofList rhLst)) 
        (sumUpLhdSet,sumUpRhdSet - sumUpLhdSet - (Set.ofList [STR_EPS])) 
 
    let (ntnSet,tnSet) =  getNTN_TN__Sets initStrLst   
 
 
    let isNullableToken ((in_ntn,in_tn):Set<string>*Set<string>) (in_ntnNullableMap:Map<string,bool>)(inTokenName:string) = 
        if inTokenName = STR_EPS then  
             true 
        elif Set.contains inTokenName in_tn then 
             false 
        else 
            in_ntnNullableMap.[inTokenName] 
 
    let isNullableTokenLst ((in_ntn,in_tn):Set<string>*Set<string>) (in_ntnNullableMap:Map<string,bool>)(inTokenNameLst:list<string>) = 
          List.forall (isNullableToken (in_ntn,in_tn) in_ntnNullableMap )inTokenNameLst //リスト中のすべてのtokenがnullableか 
           
    let isNullableTokenLstLst ((in_ntn,in_tn):Set<string>*Set<string>) (in_ntnNullableMap:Map<string,bool>)(inTokenNameLstLst:list<list<string>>) = 
          List.exists (isNullableTokenLst (in_ntn,in_tn) in_ntnNullableMap ) inTokenNameLstLst//リスト中のどれかのtokenリストがnullableか 
 
    let grams = initStrLst 
                    |> List.map splitOneLineGram 
                    |> List.map (fun (_,lh,rhEles) -> (lh,rhEles)) //[("Program",["DeclStmts";"PrintStmts"]);("DeclStmts",["VAR";"SEMI"])] 
  
    let getNTN_NullableMap (inStrLst:list<string>) = 
     
    
        let rec getNTN_NullableMapSub (inOldNullableMap:Map<string,bool>) (count:int) =  
            let nextNullableMap = 
                ntnSet 
                    |> Set.fold (fun stateMap ele -> 
                                    let targetGramsLstLst = 
                                        grams 
                                            |>List.filter (fun (ntnName,_) -> ntnName = ele) 
                                            |>List.map (fun (_,lst) -> lst) 
                                    let thisEleNullable = 
                                        isNullableTokenLstLst(ntnSet,tnSet) inOldNullableMap targetGramsLstLst 
                                    Map.add ele thisEleNullable stateMap 
                                 ) 
                                 Map.empty 
            if count > 10000 then 
                failwith "count error" 
            elif nextNullableMap = inOldNullableMap then 
                nextNullableMap 
            else 
                getNTN_NullableMapSub nextNullableMap (count + 1) 
     
        let initNullableMap = 
                    ntnSet 
                        |> Set.map (fun ele -> (ele,false)) 
                        |> Map.ofSeq 
     
        getNTN_NullableMapSub initNullableMap 0 
 
 
    let ntnNullableMap = getNTN_NullableMap initStrLst 
 
 
    let getFirstSetOfToken ((in_ntn,in_tn):Set<string>*Set<string>) (in_ntnFirstSetMap:Map<string,Set<string>>)(inTokenName:string) = 
        if inTokenName = STR_EPS then  
             Set.empty 
        elif Set.contains inTokenName in_tn then 
             Set.ofList ([inTokenName]) 
        else 
            in_ntnFirstSetMap.[inTokenName] 
 
    let getFirstSetOfTokenLst ((in_ntn,in_tn):Set<string>*Set<string>) (in_ntnNullableMap:Map<string,bool>) 
                               (in_firstSetMap:Map<string,Set<string>>) (inTokenNameLst:list<string>) = 
          let isNullableTokenPartApply = isNullableToken (in_ntn,in_tn) in_ntnNullableMap    
       
          let rec getFirstSetOfTokenLstSub (tokenLst:list<string>)  = 
            match tokenLst with 
            |[] -> Set.empty 
            |hd::tl when isNullableTokenPartApply hd -> (getFirstSetOfToken (in_ntn,in_tn) in_firstSetMap hd) + (getFirstSetOfTokenLstSub tl) 
            |hd::tl                                  -> (getFirstSetOfToken (in_ntn,in_tn) in_firstSetMap hd) 
 
          getFirstSetOfTokenLstSub inTokenNameLst 
 
    let getFirstSetOfTokenLstLst ((in_ntn,in_tn):Set<string>*Set<string>) (in_ntnNullableMap:Map<string,bool>) 
                              (in_firstSetMap:Map<string,Set<string>>) (inTokenNameLstLst:list<list<string>>) =   
 
        let getFirstSetOfTokenLstPartApply = getFirstSetOfTokenLst (in_ntn,in_tn) in_ntnNullableMap in_firstSetMap 
     
        List.fold (fun acc ele -> acc + (getFirstSetOfTokenLstPartApply ele)) Set.empty inTokenNameLstLst 
 
    let getNTN_FirstMap  (inStrLst:list<string>) = 
     
        let FisrtSetOfTokenLstLstPA = getFirstSetOfTokenLstLst (ntnSet,tnSet) ntnNullableMap 
     
        let rec getNTN_FirstMapSub (inOldFirstMap:Map<string,Set<string>>) (count:int) =  
            let nextFirstMap = 
                ntnSet 
                    |> Set.fold (fun stateMap ele -> 
                                    let targetGramsLstLst = 
                                        grams 
                                            |>List.filter (fun (ntnName,_) -> ntnName = ele) 
                                            |>List.map (fun (_,lst) -> lst) 
                                    let thisEleFisrtSet = 
                                         FisrtSetOfTokenLstLstPA inOldFirstMap targetGramsLstLst 
                                    Map.add ele thisEleFisrtSet stateMap 
                                 ) 
                                 Map.empty 
            if count > 10000 then 
                failwith "count error" 
            elif nextFirstMap = inOldFirstMap then 
                nextFirstMap 
            else 
                getNTN_FirstMapSub nextFirstMap (count + 1) 
     
        let initFirstMap = 
                    ntnSet 
                        |> Set.map (fun ele -> (ele,Set.empty)) 
                        |> Map.ofSeq 
     
        getNTN_FirstMapSub initFirstMap 0 
 
    let ntnFirstMap = getNTN_FirstMap initStrLst 
     
    let getAfterTokens (inStr:string) ((lhdStr,rhStrLst):string*list<string>) = 
        let rec getAfterTokensSub strLst res = 
            match strLst with 
            |hd::tl when hd = inStr -> getAfterTokensSub tl ((tl,lhdStr)::res) 
            |hd::tl                 -> getAfterTokensSub tl res 
            | [] -> res 
        getAfterTokensSub rhStrLst [] 
     
    let getNTN_FollowMap  (inStrLst:list<string>) = 
        let isNullableTokensLstPA (tokenLst:list<string>) = isNullableTokenLst (ntnSet,tnSet) ntnNullableMap tokenLst 
        let getFirstSetOfTokenLstPA (tokenLst:list<string>) = getFirstSetOfTokenLst (ntnSet,tnSet) ntnNullableMap  ntnFirstMap tokenLst 
  
        let rec getNTN_FollowMapSub (inOldFollowMap:Map<string,Set<string>>) (count:int) =  
           let getFollowSet (afterTokens:list<string>,ntnName:string) = 
                    if isNullableTokensLstPA afterTokens then 
                        (getFirstSetOfTokenLstPA afterTokens) + (inOldFollowMap.[ntnName]) 
                    else 
                        (getFirstSetOfTokenLstPA afterTokens)                 
           let nextFollowMap = 
                ntnSet 
                    |> Set.fold (fun stateMap ele -> 
                                    let includeEleGrams = 
                                        grams 
                                          |> List.fold (fun state2 (ntnName2,tokenLst) 
                                                            -> state2 @ (getAfterTokens ele (ntnName2,tokenLst))) 
                                                        [] 
                                                     
                                    let followSet = 
                                        includeEleGrams 
                                          |> List.fold (fun (state3:Set<string>) (afterTokens,ntnName) -> 
                                                        state3 + (getFollowSet (afterTokens,ntnName))) 
                                                        Set.empty 
                                    Map.add ele followSet stateMap 
                                 ) 
                                 Map.empty 
           if count > 10000 then 
                failwith "count error" 
           elif nextFollowMap = inOldFollowMap then 
                nextFollowMap 
           else 
                getNTN_FollowMapSub nextFollowMap (count + 1) 
 
 
        let initFollowMap = 
                    ntnSet 
                        |> Set.map (fun ele -> (ele,Set.empty)) 
                        |> Map.ofSeq 
     
        getNTN_FollowMapSub initFollowMap 0 
     
    let ntnFollowMap = getNTN_FollowMap initStrLst 
 
    ///////////////////////////////////////////LR1部分//////////////////////////////////////////////////////////////////////// 
    //マーカーを付けて、マーカーの前後の記号とそれのタプルを返す 
    let addMarkers (idNum:int, lhName:string, inLst:list<string>) = 
        if inLst = [STR_EPS] then 
            [(idNum,1,lhName,"NULL","NULL",["@"])] 
        else 
            let withSenti ="NULL"::inLst @ ["NULL"] 
            let rec addMarkerSub (lst:list<string>) (acchd:list<string>) accLst (counter) = 
                match lst with 
                |hd::tl when tl <> []  
                    -> addMarkerSub tl (acchd @ [hd]) ((idNum,counter,lhName,hd, List.head tl,((acchd @ [hd] @ ["@"] @ tl)))::accLst) (counter+1) 
                |_ ->  accLst |> List.map (fun (id,cnt,lh,bef,aft,resLst) -> (id,cnt,lh,bef,aft,resLst |> List.rev |> List.tail |> List.rev |> List.tail)) 
     
            List.rev (addMarkerSub withSenti [] [] 1) 
 
    let getGramWithMarker (inStr:string) = 
        splitOneLineGram inStr   
          |> addMarkers 
 
    let getLR1Terms (inStrLst:list<string>) = 
       let (ntnSet,ntSet) = getNTN_TN__Sets  inStrLst 
       let lr0TermsSet = 
            inStrLst 
                |> List.map getGramWithMarker 
                |> List.concat 
                |> Set.ofList 
       let shiftItemsSet = //markerの直後が終端記号 
            Set.filter (fun (_,_,_,_,aft,_) -> Set.contains aft ntSet) lr0TermsSet 
       let reduceItemsSet = //markerが末尾 
            Set.filter (fun (_,_,_,_,aft,_) -> aft = "NULL") lr0TermsSet 
       let topMarker_ItemsSet = //markerが先頭 
           Set.filter (fun (_,_,_,bfr,_,_) -> bfr = "NULL") lr0TermsSet 
    
       let ntnAfterMarkerItemsSet = //markerの直後が非終端記号 
          Set.filter (fun (_,_,_,_,aft,_) -> Set.contains aft ntnSet) lr0TermsSet 
   
    
       let lr0TItemsMap = 
         lr0TermsSet  
            |> Set.map (fun (id,subId,lhName,bfr,aft,lst) -> ((id,subId),(id,subId,lhName,bfr,aft,lst))) 
            |> Map.ofSeq   
 
    
       //markerの直後が非終端記号のものについては、その要素とmarkerの直後の非終端記号の後のリストを組にする 
       //補助関数 
       let rec ntnAMSub lst  = 
            match lst with 
            |hd::tl when hd = "@" -> List.tail tl 
            |hd::tl -> ntnAMSub tl  
            | [] -> failwith "neverOccurableError" 
    
       let rec makeMap inLst accMap = 
            match inLst with 
            |[] -> accMap 
            |(id,subId,_,_,_,lst)::tl ->makeMap tl (Map.add (id,subId) (ntnAMSub lst) accMap) 
 
 
       let idSubId2AfterAfterMarkerMap = makeMap (List.ofSeq ntnAfterMarkerItemsSet) Map.empty 
       
       (lr0TermsSet,shiftItemsSet,reduceItemsSet,topMarker_ItemsSet,ntnAfterMarkerItemsSet,lr0TItemsMap,idSubId2AfterAfterMarkerMap) 
 
 
    let getClosure  ((in_ntn,in_tn):Set<string>*Set<string>) (in_ntnNullableMap:Map<string,bool>) 
                    (in_firstSetMap:Map<string,Set<string>>)  
                    (inIdSubId2AfterAfterMarkerMap:Map<(int * int),string list>) (inNtnAfterMarkerItemsSet:Set<LR0ItemType>)  
                    (inTopMarker_ItemSet:Set<LR0ItemType>) (initI :Set<LR1ItemType>) = 
        let rec getClosureSub oldClosureSet = 
                                      //oldClosureSetの中で非終端記号の前にマーカーがついている形のもの 
            let shouldAddedLR1Items  = Set.filter (fun (ele,_) -> Set.contains ele inNtnAfterMarkerItemsSet) oldClosureSet 
            let newClosureSet = 
                Set.fold  (fun oldClosureSet ((id,subId,_,_,aft0,_),lookAheads) -> //aftはマーカーの直後の非終端記号 
                                let addLRItemBases:Set<LR0ItemType> = Set.filter (fun (_,_,lh,_,_,_ ) -> lh = aft0) inTopMarker_ItemSet 
                                let addLR1Items = 
                                    addLRItemBases 
                                      |> Set.map (fun lr0Item -> 
                                                    let afterAfterMarkerLst = inIdSubId2AfterAfterMarkerMap.[(id,subId)]  
                                                    let afterAfterMarkerNullable = 
                                                        isNullableTokenLst (in_ntn,in_tn) in_ntnNullableMap afterAfterMarkerLst 
                                                    let afterAfterMarkerFirst = 
                                                         getFirstSetOfTokenLst (in_ntn,in_tn) in_ntnNullableMap in_firstSetMap afterAfterMarkerLst 
                                                    let addLR1ItemLookAheads = 
                                                          if afterAfterMarkerNullable = true then  
                                                                afterAfterMarkerFirst + lookAheads 
                                                          else 
                                                                afterAfterMarkerFirst 
                                                    (lr0Item,addLR1ItemLookAheads) 
                                                  ) 
                                oldClosureSet + addLR1Items 
                            ) 
                           oldClosureSet 
                           shouldAddedLR1Items 
            if newClosureSet = oldClosureSet then 
                 newClosureSet 
            else  
                getClosureSub newClosureSet 
 
        let res0Lst = List.sort (List.ofSeq (getClosureSub initI))  
         //ここまででは(5, 1, "Term", "NULL", "ID", ["@"; "ID"]), set ["ADD"]);((5, 1, "Term", "NULL", "ID", ["@"; "ID"]), set ["EQ2"] 
        //とまとめるべきものがバラバラになっているのでこれをまとめる。 
 
        let dummyEle = ((-1,-1,"","","",[]),Set.empty) 
    
        let (res,_) =  //最後のdummyEleが_にくる 
              (res0Lst @ [dummyEle]) |>   
              List.fold (fun (acc:Set<LR1ItemType>,(oldlr0Part:LR0ItemType,oldLookAheadsPart:Set<string>)) (lr0Part:LR0ItemType,lookAhedsPart:Set<string>) 
                                    ->if oldlr0Part = lr0Part then 
                                            (acc, (oldlr0Part,oldLookAheadsPart + lookAhedsPart)) 
                                      else       
                                            ((Set.add (oldlr0Part,oldLookAheadsPart) acc),(lr0Part,lookAhedsPart)) 
                            ) 
                 (Set.empty,dummyEle) 
 
      
        Set.filter (fun ((a,_,_,_,_,_),_) -> a <> -1) res //最初のdummyEleを除く(これがgetClosureの返り値) 
 
 
    let getGoto  ((in_ntn,in_tn):Set<string>*Set<string>) (in_ntnNullableMap:Map<string,bool>) 
                    (in_firstSetMap:Map<string,Set<string>>)  
                    (inIdSubId2AfterAfterMarkerMap:Map<(int * int),string list>) (inNtnAfterMarkerItemsSet:Set<LR0ItemType>)  
                    (inTopMarker_ItemSet:Set<LR0ItemType>)  (inIRItemMap:Map<(int*int),LR0ItemType>) 
                    (inLR1ItemSet:Set<LR1ItemType>) (inStr:string) = 
 
 
        let getClosurePA = getClosure (in_ntn,in_tn) in_ntnNullableMap in_firstSetMap inIdSubId2AfterAfterMarkerMap 
                                        inNtnAfterMarkerItemsSet inTopMarker_ItemSet 
        let shouldAddGredienceLR1Items = Set.filter (fun ((_,_,_,_,aft,_),_) -> aft = inStr) inLR1ItemSet  
        let tempSet = //マーカーをずらしたものの集合 
                shouldAddGredienceLR1Items 
                    |> Set.fold (fun accSet ((i,j,_,_,_,_),lookAheads) ->   
                                    let addItemLR0Part = inIRItemMap.[(i,j+1)] //(マーカーを一つ進めたもの(マーカーの次はinStr))  
                                    let addLR1Item = (addItemLR0Part,lookAheads) 
                                    Set.add addLR1Item accSet   
                                ) 
                       Set.empty  
     
        getClosurePA tempSet 
 
 
    let makeLR1Map (inGrams:list<string>) = 
     
        let (ntnSet,tnSet) = getNTN_TN__Sets  inGrams 
        let wholeNtnAndTnLst = List.ofSeq(ntnSet + tnSet) 
        let (whole,shift,reduce,topM,ntnAftM,lr0TItemsMap,idSubId2AfterAfterMarkerMap) = getLR1Terms inGrams 
     
        let (ntn,tn) = getNTN_TN__Sets inGrams 
        let ntnNullableMap = getNTN_NullableMap inGrams 
        let firstSetMap = getNTN_FirstMap inGrams 
 
        //受理状態のみを含むClosureか  
        let isFinalLR1Item (cls:Set<LR1ItemType>)  =  
               (Set.exists (fun ((_,_,lh,bfr,aft,_),_) ->lh = "Z" && bfr = "Program" && aft = "EOF") cls)  && (Set.count cls = 1) 
 
 
        //引数のmapに受理状態のみを含むClosureについてEOFの欄だけの項を付け加えて返す。(「noは受理状態のみを含むClosure」の番号を渡す) 
        let addFinalRow2map (idNo:int) (seedMap:Map<int*string,LR0State>) = 
               List.fold  (fun stateMap ele -> 
                                if ele <> "EOF" then stateMap  //なにもマップに付け加えない。 
                                else Map.add (idNo,"EOF") ACCEPT stateMap 
                          ) 
                          seedMap 
                          wholeNtnAndTnLst 
 
        let getGotoPA = getGoto (ntn,tn) ntnNullableMap firstSetMap idSubId2AfterAfterMarkerMap ntnAftM topM lr0TItemsMap 
 
 
        let rec makeMapSub (ntn_tnLst:List<string>) (curProcessingClsNo:int) (curExistClsNum:int)  
                           (accCls2IdMap:Map<Set<LR1ItemType>,int>) (accId2ClsMap:Map<int,Set<LR1ItemType>>)  
                           (accMap:Map<int*string,LR0State>) = 
            //表の右下まで到達 
            if ntn_tnLst = [] && curProcessingClsNo = curExistClsNum then  
                    (accId2ClsMap,accMap) 
            //表の右端まで到達 
            elif ntn_tnLst = [] && curProcessingClsNo < curExistClsNum then 
                    makeMapSub wholeNtnAndTnLst (curProcessingClsNo + 1)  curExistClsNum  accCls2IdMap accId2ClsMap accMap 
            //受理状態のみを含むClosureの左端の場合 
            elif  isFinalLR1Item  accId2ClsMap.[curProcessingClsNo] = true then  
                    let addedMap = addFinalRow2map curProcessingClsNo accMap 
                    makeMapSub wholeNtnAndTnLst (curProcessingClsNo + 1) curExistClsNum  accCls2IdMap accId2ClsMap addedMap 
            //一般状態 
            else     
               match ntn_tnLst with 
                |[] -> //右端に来る場合は最初の2つの場合でチェック済み 
                    failwith "neverOccurable Error" 
                |hd::tl -> 
                    //還元の可能性を調べる(ここの扱いがSLRと異なる) 
                    let reduceItems = 
                       accId2ClsMap.[curProcessingClsNo] 
                        |> Set.filter (fun ((_,_,_,_,aft,_),lookAheads) -> aft = "NULL" && Set.contains hd lookAheads ) 
                    if  Set.count reduceItems > 1 then 
                        failwith (sprintf "還元/還元衝突 %s  %A " hd reduceItems ) 
                 
                    elif Set.count reduceItems = 1 then //還元項がある場合 
                        //シフトの可能性を調べる 
                        let shiftableItems =  
                            accId2ClsMap.[curProcessingClsNo]  
                                |>Set.filter (fun ((_,_,_,_,aft,_),_) -> aft = hd)   
                     
                        if Set.count shiftableItems >= 1 then 
                            failwith (sprintf "シフト/還元衝突 %s  reduceItems = %A \n shiftItem = %A" hd reduceItems shiftableItems ) 
                        else //還元としてMapに追加 
                            match List.head (List.ofSeq reduceItems) with //要素は一個だけ 
                            |((gramNo,_,lhName,_,_,lstWithMarker),_) ->  
                                    makeMapSub tl curProcessingClsNo curExistClsNum accCls2IdMap accId2ClsMap  
                                            (Map.add (curProcessingClsNo,hd) (REDUCE(gramNo,((List.length lstWithMarker) - 1),lhName))  accMap)  
                 
                    else //還元しない場合(シフトもしくは対象なしの場合) 
                        let newGoto = getGotoPA accId2ClsMap.[curProcessingClsNo] hd //処理中のclosureとtermからGoto集合を求める 
                        if newGoto = Set.empty then //行先なし(表として空欄になる)場合(なにも付け加えない) 
                               makeMapSub tl curProcessingClsNo curExistClsNum accCls2IdMap accId2ClsMap accMap 
                        else 
                            match (Map.tryFind newGoto accCls2IdMap) with 
                            //newGotoがすでに、Closureとして存在する場合 
                            |Some(i) -> makeMapSub tl curProcessingClsNo curExistClsNum  
                                                   accCls2IdMap accId2ClsMap (Map.add (curProcessingClsNo,hd)  (SHIFT(i)) accMap) 
                            //newGotoがまだ、Closureとして存在しない場合 
                            |None    ->let newAccCls2IdMap = Map.add newGoto (curExistClsNum + 1) accCls2IdMap 
                                       let newAccId2ClsdMap = Map.add (curExistClsNum + 1) newGoto accId2ClsMap 
                                       makeMapSub tl curProcessingClsNo (curExistClsNum + 1)  
                                                   newAccCls2IdMap newAccId2ClsdMap (Map.add (curProcessingClsNo,hd)  (SHIFT(curExistClsNum + 1)) accMap)  
 
 
        let initI = ((0,1, "Z", "NULL", "Program", ["@"; "Program"; "EOF"]),Set.ofList ["EOF"]) 
        let cls1 = getClosure  (ntn,tn) ntnNullableMap firstSetMap idSubId2AfterAfterMarkerMap ntnAftM topM (Set.ofList [initI]) 
        let initAccCls2IdMap = Map.ofList [(cls1,1)] 
        let initId2accCls = Map.ofList [(1,cls1)] 
        makeMapSub wholeNtnAndTnLst 1 1  initAccCls2IdMap initId2accCls Map.empty 
 
 
    //リストからn個の要素をpopして残りを返す補助関数 
    let popN in_lst in_n = 
        let rec popNSub lst count = 
            if count = in_n then 
                lst 
            else 
                popNSub (List.tail lst) (count + 1) 
        popNSub in_lst 0 
 
 
    //リストからn個の要素をpopしてpopしたものと残りを返す補助関数 
    let getPopN in_lst in_n = 
        let rec popNSub lst acc count = 
            if count = in_n then 
                (List.rev acc,lst) 
            else 
                popNSub (List.tail lst) ((List.head lst)::acc) (count + 1) 
        popNSub in_lst [] 0 
 
    /////////////////id2gramRuleMapは構文番号->構文内容へのMap 
    let getTree (id2gramRuleMap:Map<int,string>) (in_idTerm2VLR1Map:Map<int*string,LR0State>) (inTokenLst:list<Token>) = 
         
        let rec getTreeSub  ((stk,rem):anaState) (stkOfTree:list<embodyST>,remOfTree:list<embodyST>)= 
            let curAtmtnst = List.head stk 
            let topRemain = List.head rem 
            let nextMove = Map.tryFind   (curAtmtnst,topRemain) in_idTerm2VLR1Map 
            let topRemainNode = List.head remOfTree 
            match nextMove with 
            |Some(SHIFT(nextAtmtnNo)) -> 
                        getTreeSub (nextAtmtnNo::stk,List.tail rem) (topRemainNode::stkOfTree,List.tail remOfTree) 
             
            |Some(REDUCE(ruleNo,graEleNum,lhName)) -> 
                        let (popNodes,remT) = getPopN stkOfTree graEleNum 
                        getTreeSub (popN stk graEleNum ,lhName::rem) (remT,(Node(ruleNo,id2gramRuleMap.[ruleNo],(List.rev popNodes)))::remOfTree) 
            |Some(ACCEPT)->      //終了の場合は状態を変えない 
                    List.head stkOfTree 
            |None   -> 
                    failwith "ソースが文法にのっとっていません" 
         
        let initTokenKindLst = inTokenLst |> List.map (fun tkn -> tkn.Kind) 
        let initNodeLst = inTokenLst |> List.map (fun tkn -> Leaf(tkn)) 
 
        getTreeSub ([1],initTokenKindLst) ([],initNodeLst) 
 
  
    let id2gramRuleMap = //[(5,"5:Program = DeclStmts PrintStmts");.....という形 
          initStrLst 
            |> List.map (fun s ->  
                            let (no,lhName,_) = splitOneLineGram s 
                            (no,s) 
                        ) 
            |> Map.ofList 
 
    //このMapを使ってトークン列を解析する 
    let (_,lr1Map) = makeLR1Map initStrLst 
    let getTreePA = getTree id2gramRuleMap lr1Map 
 
    member this.GetTokens (sourceLst:list<string>) =   
        tokenizer sourceLst   
 
 
    member this.GetEBASTtree (sourceLst:list<string>) =   
        let forTokenizedLst =  sourceLst @ ["EOF"] 
        let tokens = tokenizer forTokenizedLst 
        getTreePA tokens 
 
///////////////type LR1TokenizeAndParse end/////////////////////////////////////////////////////////////////////////// 
 
 
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"; 
 
    ] 
 
 
//抽象木 
 
type PosAST0 = int*int //ソース内の位置 
 
                 
type ExpAST0 =  
     |VarExpAST0 of string * PosAST0    
     |IntExpAST0 of string * PosAST0 
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 
  
and BodyStmtAST0 = 
    |VarDecStmtAST0 of VarDecElesAST0  
    |CallFuncAST0 of string * PosAST0 * list<ExpAST0> //funcName funcPos argList 
    |BlockStmtAST0 of list<BodyStmtAST0>   
 
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 ") 
 
 
//let tp1 = new LR1TokenizeAndParse (tnR1,grammersStrLst1) 
// 
//let src0 = ["int x ;void f(int k,int u){int y;{int i = y ;f(3);} {int j;}}; void g(int z) {int i;};"] 
// 
//let edst = tp1.GetEBASTtree(src0) 
//let ast0 = embodyStToAST0 edst 
//printfn "%A" ast0 
 
//Symbolの型(名)を返すインターフェイス 
type IType = 
  interface 
       abstract GetName : unit -> string 
  end 
 
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)を探す  
 
 
type VariableSymbol (name:string,in_sType:option<IType>) = 
    inherit Symbol(name,in_sType) 
 
type BuiltInTypeSymbol (name:string) = 
    inherit Symbol(name,None) 
    interface IType with 
        member this.GetName () = 
            name 
 
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()      
 
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") 
 
 
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()      
     
 
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)   
 
 
 
let tp1 = new LR1TokenizeAndParse (tnR1,grammersStrLst1) 
 
let src0 = ["int x ;void f(int k,int u){int y;{int i = y ;f(3);} {int j;}}; void g(int z) {int i;};"] 
 
let edst = tp1.GetEBASTtree(src0) 
let ast0 = embodyStToAST0 edst 
printfn "%A" ast0 
  
let globalScope = new GlobalScope() 
(globalScope :> IScope).define(new BuiltInTypeSymbol("int")) 
(globalScope :> IScope).define(new BuiltInTypeSymbol("float")) 
(globalScope :> IScope).define(new BuiltInTypeSymbol("void")) 
 
let castedGlobalScope = globalScope :> IScope 
 
let cur_scope = ref castedGlobalScope  
 
let currentScope = mkSymtbl cur_scope ast0 
 
printfn "グローバルスコープ内の登録は次の通りです。\n%A" (currentScope.ToString()) 
スポンサーサイト

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

コメントの投稿

非公開コメント

プロフィール

T GYOUTEN

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

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

この人とブロともになる

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