スポンサーサイト

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

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

 前回までで、closureを求める方法を紹介しました。 
今例にしている文法は次のようなものです。 
 
1:Program=LPAR Seq RPAR 
2:Program = NUM 
3:Seq = Program 
4:Seq = Seq COMMA Program 
 
LR(0)項というものは、文法にマーカー(いまから読み込もうとしている位置)を付け加えたものでした。 
Program → ["@"; "Program"; "EOF"] 
ただプログラム上ではもっと情報量をつけくわえた次のような形のタプルを使っています。 
 
(0, 1, "Z", "NULL", "Program", ["@"; "Program"; "EOF"]) 
タプルの第一成分...文法番号 
タプルの第二成分...文法番号内の通し番号(一つ大きいのがマーカーをひとつ後ろにずらしたもの) 
タプルの第三成分...左辺の非終端記号 
タプルの第四成分...マーカーの前の記号(ない場合は"NULL"とします。) 
タプルの第五成分...マーカーの後の記号(ない場合は"NULL"とします。) 
タプルの第六成分...右辺にマーカーをつけたもの 
 
またProgram → ["@"; "Program"; "EOF"]という状況は、文法より 
Program → ["@"; "LPAR"; "Seq"; "RPAR"] 
Program → ["@"; "NUM"] 
という状況でもあります(ある可能性がある)ので、同じ状況でありうるものをひと塊にしたものをclosureというのでした。 
Program → ["@"; "Program"; "EOF"]のclosureは 
{Program → ["@"; "Program"; "EOF"]、Program → ["@"; "LPAR"; "Seq"; "RPAR"]、Program → ["@"; "NUM"]}です。 
 
さて実際に入力文字列を解析している場合には次のトークンがやってきます。このトークンによってどのIR(0)項を使用して次の遷移状態に移るかということが決定されます。 
例えば上の場合で、次のトークンがLPARなら、LPARを読み込みProgram → [ "LPAR";"@"; "Seq"; "RPAR"]という状態に遷移する。次のトークンがNUMなら、NUMを読み込みProgram → [ "NUM";"@"]と遷移します。 
ここでgoyo(I,A)を次の様に定義します。 
LR(0)集合Iの状態で,「終端もしくは非終端記号である記号A」を受け取ったら、どの状態になるか。 
例 
goto( (Z->["@"; "Program"; "EOF"],Program->["@"; "EX"; "Exp"]) , EX) = {Program ->["EX";"@";"Exp"]}です。 
 
ではgoto(I,A)を求める関数を定義します。 
 
> let getGoto (inNtnAfterMarkerItemsSet:Set<LR0ItemType>) (inTopMarker_ItemSet:Set<LR0ItemType>)  
            (inIRItemMap:Map<(int*int),LR0ItemType>)  
            (inLRItemSet:Set<LR0ItemType>) (inStr:string) = 
    let getClosurePA = getClosure inNtnAfterMarkerItemsSet inTopMarker_ItemSet 
    let shouldAddGredienceLRItems = Set.filter (fun (_,_,_,_,aft,_) -> aft = inStr) inLRItemSet  
    let tempSet = //マーカーをずらしたものの集合 
            shouldAddGredienceLRItems 
                |> Set.fold (fun accSet (i,j,_,_,_,_) ->   
                                let addItem =inIRItemMap.[(i,j+1)] //(マーカーを一つ進めたもの(マーカーの次はinStr)) 
                                Set.add addItem accSet   
                            ) 
                   Set.empty  
    getClosurePA tempSet;; 
 
val getGoto : 
  Set<LR0ItemType> -> 
    Set<LR0ItemType> -> 
      Map<(int * int),LR0ItemType> -> 
        Set<LR0ItemType> -> string -> Set<LR0ItemType> 
 
 
使用してみます。まずは準備から。 
 
> let (whole,shift,reduce,topM,ntnAftM,rlMap) = getLR0Terms grams 
let initI = (0,1, "Z", "NULL", "Program", ["@"; "Program"; "EOF"]) 
let t = getClosure  ntnAftM topM (Set.ofList [initI]);; 
 
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 rlMap : 
  Map<(int * int),(int * int * string * string * string * string list)> = 
  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"; "@"])); ...] 
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"])] 
val initI : int * int * string * string * string * string list = 
  (0, 1, "Z", "NULL", "Program", ["@"; "Program"; "EOF"]) 
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,"LPAR")を求めてみます。 
 
getGoto ntnAftM topM rlMap t "LPAR";; 
val it : Set<LR0ItemType> = 
  set 
    [(1, 1, "Program", "NULL", "LPAR", ["@"; "LPAR"; "Seq"; "RPAR"]); 
     (1, 2, "Program", "LPAR", "Seq", ["LPAR"; "@"; "Seq"; "RPAR"]); 
     (2, 1, "Program", "NULL", "NUM", ["@"; "NUM"]); 
     (3, 1, "Seq", "NULL", "Program", ["@"; "Program"]); 
     (4, 1, "Seq", "NULL", "Seq", ["@"; "Seq"; "COMMA"; "Program"])] 
  
次回はいよいよ構文解析を始めます。 
getGoto関数までのコードは次の通りです。 
 open System    
 
//文法定義のエラー 
exception MyGramExcp of string 
 
let STR_EPS ="EPSILON" 
 
///////////////////////////////// 
 
//splitOneLineGram "5:Program = DeclStmts PrintStmts" 
//結果 (5,"Program", ["DeclStmts"; "PrintStmts"]) 
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) 
 
//非終端記号と終端記号のSetを返す 
//getNTN_TN_Sets ["1:Program = DeclStmts PrintStmts";"2:DeclStmts = VAR SEMI";"3:PrintStmts = EPSILON"] 
//(set ["DeclStmts"; "PrintStmts"; "Program"], set ["SEMI"; "VAR"]) 
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 grams = ["0:Z=Program EOF";"1:Program=LPAR Seq RPAR";"2:Program = NUM";"3:Seq = Program";"4:Seq = Seq COMMA Program"] 
 
 
type LR0ItemType = int * int * string * string * string * string list 
//                (1,3, "Program", "RPAR", "NULL", ["LPAR"; "Seq"; "RPAR"; "@"]) 
//タプルの第二成分は同一構文規則内の通し番号、一つ大きいのがマーカーを一つ後ろにずらしたもの 
 
//マーカーを付けて、マーカーの前後の記号とそれのタプルを返す 
//> 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"; "@"])] 
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) 
 
//> 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"; "@"])] 
let getGramWithMarker (inStr:string) = 
    splitOneLineGram inStr   
      |> addMarkers 
 
//> getLR0Terms grams;; //結果は中略してある 
// (set 
//     [(0, 1, "Z", "NULL", "Program", ["@"; "Program"; "EOF"]); 
//      (2, 2, "Program", "NUM", "NULL", ["NUM"; "@"]); ...], 
//   set 
//     [(0, 2, "Z", "Program", "EOF", ["Program"; "@"; "EOF"]); 
//      (4, 2, "Seq", "Seq", "COMMA", ["Seq"; "@"; "COMMA"; "Program"])], 
//   set 
//     [(0, 3, "Z", "EOF", "NULL", ["Program"; "EOF"; "@"]); 
//      (4, 4, "Seq", "Program", "NULL", ["Seq"; "COMMA"; "Program"; "@"])], 
//   set 
//     [(0, 1, "Z", "NULL", "Program", ["@"; "Program"; "EOF"]); 
//      (4, 1, "Seq", "NULL", "Seq", ["@"; "Seq"; "COMMA"; "Program"])], 
//   set 
//     [(0, 1, "Z", "NULL", "Program", ["@"; "Program"; "EOF"]); 
//      (4, 3, "Seq", "COMMA", "Program", ["Seq"; "COMMA"; "@"; "Program"])], 
//   map 
//     [((0, 1), (0, 1, "Z", "NULL", "Program", ["@"; "Program"; "EOF"])); 
//      ((2, 2), (2, 2, "Program", "NUM", "NULL", ["NUM"; "@"])); ...]) 
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) 
 
//let (whole,shift,reduce,topM,ntnAftM,_) = getLR0Terms grams 
//let initI = (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"])] 
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 
 
 
let (whole,shift,reduce,topM,ntnAftM,rlMap) = getLR0Terms grams 
let initI = (0,1, "Z", "NULL", "Program", ["@"; "Program"; "EOF"]) 
let t = getClosure  ntnAftM topM (Set.ofList [initI]) 
//let u = getGoto ntnAftM topM rlMap t "LPAR" 
//val u : Set<LR0ItemType> = 
//  set 
//    [(1, 1, "Program", "NULL", "LPAR", ["@"; "LPAR"; "Seq"; "RPAR"]); 
//     (1, 2, "Program", "LPAR", "Seq", ["LPAR"; "@"; "Seq"; "RPAR"]); 
//     (2, 1, "Program", "NULL", "NUM", ["@"; "NUM"]); 
//     (3, 1, "Seq", "NULL", "Program", ["@"; "Program"]); 
//     (4, 1, "Seq", "NULL", "Seq", ["@"; "Seq"; "COMMA"; "Program"])] 
let getGoto (inNtnAfterMarkerItemsSet:Set<LR0ItemType>) (inTopMarker_ItemSet:Set<LR0ItemType>)  
            (inIRItemMap:Map<(int*int),LR0ItemType>)  
            (inLRItemSet:Set<LR0ItemType>) (inStr:string) = 
    let getClosurePA = getClosure inNtnAfterMarkerItemsSet inTopMarker_ItemSet 
    let shouldAddGredienceLRItems = Set.filter (fun (_,_,_,_,aft,_) -> aft = inStr) inLRItemSet  
    let tempSet = //マーカーをずらしたものの集合 
            shouldAddGredienceLRItems 
                |> Set.fold (fun accSet (i,j,_,_,_,_) ->   
                                let addItem =inIRItemMap.[(i,j+1)] //(マーカーを一つ進めたもの(マーカーの次はinStr)) 
                                Set.add addItem accSet   
                            ) 
                   Set.empty  
    getClosurePA tempSet 
 
スポンサーサイト

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

コメントの投稿

非公開コメント

プロフィール

T GYOUTEN

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

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

この人とブロともになる

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