スポンサーサイト

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

F#で入門 コンパイラ 、インタプリタ編 上向き構文解析 LR(0) (2)

 前回は 
a:Z = Program EOF 
b:Program=EX Exp 
c:Exp = NUM 
という文法に対し、右辺に解析途中の位置を表すマーカーを埋め込んだものを考えそれを材料にして構文解析を行いました。これをLR(0)項といいます。(0は先読み記号の数を表します。) 
例えばExp →["@"; "EX"; "Exp"]がLR(0)項です。 
 ["@"; "Program"; "EOF"] という状態は、文法bより ["@"; "EX"; "Exp"] という状態とも考えられます。このような関係を記号↓を用いて、 
  (Program → ["EX"; "@"; "Exp"]) ↓( Exp →["@"; "EX"; "Exp"])と表します。 
  今から紹介するのはLR(0)項から、同じ状態と考えられる(同じ状態である可能性がある)LR(0)項の集合を求める方法です。 
 まず一つのLR(0)項が与えられたとします。 
 (1)このLR(0)項だけが要素の集合をIとします。(これが初期状態) 
 (2)Iに含まれるLR(0)項の中で非終端記号の前にマーカーがついている形のものそれぞれについて 
    文法中で、その非終端記号の定義の右辺の先頭にマーカーをつけたものを追加します。 
  (例えばX→α@Yβで Y→γと定義されているのであればY→@γを追加します。 
   
  あとは(2)を変化がなくなるまで繰り返します。 
   
  これをIのclosureといいます。 
  正確な定義は「{closure(I) = I ∪ { t | i ∈ closure(I), i ↓ t }を満たす最小の集合」という ものです。 
   
  今回は文法からclosureを求めるところまでをやってみます。 
  まずは準備から 
   
> open System    
 
//文法定義のエラー 
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 ["1:Program = DeclStmts PrintStmts";"2:DeclStmts = VAR SEMI";"3:PrintStmts = EPSILON"];; 
val it : Set<string> * Set<string> = 
  (set ["DeclStmts"; "PrintStmts"; "Program"], set ["SEMI"; "VAR"]) 
   
LR(0)の要素を表す型をタプルで定義しておきます。 
> type LR0ItemType = int * int * string * string * string * string list;; 
 
type LR0ItemType = int * int * string * string * string * string list 
 
(1,3, "Program", "RPAR", "NULL", ["LPAR"; "Seq"; "RPAR"; "@"])という形でつかいます。 
タプルの第一成分...文法番号 
タプルの第二成分...文法番号内の通し番号(一つ大きいのがマーカーをひとつ後ろにずらしたもの) 
タプルの第三成分...左辺の非終端記号 
タプルの第四成分...マーカーの前の記号(ない場合は"NULL"とします。) 
タプルの第五成分...マーカーの後の記号(ない場合は"NULL"とします。) 
タプルの第六成分...右辺にマーカーをつけたもの 
 
それでは「文法要素から上の形(LR0ItemType型)のリストを返す」関数を定義します。 
 
> let addMarkers (idNum:int, lhName:string, inLst:list<string>) = 
    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);; 
 
val addMarkers : 
  int * string * string list -> 
    (int * int * string * string * string * string list) list 
     
(使用例) 
 
> addMarkers (1,"Program",["LPAR";"Seq";"RPAR"]);; 
val it : (int * int * string * string * string * string list) list = 
  [(1, 1, "Program", "NULL", "LPAR", ["@"; "LPAR"; "Seq"; "RPAR"]); 
   (1, 2, "Program", "LPAR", "Seq", ["LPAR"; "@"; "Seq"; "RPAR"]); 
   (1, 3, "Program", "Seq", "RPAR", ["LPAR"; "Seq"; "@"; "RPAR"]); 
   (1, 4, "Program", "RPAR", "NULL", ["LPAR"; "Seq"; "RPAR"; "@"])] 
 
ここで、これからしばらく例として使う文法を挙げておきます。 
 
1:Program=LPAR Seq RPAR 
2:Program = NUM 
3:Seq = Program 
4:Seq = Seq COMMA Program 
 
これは入れ子をなす整数の並びを表す文法です。 
(この辺も山下義行さんの「コンパイラ入門」を参考にしています。ぜひご購入を!) 
例(1,(2,3),5,(4,((2,3),2),9)) 
 
では文法(のリスト)をgramという名前で定義しておきます。 
 
> let grams = ["0:Z=Program EOF";"1:Program=LPAR Seq RPAR";"2:Program = NUM";"3:Seq = Program";"4:Seq = Seq COMMA Program"];; 
 
val grams : string list = 
  ["0:Z=Program EOF"; "1:Program=LPAR Seq RPAR"; "2:Program = NUM"; 
   "3:Seq = Program"; "4:Seq = Seq COMMA Program"] 
    
文法要素の一つにaddMarkers関数を適用する関数を定義します。 
 
> let getGramWithMarker (inStr:string) = 
    splitOneLineGram inStr   
      |> addMarkers;; 
 
val getGramWithMarker : 
  string -> (int * int * string * string * string * string list) list 
   
(実行例) 
> getGramWithMarker "3:Seq = Program";; 
val it : (int * int * string * string * string * string list) list = 
  [(3, 1, "Seq", "NULL", "Program", ["@"; "Program"]); 
   (3, 2, "Seq", "Program", "NULL", ["Program"; "@"])] 
 
文法全体を対象にしてaddMarkers関数を適用する関数を定義します。 
これは「IR0項のSet,markerの直後が終端記号であるIR0項のSet、markerが末尾であるIR0項のSet、markerが先頭であるIR0項のSet、markerの直後が非終端記号であるIR0項のSet、、文法番号とマーカーがひとつ後ろにずれる毎にひとつ増える番号のタプルとIR0項を対応させるマップ」のタプルを返します。 
 
> let getLR0Terms (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   
 
   (lr0TermsSet,shiftItemsSet,reduceItemsSet,topMarker_ItemsSet,ntnAfterMarkerItemsSet,lr0TItemsMap);; 
 
val getLR0Terms : 
  string list -> 
    Set<int * int * string * string * string * string list> * 
    Set<int * int * string * string * string * string list> * 
    Set<int * int * string * string * string * string list> * 
    Set<int * int * string * string * string * string list> * 
    Set<int * int * string * string * string * string list> * 
    Map<(int * int),(int * int * string * string * string * string list)> 
 
> getLR0Terms grams;; 
val it : 
  Set<int * int * string * string * string * string list> * 
  Set<int * int * string * string * string * string list> * 
  Set<int * int * string * string * string * string list> * 
  Set<int * int * string * string * string * string list> * 
  Set<int * int * string * string * string * string list> * 
  Map<(int * int),(int * int * string * string * string * string list)> = 
  (set 
     [(0, 1, "Z", "NULL", "Program", ["@"; "Program"; "EOF"]); 
      (0, 2, "Z", "Program", "EOF", ["Program"; "@"; "EOF"]); 
      (0, 3, "Z", "EOF", "NULL", ["Program"; "EOF"; "@"]); 
      (1, 1, "Program", "NULL", "LPAR", ["@"; "LPAR"; "Seq"; "RPAR"]); 
      (1, 2, "Program", "LPAR", "Seq", ["LPAR"; "@"; "Seq"; "RPAR"]); 
      (1, 3, "Program", "Seq", "RPAR", ["LPAR"; "Seq"; "@"; "RPAR"]); 
      (1, 4, "Program", "RPAR", "NULL", ["LPAR"; "Seq"; "RPAR"; "@"]); 
      (2, 1, "Program", "NULL", "NUM", ["@"; "NUM"]); 
      (2, 2, "Program", "NUM", "NULL", ["NUM"; "@"]); ...], 
   set 
     [(0, 2, "Z", "Program", "EOF", ["Program"; "@"; "EOF"]); 
      (1, 1, "Program", "NULL", "LPAR", ["@"; "LPAR"; "Seq"; "RPAR"]); 
      (1, 3, "Program", "Seq", "RPAR", ["LPAR"; "Seq"; "@"; "RPAR"]); 
      (2, 1, "Program", "NULL", "NUM", ["@"; "NUM"]); 
      (4, 2, "Seq", "Seq", "COMMA", ["Seq"; "@"; "COMMA"; "Program"])], 
   set 
     [(0, 3, "Z", "EOF", "NULL", ["Program"; "EOF"; "@"]); 
      (1, 4, "Program", "RPAR", "NULL", ["LPAR"; "Seq"; "RPAR"; "@"]); 
      (2, 2, "Program", "NUM", "NULL", ["NUM"; "@"]); 
      (3, 2, "Seq", "Program", "NULL", ["Program"; "@"]); 
      (4, 4, "Seq", "Program", "NULL", ["Seq"; "COMMA"; "Program"; "@"])], 
   set 
     [(0, 1, "Z", "NULL", "Program", ["@"; "Program"; "EOF"]); 
      (1, 1, "Program", "NULL", "LPAR", ["@"; "LPAR"; "Seq"; "RPAR"]); 
      (2, 1, "Program", "NULL", "NUM", ["@"; "NUM"]); 
      (3, 1, "Seq", "NULL", "Program", ["@"; "Program"]); 
      (4, 1, "Seq", "NULL", "Seq", ["@"; "Seq"; "COMMA"; "Program"])], 
   set 
     [(0, 1, "Z", "NULL", "Program", ["@"; "Program"; "EOF"]); 
      (1, 2, "Program", "LPAR", "Seq", ["LPAR"; "@"; "Seq"; "RPAR"]); 
      (3, 1, "Seq", "NULL", "Program", ["@"; "Program"]); 
      (4, 1, "Seq", "NULL", "Seq", ["@"; "Seq"; "COMMA"; "Program"]); 
      (4, 3, "Seq", "COMMA", "Program", ["Seq"; "COMMA"; "@"; "Program"])], 
   map 
     [((0, 1), (0, 1, "Z", "NULL", "Program", ["@"; "Program"; "EOF"])); 
      ((0, 2), (0, 2, "Z", "Program", "EOF", ["Program"; "@"; "EOF"])); 
      ((0, 3), (0, 3, "Z", "EOF", "NULL", ["Program"; "EOF"; "@"])); 
      ((1, 1), (1, 1, "Program", "NULL", "LPAR", ["@"; "LPAR"; "Seq"; "RPAR"])); 
      ((1, 2), (1, 2, "Program", "LPAR", "Seq", ["LPAR"; "@"; "Seq"; "RPAR"])); 
      ((1, 3), (1, 3, "Program", "Seq", "RPAR", ["LPAR"; "Seq"; "@"; "RPAR"])); 
      ((1, 4), (1, 4, "Program", "RPAR", "NULL", ["LPAR"; "Seq"; "RPAR"; "@"])); 
      ((2, 1), (2, 1, "Program", "NULL", "NUM", ["@"; "NUM"])); 
      ((2, 2), (2, 2, "Program", "NUM", "NULL", ["NUM"; "@"])); ...]) 
 
これで準備が整いましたので、IR0項を与えるとそれを含むclosureを返す関数を定義します。 
 
> let getClosure  (inNtnAfterMarkerItemsSet:Set<LR0ItemType>) (inTopMarker_ItemSet:Set<LR0ItemType>) (initI :Set<LR0ItemType>) = 
    let rec getClosureSub oldClosureSet = 
                                  //oldClosureSetの中で非終端記号の前にマーカーがついている形のもの 
        let shouldAddedLRItems  = Set.filter (fun ele -> Set.contains ele inNtnAfterMarkerItemsSet) oldClosureSet 
        let newClosureSet = 
            Set.fold  (fun oldSet (_,_,_,_,aft,_) -> //aftはマーカーの直後の非終端記号 
                            let addLRItems = Set.filter (fun (_,_,lh,_,_,_ ) -> lh = aft) inTopMarker_ItemSet 
                            oldSet + addLRItems) 
                       oldClosureSet 
                       shouldAddedLRItems 
        if newClosureSet = oldClosureSet then 
             newClosureSet 
        else  
            getClosureSub newClosureSet 
 
    getClosureSub initI;; 
 
val getClosure : 
  Set<LR0ItemType> -> Set<LR0ItemType> -> Set<LR0ItemType> -> Set<LR0ItemType> 
 
次のように使用します。 
> let (whole,shift,reduce,topM,ntnAftM,_) = getLR0Terms grams;; 
 
val whole : Set<int * int * string * string * string * string list> = 
  set 
    [(0, 1, "Z", "NULL", "Program", ["@"; "Program"; "EOF"]); 
     (0, 2, "Z", "Program", "EOF", ["Program"; "@"; "EOF"]); 
     (0, 3, "Z", "EOF", "NULL", ["Program"; "EOF"; "@"]); 
     (1, 1, "Program", "NULL", "LPAR", ["@"; "LPAR"; "Seq"; "RPAR"]); 
     (1, 2, "Program", "LPAR", "Seq", ["LPAR"; "@"; "Seq"; "RPAR"]); 
     (1, 3, "Program", "Seq", "RPAR", ["LPAR"; "Seq"; "@"; "RPAR"]); 
     (1, 4, "Program", "RPAR", "NULL", ["LPAR"; "Seq"; "RPAR"; "@"]); 
     (2, 1, "Program", "NULL", "NUM", ["@"; "NUM"]); 
     (2, 2, "Program", "NUM", "NULL", ["NUM"; "@"]); ...] 
val topM : Set<int * int * string * string * string * string list> = 
  set 
    [(0, 1, "Z", "NULL", "Program", ["@"; "Program"; "EOF"]); 
     (1, 1, "Program", "NULL", "LPAR", ["@"; "LPAR"; "Seq"; "RPAR"]); 
     (2, 1, "Program", "NULL", "NUM", ["@"; "NUM"]); 
     (3, 1, "Seq", "NULL", "Program", ["@"; "Program"]); 
     (4, 1, "Seq", "NULL", "Seq", ["@"; "Seq"; "COMMA"; "Program"])] 
val shift : Set<int * int * string * string * string * string list> = 
  set 
    [(0, 2, "Z", "Program", "EOF", ["Program"; "@"; "EOF"]); 
     (1, 1, "Program", "NULL", "LPAR", ["@"; "LPAR"; "Seq"; "RPAR"]); 
     (1, 3, "Program", "Seq", "RPAR", ["LPAR"; "Seq"; "@"; "RPAR"]); 
     (2, 1, "Program", "NULL", "NUM", ["@"; "NUM"]); 
     (4, 2, "Seq", "Seq", "COMMA", ["Seq"; "@"; "COMMA"; "Program"])] 
val reduce : Set<int * int * string * string * string * string list> = 
  set 
    [(0, 3, "Z", "EOF", "NULL", ["Program"; "EOF"; "@"]); 
     (1, 4, "Program", "RPAR", "NULL", ["LPAR"; "Seq"; "RPAR"; "@"]); 
     (2, 2, "Program", "NUM", "NULL", ["NUM"; "@"]); 
     (3, 2, "Seq", "Program", "NULL", ["Program"; "@"]); 
     (4, 4, "Seq", "Program", "NULL", ["Seq"; "COMMA"; "Program"; "@"])] 
val ntnAftM : Set<int * int * string * string * string * string list> = 
  set 
    [(0, 1, "Z", "NULL", "Program", ["@"; "Program"; "EOF"]); 
     (1, 2, "Program", "LPAR", "Seq", ["LPAR"; "@"; "Seq"; "RPAR"]); 
     (3, 1, "Seq", "NULL", "Program", ["@"; "Program"]); 
     (4, 1, "Seq", "NULL", "Seq", ["@"; "Seq"; "COMMA"; "Program"]); 
     (4, 3, "Seq", "COMMA", "Program", ["Seq"; "COMMA"; "@"; "Program"])] 
  
  
 > let initI = (0,1, "Z", "NULL", "Program", ["@"; "Program"; "EOF"]);; 
 
val initI : int * int * string * string * string * string list = 
  (0, 1, "Z", "NULL", "Program", ["@"; "Program"; "EOF"]) 
 
 
> let t = getClosure  ntnAftM topM (Set.ofList [initI]);; 
 
val t : Set<LR0ItemType> = 
  set 
    [(0, 1, "Z", "NULL", "Program", ["@"; "Program"; "EOF"]); 
     (1, 1, "Program", "NULL", "LPAR", ["@"; "LPAR"; "Seq"; "RPAR"]); 
     (2, 1, "Program", "NULL", "NUM", ["@"; "NUM"])] 
 
次回はgoto集合というものを紹介します。 
スポンサーサイト

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

コメントの投稿

非公開コメント

プロフィール

T GYOUTEN

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

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

この人とブロともになる

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