スポンサーサイト

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

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

前回までで、たとえば文法  
1:Program=LPAR Seq RPAR   
2:Program = NUM   
3:Seq = Program   
4:Seq = Seq COMMA Program   
に対し 
LR(0)状態集合を以下のように求め、 
 
--------------------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"; "@"]  
 
其々の状態で、次のトークンによってどのような動作をするかの表(構文解析表) 

1023-1_20120308194614.jpg
を作り上げました。 
 
さて、では上向き構文解析の最初の部分で説明したように、二つのスタックを利用して構文解釈をしてみたいと思います。 
まずは補助の関数を二つ定義します。 
 
> //リストからn個の要素をpopして残りを返す補助関数 
let popN in_lst in_n = 
    let rec popNSub lst count = 
        if count = in_n then 
            lst 
        else 
            popNSub (List.tail lst) (count + 1) 
    popNSub in_lst 0 
 
 
//リストからn個の要素をpopしてpopしたものと残りを返す補助関数 
let getPopN in_lst in_n = 
    let rec popNSub lst acc count = 
        if count = in_n then 
            (List.rev acc,lst) 
        else 
            popNSub (List.tail lst) ((List.head lst)::acc) (count + 1) 
    popNSub in_lst [] 0;; 
 
val popN : 'a list -> int -> 'a list 
val getPopN : 'a list -> int -> 'a list * 'a list 
 
 
次にスタックに詰め込む内容としてanaState型を定義します。 
 
 
>               //stepNo*スタック*入力記号の残り 
type anaState = int*list<string>*list<string>;; 
 
type anaState = int * string list * string list 
 
では、「LR(0)状態番号」と「次のトークン」のタプルと、「どのような動作(シフト、還元等)をするか」の値を対応させるMap(これは前回求めました。)とanaStateを引数として、anaStateを返す関数analizeOneStepを定義します。 
 
> let analizeOneStep (idTerm2VLR0Map:Map<int*string,LR0State>) ((no,stk,rem):anaState) = 
    let curAtmtnst:int =  System.Int32.Parse(List.head stk) 
    let topRemain:string = List.head rem 
    let nextMove = idTerm2VLR0Map.[curAtmtnst,topRemain] 
    match nextMove with 
    |SHIFT(nextAtmtnNo) -> 
                (no+1,nextAtmtnNo.ToString()::topRemain::stk,List.tail rem) 
    |REDUCE(ruleNo,graEleNum,lhName) -> 
                (no+1,popN stk (2*graEleNum) ,lhName::rem) 
    |ACCEPT->      //終了の場合は状態を変えない 
            (no,stk,rem) 
    |NUL   -> 
            failwith "ソースが文法にのっとっていません";; 
 
val analizeOneStep : 
  Map<(int * string),LR0State> -> 
    int * string list * string list -> int * string list * string list 
     
では使用してみます。 
準備として{「LR(0)状態番号」と「次のトークン」のタプルと、「どのような動作(シフト、還元等)をするか」の値を対応させるMap」を文法から求めます。 
 
> 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"] 
 
> let (_,useMap) = makeLR0Map grams;; 
 
val useMap : Map<(int * string),LR0State> = 
  map 
    [((1, "COMMA"), NUL); ((1, "EOF"), NUL); ((1, "LPAR"), SHIFT 2); 
     ((1, "NUM"), SHIFT 3); ((1, "Program"), SHIFT 4); ((1, "RPAR"), NUL); 
     ((1, "Seq"), NUL); ((1, "Z"), NUL); ((2, "COMMA"), NUL); ...] 
 
analizeOneStep関数にuseMapを部分適用します。 
 
> let myAnalize = analizeOneStep useMap;; 
 
val myAnalize : (anaState -> int * string list * string list) 
 
では トークン列 ["LPAR";"NUM";"RPAR"]を構文解釈してみます。 
最初のLR(0)状態は1なので、片方のスタックに"1"を入れ,もう一方のスタックは残り記号列をいれるので 
["LPAR";"NUM";"RPAR";"EOF"]を入れておきます。タプルの第一成分のintは処理が第何手かが分かるようにいれたstep番号で、本質的には不必要なものです。 
 
> let t1 = myAnalize (0,["1"],["LPAR";"NUM";"RPAR";"EOF"]);; 
 
val t1 : int * string list * string list = 
  (1, ["2"; "LPAR"; "1"], ["NUM"; "RPAR"; "EOF"]) 
   
まずは状態1でLPARを読み込む場合なので、S<2>より、LPARを読み込んで、状態2に移りました。 
 
> let t2 = myAnalize (1, ["2"; "LPAR"; "1"], ["NUM"; "RPAR"; "EOF"]);; 
 
val t2 : int * string list * string list = 
  (2, ["3"; "NUM"; "2"; "LPAR"; "1"], ["RPAR"; "EOF"]) 
 
状態2でNUMを読み込む場合なので、S<3>より、NUMを読み込んで、状態3に移りました。 
 
> let t3 = myAnalize (2, ["3"; "NUM"; "2"; "LPAR"; "1"], ["RPAR"; "EOF"]);; 
 
val t3 : int * string list * string list = 
  (3, ["2"; "LPAR"; "1"], ["Program"; "RPAR"; "EOF"]) 
   
ここでは、状態3で、RPARを読み込む場合ですから、表よりR[2]1を実行します。 
これは文法番号2の「2:Program = NUM」を使っての還元ですから、左のスタックから"3"と "NUM"を降ろして、右に"Program"を乗っけます。状態が1つバックするわけです。(左のスタックの先頭が今いるLR(0)状態を表します。)((注)読み込んだトークンも記録しているので、降ろす個数は1*2個となります。) 
 
> let t4 = myAnalize (3, ["2"; "LPAR"; "1"], ["Program"; "RPAR"; "EOF"]);; 
 
val t4 : int * string list * string list = 
  (4, ["5"; "Program"; "2"; "LPAR"; "1"], ["RPAR"; "EOF"]) 
   
状態2でProgramを読み込む場合なので、S<5>より、Programを読み込んで、状態5に移りました。 
 
> let t5 = myAnalize (4, ["5"; "Program"; "2"; "LPAR"; "1"], ["RPAR"; "EOF"]);; 
 
val t5 : int * string list * string list = 
  (5, ["2"; "LPAR"; "1"], ["Seq"; "RPAR"; "EOF"]) 
 
状態5でRPARを読み込む場合なので、R[3]1より、「3:Seq = Program」を使って還元して、状態2に戻っています。 
 
> let t6 = myAnalize (5, ["2"; "LPAR"; "1"], ["Seq"; "RPAR"; "EOF"]);; 
 
val t6 : int * string list * string list = 
  (6, ["6"; "Seq"; "2"; "LPAR"; "1"], ["RPAR"; "EOF"]) 
 
状態2でSeqを読み込む場合なので、s<6>より、、Seqを読み込んで、状態6に移りました。 
 
> let t7 = myAnalize (6, ["6"; "Seq"; "2"; "LPAR"; "1"], ["RPAR"; "EOF"]);; 
 
val t7 : int * string list * string list = 
  (7, ["8"; "RPAR"; "6"; "Seq"; "2"; "LPAR"; "1"], ["EOF"]) 
 
状態6でRPARを読み込む場合なので、s<8>より、、RPARを読み込んで、状態8に移りました。 
 
> let t8 = myAnalize  (7, ["8"; "RPAR"; "6"; "Seq"; "2"; "LPAR"; "1"], ["EOF"]);; 
 
val t8 : int * string list * string list = (8, ["1"], ["Program"; "EOF"]) 
 
状態8でEOFを読み込む場合なので、R[1}3より、、文法番号1の「1:Program=LPAR Seq RPAR」を使っての還元ですから、左のスタックから3*2で6個の内容を降ろして右のスタックにProgramを押し込みます。状態は1に戻ります。 
 
> let t9 = myAnalize (8, ["1"], ["Program"; "EOF"]);; 
 
val t9 : int * string list * string list = (9, ["4"; "Program"; "1"], ["EOF"]) 
 
状態1でProgramを読み込む場合なので、s<4>より、、Programを読み込んで、状態4に移りました。 
 
> let t10 = myAnalize (9, ["4"; "Program"; "1"], ["EOF"]);; 
 
val t10 : int * string list * string list = 
  (9, ["4"; "Program"; "1"], ["EOF"]) 
   
状態4でEOFを読み込む場合なので、A(受理)より、構文解析完了です。 
 
ここまでの構文解析を一覧にすると次の様になります。(下から上へみてください。) 
(左のスタックは右左が逆に表示しています。) 
 
10 ["1"; "Program"; "4"] <<->>["EOF"]  
9 ["1"] <<->>["Program"; "EOF"]  
8 ["1"; "LPAR"; "2"; "Seq"; "6"; "RPAR"; "8"] <<->>["EOF"]  
7 ["1"; "LPAR"; "2"; "Seq"; "6"] <<->>["RPAR"; "EOF"]  
6 ["1"; "LPAR"; "2"] <<->>["Seq"; "RPAR"; "EOF"]  
5 ["1"; "LPAR"; "2"; "Program"; "5"] <<->>["RPAR"; "EOF"]  
4 ["1"; "LPAR"; "2"] <<->>["Program"; "RPAR"; "EOF"]  
3 ["1"; "LPAR"; "2"; "NUM"; "3"] <<->>["RPAR"; "EOF"]  
2 ["1"; "LPAR"; "2"] <<->>["NUM"; "RPAR"; "EOF"]  
1 ["1"] <<->>["LPAR"; "NUM"; "RPAR"; "EOF"]  
 
実際に構文解析するには左のスタックで、読み込んだ記号は必要ないので、状態番号だけ積む関数も定義しておきます。 
 
> let analizeOneStepSimple (idTerm2VLR0Map:Map<int*string,LR0State>) ((no,stk,rem):anaState) = 
    let curAtmtnst:int =  System.Int32.Parse(List.head stk) 
    let topRemain:string = List.head rem 
    let nextMove = idTerm2VLR0Map.[curAtmtnst,topRemain] 
    match nextMove with 
    |SHIFT(nextAtmtnNo) -> 
                (no+1,nextAtmtnNo.ToString()::stk,List.tail rem) 
    |REDUCE(ruleNo,graEleNum,lhName) -> 
                (no+1,popN stk graEleNum ,lhName::rem) 
    |ACCEPT->      //終了の場合は状態を変えない 
            (no,stk,rem) 
    |NUL   -> 
            failwith "ソースが文法にのっとっていません";; 
 
val analizeOneStepSimple : 
  Map<(int * string),LR0State> -> 
    int * string list * string list -> int * string list * string list 
 
 
今回で、構文解析はできるようになったのですが、これだけでは、ソースが文法的に正しいかどうかの確認だけしかできないので、次回は同時に「抽象木」を生成させたいと思います。 
スポンサーサイト

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

コメントの投稿

非公開コメント

プロフィール

T GYOUTEN

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

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

この人とブロともになる

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