スポンサーサイト

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

F#で入門 コンパイラ、インタプリタ編 LL(1) nullable

ここからしばらく先読み記号による分岐について考えていきたいと思います。 
例えば 
NonTerminal1 = Terminal1 ...... 
NonTerminal1 = Terminal2 ...... 
という構文規則があり、nonTerminal1 という名前の関数でNonTerminal1に対応するトークンを処理する場合を考えます。この場合は与えられたトークン列の先頭を見て、それがTerminal1であれば1番目の形、Terminal2であれば2番目の形として処理すればよいわけでした。 
 
では 
NonTerminal1 = NonTerminal2 ...... 
NonTerminal1 = NonTerminal3 ...... 
この場合はどうでしょうか。 
この場合は単純に考えるのは難しく、NonTerminal2もNonTerminal3も空列(ε)になる可能性のない場合は、NonTerminal2から導出される可能性のあるトークン列の先頭の非終端記号、と、NonTerminal3から導出される可能性のあるトークン列の先頭の非終端記号の比較になります。 
 
一般に処理すべき残りのトークン列が与えられたときに 
Nonterminal = NonOrOuiTerminal1 NonOrOuiTerminal2 .... NonOrOuiTerminaln 
という構文規則にもとづいた関数が適用可能かどうかを調べるには 
Nonterminalがεになる可能性がないのであれば 
Nonterminal = NonOrOuiTerminal1 NonOrOuiTerminal2 .... NonOrOuiTerminaln 
を終端記号に導出した時に、先頭には何がでる可能性があるかを調べることになります。 
ではNonterminalがεになる可能性がある(つまりNonOrOuiTerminal1,2,..,nがすべてεになる可能性がある)場合はどうでしょうか。 
この場合はNonterminalが呼び出される文脈を考える必要があり 
たとえば 
PrevNonterminal1 = NonOrOuiTerminal  Nonterminal .... 
という文脈でNonTerminalが呼び出されるのであればNonOrOuiTerminalがトークンを消費した次の段階でNonterminalが適用される可能性も考慮にいれる必要があります。 
 
ということで、構文規則すべてを念頭に置いた上で、それぞれの構文要素について、次のようなものを調べる必要がでてきます。 
(1)εになる可能性があるかないか(これをNullableといいます。) 
(2)NonOrOuiTerminal0(非終端記号および終端記号)をすべて終端記号にまで導出したとき、最初にくる可能性のある終端記号はなにか(これをNonOrOuiTerminal0のFirst集合といいます。) 
(導出されるものがない場合は空集合とします。First(ε)=空集合です。) 
(3)非終端記号Ntnがnullableな時に、その非終端記号Ntnを呼び出す可能性のある構文規則それぞれについて、Ntnを呼び出して、Ntnがεに導出された時に、どのような非終端記号がトークン列の最初にある可能性があるか。 
 
(3)はわかりにくいので例で説明します。 
 
(1)Ntn1 = ε 
(2)Ntn1 = TN1 TN2 
(3)Ntn2 = Ntn1 Ntn3 
(4)Ntn2 = Ntn1 Ntn4 
(5)Ntn3 = TN5 TN6 
(6)Ntn4 = TN7 TN8 
 
例えばNtn1に対応する関数を書くことを考えます。 
and ntn1 (remain:list<TokenKind>) = 
       match remain with 
       |TN1::TN2:: ..... ->......... Ntn1が(2)で導出されている場合の処理 
       (次に(1)で導出されている場合を考える) 
        
この(1)で導出されている場合ですがこれはNtn1 = εなので、トークン列の最初には 
Ntn3かNtn4から導出されたトークンが頭にきているばすです。(この場合TN5かTN7が来ている。) 
このようにNtn1が右辺の構成要素になっている構文規則を見つけて、Ntn1の 次の 構成要素が導出された場合の最初の要素と先読み記号を比較する必要があるわけです。 
このように「Ntn1の 次の 構成要素が導出された場合の最初の終端記号」を、すべての構文規則について調べ合わせたものをNtn1のFollow集合といいます。 
 
今から順番にNullable,First集合、Follow集合を調べていきます。 
(最終的にはプログラム化します。) 
 
例の構文規則として次を使用します。(ε(空列)はEPSILONとして表します。) 
構文番号は1以上で、一意であればよいものとします。 
 
1:Program = DeclStmts PrintStmts 
2:DeclStmts = DeclStmt SEMI DeclStmts2 
3:DeclStmts2  = EPSILON 
4:DeclStmts2  = DeclStmts 
5:DeclStmt = INT VarDefs 
6:VarDefs = ID EQ NUM VarDefs2 
7:VarDefs2 = COMMA ID EQ NUM VarDefs2 
8:VarDefs2 = EPSILON 
9:PrintStmts = EPSILON 
10:PrintStmts = PrintStmt SEMI PrintStmts 
11:PrintStmt = EX VarRefs 
12:VarRefs = ID VarRefs2 
13:VarRefs2 = COMMA ID VarRefs2 
14:VarRefs2 = EPSILON 
 
上をlist<string>としたものをテスト用に準備しておきます。 
 
> let testStrLst = 
   ["0:Z = Program EOF";//この行だけ付け加えます。 
    "1:Program = DeclStmts PrintStmts"; 
    "2:DeclStmts = DeclStmt SEMI DeclStmts2"; 
    "3:DeclStmts2  = EPSILON"; 
    "4:DeclStmts2  = DeclStmts"; 
    "5:DeclStmt = INT VarDefs"; 
    "6:VarDefs = ID EQ NUM VarDefs2"; 
    "7:VarDefs2 = COMMA ID EQ NUM VarDefs2"; 
    "8:VarDefs2 = EPSILON"; 
    "9:PrintStmts = EPSILON"; 
    "10:PrintStmts = PrintStmt SEMI PrintStmts"; 
    "11:PrintStmt = EX VarRefs"; 
    "12:VarRefs = ID VarRefs2"; 
    "13:VarRefs2 = COMMA ID VarRefs2"; 
    "14:VarRefs2 = EPSILON"] 
 
返答略 
 
 
非終端記号は左辺に現れるもの、終端記号は出てくる記号すべてから非終端記号とEPSILONを除いたものとします。 
 
自家製エラーとEPSILONを定義しておきます。 
 
> exception MyGramExcp of string 
let STR_EPS ="EPSILON";; 
 
exception MyGramExcp of string 
val STR_EPS : string = "EPSILON" 
 
各行をインデックスと左辺の非終端記号の文字列、右辺の記号の文字列リストのタプルにする関数を定義します。 
 
> 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);; 
 
val splitOneLineGram : string -> int * string * string list 
 
実行例 
> splitOneLineGram "5:Program = DeclStmts PrintStmts";; 
 
val it : int * string * string list = 
  (5, "Program", ["DeclStmts"; "PrintStmts"]) 
   
 
非終端記号と終端記号のSetをタプルで返す関数を定義します。 
 
> 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]));; 
 
val getNTN_TN__Sets : string list -> Set<string> * Set<string> 
 
実行例 
 
> getNTN_TN__Sets testStrLst;; 
val it : Set<string> * Set<string> = 
  (set 
     ["DeclStmt"; "DeclStmts"; "DeclStmts2"; "PrintStmt"; "PrintStmts"; 
      "Program"; "VarDefs"; "VarDefs2"; "VarRefs"; ...], 
   set ["COMMA"; "EQ"; "EX"; "ID"; "INT"; "NUM"; "SEMI"]) 
    
    
さて次はnullable(空列になりうるか)かどうかを返す関数ですが、まずは一つのトークン名(非終端記号もしくは終端記号もしくは空列)を与えられたときにどうかを返す関数を定義します。 
もちろん最初はそれぞれの非終端記号がnullableかどうかは分からないのですが、非終端記号は全部falseであるという仮定で、マップを作成して、これをどんどん更新してゆき、変化しなくなったところで、非終端記号をnullableかどうかに対応させるマップを完成させます。 
手順としては次のようになります。 
 
(1)関係式に含まれるすべての変数に初期値を設定。(どのような初期値をあたえるかは問題次第) 
(2)関係式を右辺から左辺の代入の代入式とみて、現時点での変数の値から左辺の値を計算し、変数の値をUPDATEする。 
(3)(2)をすべての関係式について値が変化しなくなるまで繰り返す。 
 
では更新させる予定のマップをin_ntnNullableMapという引数名で、一つのトークンがnullableかどうかを返す関数を定義してみます。 
 
> 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];; //トークンが非終端記号の場合 
 
val isNullableToken : 
  Set<string> * Set<string> -> Map<string,bool> -> string -> bool 
 
次にトークンのリストを引数の一部として、このリスト全体がnullableかどうかを調べる関数です。 
 
> 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か 
;; 
 
val isNullableTokenLst : 
  Set<string> * Set<string> -> Map<string,bool> -> string list -> bool 
   
次にトークンリストのリストを引数の一部として、このリストの最低一つでもnullableのとき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か 
;; 
 
val isNullableTokenLstLst : 
  Set<string> * Set<string> -> Map<string,bool> -> string list list -> bool 
 
それでは目的の関数で非終端記号とそれがnullableかどうかのMapを返す関数です。 
 
> let getNTN_NullableMap (inStrLst:list<string>) = 
     
    let (ntnSet,tnSet) = getNTN_TN__Sets inStrLst 
     
    let grams = inStrLst 
                  |> List.map splitOneLineGram 
                  |> List.map (fun (_,lh,rhEles) -> (lh,rhEles)) //[("Program",["DeclStmts";"PrintStmts"]);("DeclStmts",["VAR";"SEMI"])] 
     
    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;; 
 
val getNTN_NullableMap : string list -> Map<string,bool> 
 
(使用例) 
> getNTN_NullableMap ["1:Program = DeclStmts SEMI PrintStmts";"2:DeclStmts = EPSILON";"3:PrintStmts = EPSILON";"4:PrintStmts = PRINT"];; 
val it : Map<string,bool> = 
  map [("DeclStmts", true); ("PrintStmts", true); ("Program", false)] 
 
(使用例) 
 
> getNTN_NullableMap testStrLst ;; 
val it : Map<string,bool> = 
  map 
    [("DeclStmt", false); ("DeclStmts", false); ("DeclStmts2", true); 
     ("PrintStmt", false); ("PrintStmts", true); ("Program", false); 
     ("VarDefs", false); ("VarDefs2", true); ("VarRefs", false); ...] 
 
次回はFirst集合とFollow集合を求めてみます。
スポンサーサイト

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

コメントの投稿

非公開コメント

プロフィール

T GYOUTEN

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

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

この人とブロともになる

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