スポンサーサイト

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

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

 今回は構文解析と同時に具象構文木を作り上げていきたいと思います。 
作り上げる具象構文木は、文字で表現したときに 
 
    1:Program=LPAR Seq RPAR 
        LPAR 
        3:Seq = Program 
            2:Program = NUM 
                NUM 
        RPAR 
 
の形で表せるようにします。 
 
では具象構文木の定義からです。 
 
> type embodyST = 
    |Atmtn_Leaf of int //オートマトン番号 
    |Leaf of string //トークン文字列 
    |Node of (int* string * list<embodyST>) //intは構文規則番号,stringは "(1, "Program", ["DeclStmts"; "PrintStmts"])"等 
 
     
    //表示用 
    member this.dispStr (inc :int)  = //inc = インシデント 
            match this with 
            |Atmtn_Leaf (atmtnNo) 
                -> spaceStr(inc) +  (sprintf "atmtn = %d" atmtnNo) + "\r\n" 
 
            |Leaf(str) 
                -> spaceStr(inc) +  str + "\r\n"  
            |Node(index,str,lst)  
                -> spaceStr(inc) + str + "\r\n"  
                   + List.fold (fun state (ele:embodyST) -> state + (ele.dispStr (inc + 4)) ) "" lst  
 
    member this.getAtmtnNo () = 
            match this with 
            |Atmtn_Leaf (atmtnNo) 
                -> atmtnNo 
 
            |_  -> failwith "neverOccurableError"  
 
    member this.getTerminalName () = 
            match this with 
            |Leaf(tntName) 
                -> tntName 
            |Node(_,gramStr,childNodes) 
                ->let (_,lhName,_) = splitOneLineGram gramStr 
                  lhName   
            |_  -> failwith "neverOccurableError" ;; 
 
(返答) 
type embodyST = 
  | Atmtn_Leaf of int 
  | Leaf of string 
  | Node of (int * string * embodyST list) 
  with 
    member dispStr : inc:int -> string 
    member getAtmtnNo : unit -> int 
    member getTerminalName : unit -> string 
  end 
 
なお、コード中にAtmtn(オートマトン)という言葉が頻出しますが、これは→(矢印)部分なしのオートマトン、つまりLR(0)状態のこととして理解してください。 
 
前回では、スタックに非終端記号、終端記号、LR(0)状態番号を全部文字列として押し込んだり、取り出したりしていましたが、今回は木構造を押し込んだり、取り出したりする必要があるので、上のようにembodySTを定義しています。 
 
次に、embodyST表示用の補助の型と関数を定義しておきます。 
//スタック内のembodySTを表示用文字列に変換する時の向き 
type ST_DISP_Direction = 
    |ST_DISP_FORWARD  //スタックの先頭から 
    |ST_DISP_BACKWARD //スタックの末尾から 
 
//スタック内のembodySTを表示用文字列に変換する 
let cnvEmbodyStList2Str (inLst:list<embodyST>) (dirc: ST_DISP_Direction) = 
    let sb = new System.Text.StringBuilder() 
    let copeLst = 
        if dirc = ST_DISP_FORWARD then 
            inLst 
        else 
            List.rev inLst 
 
    copeLst 
        |> List.iter (fun node -> sb.Append(node.dispStr 4) |> ignore)  
     
    sb.ToString() 
     
 前回は処理stepと文字列のスタック2つを利用して構文解釈しましたが、今回は処理stepとembodySTのスタック2つを利用して構文解釈します。そのための型を定義しておきます。 
  
 >                //stepNo*スタック*入力記号の残り 
type treeState = int*list<embodyST>*list<embodyST>;; 
 
(返答) 
type treeState = int * embodyST list * embodyST list 
 
では、構文解釈用の表(LR(0)構文解析表)を利用して、構文解釈と同時にembodySTを構築していきます。 
解析部分のコードは後で示すことにして、どのようなステップで木が構築されるのかを、まずみてください。 
解釈するソースは前回同様に"LPAR NUM RPAR"にします。 
LR状態をもう一度のっけておきます。 
 
--------------------1---------------------- 
 
Z → ["@"; "Program"; "EOF"]  
Program → ["@"; "LPAR"; "Seq"; "RPAR"]  
Program → ["@"; "NUM"]  
 
--------------------2---------------------- 
 
Program → ["@"; "LPAR"; "Seq"; "RPAR"]  
Program → ["LPAR"; "@"; "Seq"; "RPAR"]  
Program → ["@"; "NUM"]  
Seq → ["@"; "Program"]  
Seq → ["@"; "Seq"; "COMMA"; "Program"]  
 
--------------------3---------------------- 
 
Program → ["NUM"; "@"]  
 
--------------------4---------------------- 
 
Z → ["Program"; "@"; "EOF"]  
 
--------------------5---------------------- 
 
Seq → ["Program"; "@"]  
 
--------------------6---------------------- 
 
Program → ["LPAR"; "Seq"; "@"; "RPAR"]  
Seq → ["Seq"; "@"; "COMMA"; "Program"]  
 
--------------------7---------------------- 
 
Program → ["@"; "LPAR"; "Seq"; "RPAR"]  
Program → ["@"; "NUM"]  
Seq → ["Seq"; "COMMA"; "@"; "Program"]  
 
--------------------8---------------------- 
 
Program → ["LPAR"; "Seq"; "RPAR"; "@"]  
 
--------------------9---------------------- 
 
Seq → ["Seq"; "COMMA"; "Program"; "@"]  
 
 
まず最初の段階では、左右のスタックが 
(左) 
 atmtn = 1 
(右) 
    LPAR 
    NUM 
    RPAR 
    EOF 
という状態でスタートです。atmtn = 1 というのはLR(0)状態の1からスタートということです。 
 
状態1でLPARを読み込む場合なので、S<2>より、LPARを読み込んで、状態2に移ります。 
 
(左) 
    atmtn = 1 
    LPAR 
    atmtn = 2 
(右) 
    NUM 
    RPAR 
    EOF 
     
状態2でNUMを読み込む場合なので、S<3>より、NUMを読み込んで、状態3に移ります。 
 
(左) 
    atmtn = 1 
    LPAR 
    atmtn = 2 
    NUM 
    atmtn = 3 
(右) 
    RPAR 
    EOF 
 
ここでは、状態3で、RPARを読み込む場合ですから、表よりR[2]1を実行します。 
これは文法番号2の「2:Program = NUM」を使っての還元です。 
還元する部分で、ノードを作成し、右のスタックに押し込みます。 
 
(左) 
    atmtn = 1 
    LPAR 
    atmtn = 2 
(右) 
    2:Program = NUM 
        NUM 
    RPAR 
    EOF 
 
状態2でProgramを読み込む場合なので、S<5>より、Programを読み込んで、状態5に移ります。 
(左) 
    atmtn = 1 
    LPAR 
    atmtn = 2 
    2:Program = NUM 
        NUM 
    atmtn = 5 
(右) 
    RPAR 
    EOF 
 
状態5でRPARを読み込む場合なので、R[3]1より、「3:Seq = Program」を使って還元して、状態2に戻ります。 
(左) 
    atmtn = 1 
    LPAR 
    atmtn = 2 
(右) 
    3:Seq = Program 
        2:Program = NUM 
            NUM 
    RPAR 
    EOF 
 
状態2でSeqを読み込む場合なので、s<6>より、、Seqを読み込んで、状態6に移ります。 
(左) 
    atmtn = 1 
    LPAR 
    atmtn = 2 
    3:Seq = Program 
        2:Program = NUM 
            NUM 
    atmtn = 6 
(右) 
    RPAR 
    EOF 
 
状態6でRPARを読み込む場合なので、s<8>より、、RPARを読み込んで、状態8に移ります。 
(左) 
    atmtn = 1 
    LPAR 
    atmtn = 2 
    3:Seq = Program 
        2:Program = NUM 
            NUM 
    atmtn = 6 
    RPAR 
    atmtn = 8 
(右) 
    EOF 
 
状態8でEOFを読み込む場合なので、R[1}3より、、文法番号1の「1:Program=LPAR Seq RPAR」を使っての還元ですから、左のスタックから3*2で6個の内容を降ろしてNodeを作成して右のスタックに押し込みます。状態は1に戻ります。 
 
(左) 
    atmtn = 1 
(右) 
    1:Program=LPAR Seq RPAR 
        LPAR 
        3:Seq = Program 
            2:Program = NUM 
                NUM 
        RPAR 
    EOF 
 
状態1でProgramを読み込む場合なので、s<4>より、、Programを読み込んで、状態4に移ります。 
(左) 
    atmtn = 1 
    1:Program=LPAR Seq RPAR 
        LPAR 
        3:Seq = Program 
            2:Program = NUM 
                NUM 
        RPAR 
    atmtn = 4 
(右) 
    EOF 
 
状態4でEOFを読み込む場合なので、A(受理)より、構文解析完了です。 
スタックの上から2番目の要素が、もとめたかった具象構文木です。 
 
では、このように木を作りながら、構文解釈する関数のコードをのっけておきます。 
 
> //構文木作成表示用////構文番号->"1:Program = DeclStmts PrintStmts"//構文解析map////////////////////状態////////////////////////////// 
let analizeOneStepTree (id2gramRuleMap:Map<int,string>) (idTerm2VLR0Map:Map<int*string,LR0State>) ((no,stkOfTree,remOfTree):treeState) = 
    let curAtmtnst:int = (List.head stkOfTree).getAtmtnNo() 
    let topRemainNode = List.head remOfTree 
    let topRemainNodeTerminalName:string = topRemainNode.getTerminalName() 
    let nextMove = idTerm2VLR0Map.[curAtmtnst,topRemainNodeTerminalName] 
    match nextMove with 
    |SHIFT(nextAtmtnNo) -> 
                (no+1, Atmtn_Leaf(nextAtmtnNo):: topRemainNode::stkOfTree,List.tail remOfTree) 
    |REDUCE(ruleNo,graEleNum,lhName) -> 
                let (popNodes,remT) = getPopN stkOfTree (2*graEleNum) 
                //偶数番だけとりだす。(Atmtn_Leafを取り除く ) 
                let nesNodes = popNodes |>  List.mapi(fun i x -> (i,x)) |> List.filter(fun (i,_) -> i % 2 = 1) |> List.map (fun (_,x) -> x) |> List.rev 
                (no+1,remT, (Node(ruleNo,id2gramRuleMap.[ruleNo],nesNodes))::remOfTree) 
    |ACCEPT->   //終了の場合は状態を変えない 
            (no,stkOfTree,remOfTree) 
    |NUL   -> 
            failwith "ソースが文法にのっとっていません";; 
 
(返答) 
val analizeOneStepTree : 
  Map<int,string> -> 
    Map<(int * string),LR0State> -> 
      int * embodyST list * embodyST list -> 
        int * embodyST list * embodyST list 
 
次回は、LR(0)の部分のまとめのWindows ソフトを作ります。 
スポンサーサイト

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

コメントの投稿

非公開コメント

プロフィール

T GYOUTEN

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

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

この人とブロともになる

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