スポンサーサイト

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

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

 LR(0)構文解析は、適用できる文法の範囲が狭いので、実用に耐えません。 
例えば前回のソフトで、 
1:Program = NUM 
2:Program = NUM Program 
という文法(これは単なる数字の並びを表現してます。)を構文解釈しようとするとシフト/還元衝突エラー」がでます。 
 
このような衝突を回避し、さらに構文解釈の精度を上げるために、還元を行うための条件を次のように付け加えます。 
 
[x→α@]による還元は、先読み記号がFollow(x)に含まれるときに限る 
 
LR(0)構文解釈に、このようなルールを付け加えたものをSLR構文解釈といいます。 
 
LR(0)状態の還元項[x→α@]に、xのFollow集合を付け加えて、SRL状態を構築します。 
Follow(x) = {t1,t2,..,tn}のとき、SLR状態の還元項は[x→α@,{t1,t2,..,tn}]と書きます。 
 
例えば、文法 
1:Program = NUM 
2:Program = NUM Program 
のSLR状態は次のようになります。 
 
 
--------------------1---------------------- 
 
Z → ["@"; "Program"; "EOF"]   
Program → ["@"; "NUM"]   
Program → ["@"; "NUM"; "Program"]   
 
--------------------2---------------------- 
 
Program → ["@"; "NUM"]   
Program → ["NUM"; "@"]  set ["EOF"] 
Program → ["@"; "NUM"; "Program"]   
Program → ["NUM"; "@"; "Program"]   
 
--------------------3---------------------- 
 
Z → ["Program"; "@"; "EOF"]   
 
--------------------4---------------------- 
 
Program → ["NUM"; "Program"; "@"]  set ["EOF"] 
 
2の上から二つ目の還元項にはProgramのFollow集合であるset ["EOF"]が右に書いてあり、 
4の還元項にもProgramのFollow集合であるset ["EOF"]が右に書いてあります。 
 
この文法の構文解析表は次のようになります。 
 
1027-1.jpg 
 
2の欄をみてもらうと、次のトークンがEOFの部分では、還元をおこない、NUM,Programの部分ではシフトをおこなうようになっています。 
(LR(0)解析では、この部分でシフト還元衝突がおこります。) 
 
ちなみに、ソースを"NUM NUM NUM"として構文解析を行うと、解析過程は 
 
10 ["1"; "Program"; "3"] <<->>["EOF"]  
9 ["1"] <<->>["Program"; "EOF"]  
8 ["1"; "NUM"; "2"; "Program"; "4"] <<->>["EOF"]  
7 ["1"; "NUM"; "2"] <<->>["Program"; "EOF"]  
6 ["1"; "NUM"; "2"; "NUM"; "2"; "Program"; "4"] <<->>["EOF"]  
5 ["1"; "NUM"; "2"; "NUM"; "2"] <<->>["Program"; "EOF"]  
4 ["1"; "NUM"; "2"; "NUM"; "2"; "NUM"; "2"] <<->>["EOF"]  
3 ["1"; "NUM"; "2"; "NUM"; "2"] <<->>["NUM"; "EOF"]  
2 ["1"; "NUM"; "2"] <<->>["NUM"; "NUM"; "EOF"]  
1 ["1"] <<->>["NUM"; "NUM"; "NUM"; "EOF"]  
 
となり(下から順にみてください)、抽象木は 
 
    2:Program = NUM Program 
        NUM 
        2:Program = NUM Program 
            NUM 
            1:Program = NUM 
                NUM 
                 
が生成されます。 
 
ではSLR解析する関数のソースですが、LR(0)のものとほとんど同じです。主な変更(追加)点は 
 
(1)follow集合を求める関数の追加(これはLL1解析のものと同じものを使います。) 
 
(2)還元項とfollow集合のpairを集合として定義する。(この部分のコードの抜粋は以下の通りです。) 
 
......... 
   let reduceTermPairSet = 
         let temp =  
             [for  (clNo,subNo,lh,bfr,agt,lst) in reduceItemsSet do 
                for tn in NTN_FollowMap.[lh] do 
                     yield ((clNo,subNo,lh,bfr,agt,lst),tn) 
             ] 
         Set.ofList temp        
......... 
 
(3)還元の可能性を調べる部分で、follow集合を考えに入れる。(この部分のコードの抜粋は以下の通りです。) 
 
......... 
            |hd::tl -> 
                //還元の可能性を調べる 
                let reduceItems = 
                   accId2ClsMap.[curProcessingClsNo] 
                    |> Set.filter (fun item -> Set.contains (item,hd) reduceTermPairSet) 
                if  Set.count reduceItems > 1 then 
                    failwith (sprintf "還元/還元衝突 %s  %A " hd reduceItems ) 
                 
                elif Set.count reduceItems = 1 then //還元項がある場合 
                    //シフトの可能性を調べる 
                    let shiftableItems =  
 ......... 
 
前回のLR(0)解析と同様に次のようなソフトも作ってみました。 
 
1027-2.jpg
 
 
なおこのソフトは Seq=ε というような、空文字を含む文法も解析可能なのですが、それについては次回説明します。 
 
今回のコードは以下の通りです。 

続きを読む

スポンサーサイト

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

プロフィール

T GYOUTEN

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

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

この人とブロともになる

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