スポンサーサイト

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

F#で入門 コンパイラ、インタプリタ編 LL(1) first集合 follow集合

 今回は前回の続きで、前回に定義した関数等は引き続き使用します。 
 
「トークンの列が与えられたとき、これから導出できる終端記号列のうちで、先頭の記号として現れえる終端記号の集合」を、そのトークン列のfirst集合というのでしたが、今回はこれを求める関数を定義します。 
nullableの時と同じように求める目標のMap(非終端記号からfirst集合への対応)をin_ntnFirstSetMapという名前の引数として、これを更新していくことによって求めます。 
 
まずトークン一つ用です。εの場合は空集合、終端記号の場合はそれ自身、非終端記号の場合は引数のマップをつかって値を返します。 
 
> 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];; 
 
val getFirstSetOfToken : 
  Set<string> * Set<string> -> 
    Map<string,Set<string>> -> string -> Set<string> 
 
次にトークンがリストで表されている場合です。このリストの要素を最初から見て行って、 
(1)要素のnullableがtrueなら,その要素のFirstSetと、残りのリストのFirstSetを合わせて返す。 
(2)要素のnullableがfalseなら、その要素のFirstSetを返す。 
という行為を再帰的に定義します。 
次の様になります。 
 
> 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;; 
 
val getFirstSetOfTokenLst : 
  Set<string> * Set<string> -> 
    Map<string,bool> -> Map<string,Set<string>> -> string list -> Set<string> 
     
それでは目標のfirst集合を返す関数です。nullableと同じ手法でfirst集合を求めます。 
 
> let getNTN_FirstMap  (inStrLst:list<string>) = 
     
    let (ntnSet,tnSet) = getNTN_TN__Sets inStrLst 
    let ntnNullableMap = getNTN_NullableMap inStrLst 
 
    let grams = inStrLst 
                  |> List.map splitOneLineGram 
                  |> List.map (fun (_,lh,rhEles) -> (lh,rhEles)) //[("Program",["DeclStmts";"PrintStmts"]);("DeclStmts",["VAR";"SEMI"])] 
     
    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;; 
 
val getNTN_FirstMap : string list -> Map<string,Set<string>> 
 
(実行例) 
> getNTN_FirstMap testStrLst;; 
val it : Map<string,Set<string>> = 
  map 
    [("DeclStmt", set ["INT"]); ("DeclStmts", set ["INT"]); 
     ("DeclStmts2", set ["INT"]); ("PrintStmt", set ["EX"]); 
     ("PrintStmts", set ["EX"]); ("Program", set ["INT"]); 
     ("VarDefs", set ["ID"]); ("VarDefs2", set ["COMMA"]); 
     ("VarRefs", set ["ID"]); ...] 
 
次にFollow集合に入ります。 
 
Follow集合はある非終端記号の後に続いて現れうる終端記号の集合です。 
例えば 
nonTerminal1 = ...... 
nonterminal2 = .... nonTerminal1 terminal0 
であるならterminal0はnonTErminal1のfollow集合に含まれます。 
 
nonTerminal1のfollow集合を求めるには、右辺でnonTerminal1を呼び出しているものを、調べてその続きが何になるか調べる必要があります。  
Xを右辺で呼び出しているのがY = ...Xβだけであれば、 
Xのfollow集合はβがnullabeでないときはFirst(β)、nullableのときはFirst(β)とFollow(Y)の和集合となります。(更にYを呼び出している構文まで調べにいく必要があるという訳です。) 
一般にはXを右辺で呼び出しているものそれぞれについて上の関係より集合を求め、それらを足し合わせます。 
 
ではコードですが、まず非終端記号名を与えてそれより後にあるトークンのリストと左辺の非終端記号名を返す関数を定義します。 
 
> 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 [];; 
 
val getAfterTokens : 
  string -> string * string list -> (string list * string) list 
 
(実行例) 
> getAfterTokens "DeclStmts1" ("PrintStmts1",["VarDef1";"DeclStmts1";"VarDef2";"VarDef3";"DeclStmts1";"VarDef4"]);; 
 
val it : (string list * string) list = 
  [(["VarDef4"], "PrintStmts1"); 
   (["VarDef2"; "VarDef3"; "DeclStmts1"; "VarDef4"], "PrintStmts1")] 
 
非終端記号からfollow集合へのMapを返す関数を定義します。 
 
> let getNTN_FollowMap  (inStrLst:list<string>) = 
    let (ntnSet,tnSet) = getNTN_TN__Sets inStrLst 
    let ntnNullableMap = getNTN_NullableMap inStrLst 
    let ntnFirstMap = getNTN_FirstMap inStrLst 
    let isNullableTokensLstPA (tokenLst:list<string>) = isNullableTokenLst (ntnSet,tnSet) ntnNullableMap tokenLst 
    let getFirstSetOfTokenLstPA (tokenLst:list<string>) = getFirstSetOfTokenLst (ntnSet,tnSet) ntnNullableMap  ntnFirstMap tokenLst 
    let grams = inStrLst 
                  |> List.map splitOneLineGram 
                  |> List.map (fun (_,lh,rhEles) -> (lh,rhEles)) //[("Program",["DeclStmts";"PrintStmts"]);("DeclStmts",["VAR";"SEMI"])] 
  
    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 ;; 
 
val getNTN_FollowMap : string list -> Map<string,Set<string>> 
 
(実行例) 
> getNTN_FollowMap testStrLst;; 
val it : Map<string,Set<string>> = 
  map 
    [("DeclStmt", set ["SEMI"]); ("DeclStmts", set ["EOF"; "EX"]); 
     ("DeclStmts2", set ["EOF"; "EX"]); ("PrintStmt", set ["SEMI"]); 
     ("PrintStmts", set ["EOF"]); ("Program", set ["EOF"]); 
     ("VarDefs", set ["SEMI"]); ("VarDefs2", set ["SEMI"]); 
     ("VarRefs", set ["SEMI"]); ...] 
      
 
スポンサーサイト

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

コメントの投稿

非公開コメント

プロフィール

T GYOUTEN

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

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

この人とブロともになる

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