スポンサーサイト

上記の広告は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関数までのコードは次の通りです。 

続きを読む

スポンサーサイト

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

プロフィール

T GYOUTEN

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

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

この人とブロともになる

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