F#で入門　コンパイラ 、インタプリタ編 LR1TokenizeAndParseクラス化を利用したWinソフト(2)

 今回は前回作成したソフトに少し改良を加えてみます。 
前回のソフトで使いにくい部分は、テキストボックスへの入力部分です。 
RPAR,\( 
LPAR,\) 
ADD,\+ 
SUB,\- 
MUL,\* 
DIV,\/ 
NUM,0|[1-9][0-9]* 
とか入力するのですが、visual studioのＦ＃のソースにする場合は 
let t =   
    [ 
    "RPAR","\("; 
    "LPAR","\)"; 
    "ADD","\+"; 
    "SUB","\-"; 
    "MUL","\*"; 
    "DIV","\/"; 
    "NUM","0|[1-9][0-9]*"; 
    ] 
という形になります。 
ということで、ソフト上でこの二つの形を相互変換できるようにしたいと思います。 
(文法ルールも同様に相互変換できるようにします。） 
 
ソフト側で入力しておいて 
 
1033-1.jpg 
 
「->」ボタンを押すと 
 
1033-2.jpg 
 
逆にvisual studioのソース部分を右側にコピペしておいて 
(なお、各ルール毎に改行しておくことが必要です。） 
 
 
1033-3.jpg
 
「<-」ボタンを押すと 
 
1033-4.jpg
 
となるようにします。 
 
全体は下の通りです。 
 
1033-5.jpg
 
全コードは次の通りです。 

続きを読む

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

Pagetop

F#で入門　コンパイラ 、インタプリタ編 LR1TokenizeAndParseクラスを利用したWinソフト(1)

 今回はLR1TokenizeAndParseクラスを利用してWindowsソフトを作成したいと思います。
完成形は下の通りです。
1032-1.jpg
使い方の説明です。左上のテキストボックスにトークン化ルールを入力します。
例

1032-2.jpg 
次に右上のテキストボックスに文法を入力します。
1032-3.jpg 
これで「適用」ボタンを押します。
あとはソースを入力しては、「→」ボタンを押せば、具象構文木が右下のテキストボックスに表示されます。

1032-4.jpg 
1032-5.jpg
ソースは以下の通りです。

続きを読む

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

Pagetop

F#で入門　コンパイラ 、インタプリタ編 LR(1)のクラス化

 LL(1)でもやったように、LR(1)構文解釈器をクラス化して、トークンの定義と文法を与えておけば、ソースから具象抽象木を自動生成できるようにしたいと思います。 
 
コードはあとでのっけることにして、まずはシグネチャーを示します。 
 
作られる具象抽象木の型は次の通り 
type embodyST = 
  | Leaf of Token 
  | Node of (int * string * embodyST list) 
  with 
    member dispStr : inc:int -> string 
  end 
 
構文解釈するクラスの型は次の通りです。 
type LR1TokenizeAndParse = 
  class 
    new : inDefLst:(string * string) list * inStrLst:string list -> 
            LR1TokenizeAndParse 
    member GetEBASTtree : sourceLst:string list -> embodyST 
    member GetNntnSetAdnTnSet : unit -> Set<string> * Set<string> 
    member GetTokens : sourceLst:string list -> Token list 
 
次の様に使います。 
(この文法は０以上の数の、四則演算表現（括弧の使用は可）を処理する文法です。） 
 
トークン化ルールをtnR1に束縛しておきます。 
> let tnR1 = 
   [("RPAR","\("); 
    ("LPAR","\)"); 
    ("ADD","\+"); 
    ("SUB","\-"); 
    ("MUL","\*"); 
    ("DIV","\/"); 
    ("NUM","0|[1-9][0-9]*"); 
    ];; 
 
val tnR1 : (string * string) list = 
  [("RPAR", "\("); ("LPAR", "\)"); ("ADD", "\+"); ("SUB", "\-"); ("MUL", "\*"); 
   ("DIV", "\/"); ("NUM", "0|[1-9][0-9]*")] 
 
文法ルールをgrammersStrLst1に束縛しておきます。 
> let grammersStrLst1 = 
   ["1:Program = Exp";  
    "2:Exp =  Term"; 
    "3:Exp = Term ADD Term"; 
    "4:Exp = Term SUB Term"; 
    "5:Term = Fact"; 
    "6:Term = Fact MUL Fact"; 
    "7:Term = Fact DIV Fact"; 
    "8:Fact = NUM"; 
    "9:Fact = RPAR Exp LPAR"];; 
 
val grammersStrLst1 : string list = 
  ["1:Program = Exp"; "2:Exp =  Term"; "3:Exp = Term ADD Term"; 
   "4:Exp = Term SUB Term"; "5:Term = Fact"; "6:Term = Fact MUL Fact"; 
   "7:Term = Fact DIV Fact"; "8:Fact = NUM"; "9:Fact = RPAR Exp LPAR"] 
 
インスタンスを生成します。 
 
let tp1 = new LR1TokenizeAndParse (tnR1,grammersStrLst1) 
 
> let tp1 = new LR1TokenizeAndParse (tnR1,grammersStrLst1);; 
 
val tp1 : LR1TokenizeAndParse 
 
ではソースコードを何種類か解釈させて、具象構文木を求めてみます。 
 
例１ 
"3"の解釈 
 
> tp1.GetEBASTtree([" 3 "]).dispStr 4;; 
 
val it : string = 
  "    (1)1:Program = Exp 
        (2)2:Exp =  Term 
            (5)5:Term = Fact 
                (8)8:Fact = NUM 
                    [NUM 3 (1,2)]  
" 
 
例2 
"1 - 2"の解釈 
> tp1.GetEBASTtree([" 1 -  2 "]).dispStr 4;; 
 
val it : string = 
  "    (1)1:Program = Exp 
        (4)4:Exp = Term SUB Term 
            (5)5:Term = Fact 
                (8)8:Fact = NUM 
                    [NUM 1 (1,2)]  
            [SUB - (1,4)]  
            (5)5:Term = Fact 
                (8)8:Fact = NUM 
                    [NUM 2 (1,7)]  
" 
 
例2 
"3 * ( 6 / 2)"の解釈 
 
> tp1.GetEBASTtree(["3 * ( 6 / 2)"]).dispStr 4;; 
val it : string = 
  "    (1)1:Program = Exp 
        (2)2:Exp =  Term 
            (6)6:Term = Fact MUL Fact 
                (8)8:Fact = NUM 
                    [NUM 3 (1,1)]  
                [MUL * (1,3)]  
                (9)9:Fact = RPAR Exp LPAR 
                    [RPAR ( (1,5)]  
                    (2)2:Exp =  Term 
                        (7)7:Term = Fact DIV Fact 
                            (8)8:Fact = NUM 
                                [NUM 6 (1,7)]  
                            [DIV / (1,9)]  
                            (8)8:Fact = NUM 
                                [NUM 2 (1,11)]  
                    [LPAR ) (1,12)]  
" 
 
では、このクラスのコードをのっけておきます。 
このクラスは今後ずっと使っていきたいと考えています。（今後も毎回ソースは省略せずにのっける予定なので、毎回同じコード（このクラスの定義部分）が最初にくると思います。 
では、コードは以下の通りです。 

続きを読む

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

Pagetop

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

 さて紹介する予定の構文解釈方法も今回のLALR(1)で最後です。 
LALR(1)はLR(1)に、さらに解釈の精密さを加えたものではなく、少し簡略化したものになります。 
（構文解釈能力ではLR(1)の方がLALR(1)より上です。） 
なぜ、簡略化するかというと、LR(1)では状態数が大きくなりすぎる傾向があるからです。 
では簡略化の方法を説明します。 
 
LR(1)項i=[Ｘ→α@β,t]から、先読み記号を除いたLR(0)項[Ｘ→α@β]をiの核といいます。 
LALR(1)ではLR(1)状態で核が同じものをすべて併合します。 
 
前回の例の文法 
0:Z = Program EOF 
1:Program = Exp EQ2 Exp 
2:Program = ID 
3:Exp = Exp ADD Term 
4:Exp = Term 
5:Term = ID 
で説明すると 
 
LR1状態 
 
--------------------1---------------------- 
 
Z → ["@"; "Program"; "EOF"]  set ["EOF"] 
Program → ["@"; "Exp"; "EQ2"; "Exp"]  set ["EOF"] 
Program → ["@"; "ID"]  set ["EOF"] 
Exp → ["@"; "Exp"; "ADD"; "Term"]  set ["ADD"; "EQ2"] 
Exp → ["@"; "Term"]  set ["ADD"; "EQ2"] 
Term → ["@"; "ID"]  set ["ADD"; "EQ2"] 
 
--------------------2---------------------- 
 
Program → ["Exp"; "@"; "EQ2"; "Exp"]  set ["EOF"] 
Exp → ["Exp"; "@"; "ADD"; "Term"]  set ["ADD"; "EQ2"] 
 
--------------------3---------------------- 
 
Program → ["ID"; "@"]  set ["EOF"] 
Term → ["ID"; "@"]  set ["ADD"; "EQ2"] 
 
--------------------4---------------------- 
 
Z → ["Program"; "@"; "EOF"]  set ["EOF"] 
 
--------------------5---------------------- 
 
Exp → ["Term"; "@"]  set ["ADD"; "EQ2"] 
 
--------------------6---------------------- 
 
Exp → ["Exp"; "ADD"; "@"; "Term"]  set ["ADD"; "EQ2"] 
Term → ["@"; "ID"]  set ["ADD"; "EQ2"] 
 
--------------------7---------------------- 
 
Program → ["Exp"; "EQ2"; "@"; "Exp"]  set ["EOF"] 
Exp → ["@"; "Exp"; "ADD"; "Term"]  set ["ADD"; "EOF"] 
Exp → ["@"; "Term"]  set ["ADD"; "EOF"] 
Term → ["@"; "ID"]  set ["ADD"; "EOF"] 
 
--------------------8---------------------- 
 
Term → ["ID"; "@"]  set ["ADD"; "EQ2"] 
 
--------------------9---------------------- 
 
Exp → ["Exp"; "ADD"; "Term"; "@"]  set ["ADD"; "EQ2"] 
 
--------------------10---------------------- 
 
Program → ["Exp"; "EQ2"; "Exp"; "@"]  set ["EOF"] 
Exp → ["Exp"; "@"; "ADD"; "Term"]  set ["ADD"; "EOF"] 
 
--------------------11---------------------- 
 
Term → ["ID"; "@"]  set ["ADD"; "EOF"] 
 
--------------------12---------------------- 
 
Exp → ["Term"; "@"]  set ["ADD"; "EOF"] 
 
--------------------13---------------------- 
 
Exp → ["Exp"; "ADD"; "@"; "Term"]  set ["ADD"; "EOF"] 
Term → ["@"; "ID"]  set ["ADD"; "EOF"] 
 
--------------------14---------------------- 
 
Exp → ["Exp"; "ADD"; "Term"; "@"]  set ["ADD"; "EOF"] 
 
1029-0.jpg 

でしたがLALR(1)では、次のようになります。 
 
--------------------1---------------------- 
 
Z → ["@"; "Program"; "EOF"]  set ["EOF"] 
Program → ["@"; "Exp"; "EQ2"; "Exp"]  set ["EOF"] 
Program → ["@"; "ID"]  set ["EOF"] 
Exp → ["@"; "Exp"; "ADD"; "Term"]  set ["ADD"; "EQ2"] 
Exp → ["@"; "Term"]  set ["ADD"; "EQ2"] 
Term → ["@"; "ID"]  set ["ADD"; "EQ2"] 
 
--------------------2---------------------- 
 
Program → ["Exp"; "@"; "EQ2"; "Exp"]  set ["EOF"] 
Exp → ["Exp"; "@"; "ADD"; "Term"]  set ["ADD"; "EQ2"] 
 
--------------------3---------------------- 
 
Program → ["ID"; "@"]  set ["EOF"] 
Term → ["ID"; "@"]  set ["ADD"; "EQ2"] 
 
--------------------4---------------------- 
 
Z → ["Program"; "@"; "EOF"]  set ["EOF"] 
 
--------------------5---------------------- 
 
Exp → ["Term"; "@"]  set ["ADD"; "EOF"; "EQ2"] 
 
--------------------6---------------------- 
 
Exp → ["Exp"; "ADD"; "@"; "Term"]  set ["ADD"; "EOF"; "EQ2"] 
Term → ["@"; "ID"]  set ["ADD"; "EOF"; "EQ2"] 
 
--------------------7---------------------- 
 
Program → ["Exp"; "EQ2"; "@"; "Exp"]  set ["EOF"] 
Exp → ["@"; "Exp"; "ADD"; "Term"]  set ["ADD"; "EOF"] 
Exp → ["@"; "Term"]  set ["ADD"; "EOF"] 
Term → ["@"; "ID"]  set ["ADD"; "EOF"] 
 
--------------------8---------------------- 
 
Term → ["ID"; "@"]  set ["ADD"; "EOF"; "EQ2"] 
 
--------------------9---------------------- 
 
Exp → ["Exp"; "ADD"; "Term"; "@"]  set ["ADD"; "EOF"; "EQ2"] 
 
--------------------10---------------------- 
 
Program → ["Exp"; "EQ2"; "Exp"; "@"]  set ["EOF"] 
Exp → ["Exp"; "@"; "ADD"; "Term"]  set ["ADD"; "EOF"] 
 
 
1030-0.jpg  
併合されて状態が4つ減っています。 
 
コードとしては、LR1用のdataのセット(accMap,accId2ClsMap,accId2ClsMap)をLALR1用にコンバートする関数 cnvLR12LALR1　を定義してそれを使う部分が変更点になります。 
 
なお、yaccもLALR(1)構文解析器を自動生成するツールです。（恥ずかしながら自動生成ツールは使ったことがありませんが。） 
 
今回も前回と同じようなソフトを作ってみました。 
（実行図） 
 
1030-1.jpg
 
コードは次の通りです。 

続きを読む

Pagetop

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

 今回はSRL構文解釈より、もひとつ強力なLR(1)構文解釈を紹介したいとおもいます。 
LR(0)を以前やりましたが、LR(1)は、LR(0)に先読み記号をひとつくわえて、解釈の精密さを加えたものに 
なります。（LR(?)の（）の中は先読み記号の個数です。） 
（ちなみに前回やったSLRはSimple LR(1) の省略です。） 
 
なおここからは、a,b,c,...は終端記号,Ｘ，Ｙ，Zは非終端記号,u,v,..は終端記号の列,α、β、...は記号列とします。 
LR(0)項は[Ｘ→α@β] の形であらわされるものでしたが、LR(1)項はこれに、先読み記号である終端記号（先読み記号は実際にトークンを読むときにでてくるのですから、当然終端記号です。）を付け加えます。 
すなわちLR(1)項は[Ｘ→α@β,t]という形です。（β部分を読み切った時に、次にtが現れるということ） 
 
LR(1)項で[Ｘ→α@Yβ,t]と[Y→@γ,t']が同じ状況を表すときを考えます。 
 
[Ｘ→α@Yβ,t]はYβを読み切った時、非終端記号tが現れる。 
[Y→@γ,t']はγ（すなわちY)を読み切った時、非終端記号t'が現れる。 
ということですから、すなわち 
 
「βがnullableの時はt'∈First(β)∪{t}の時、βがnullableでないときは、t'∈First(β)の時」です。 
 
なお、実際にLR(1)状態を処理するときには[Ｘ→α@Yβ,t1],[Ｘ→α@Yβ,t2]...[Ｘ→α@Yβ,tn]をまとめて[Ｘ→α@Yβ,set[t1,t2,...,tn]]の形で処理します。 
コードは後でのっけることにして例を挙げます。 
 
例 
文法 
0:Z = Program EOF 
1:Program = Exp EQ2 Exp 
2:Program = ID 
3:Exp = Exp ADD Term 
4:Exp = Term 
5:Term = ID 
 
LR1状態 
 
--------------------1---------------------- 
 
Z → ["@"; "Program"; "EOF"]  set ["EOF"] 
Program → ["@"; "Exp"; "EQ2"; "Exp"]  set ["EOF"] 
Program → ["@"; "ID"]  set ["EOF"] 
Exp → ["@"; "Exp"; "ADD"; "Term"]  set ["ADD"; "EQ2"] 
Exp → ["@"; "Term"]  set ["ADD"; "EQ2"] 
Term → ["@"; "ID"]  set ["ADD"; "EQ2"] 
 
--------------------2---------------------- 
 
Program → ["Exp"; "@"; "EQ2"; "Exp"]  set ["EOF"] 
Exp → ["Exp"; "@"; "ADD"; "Term"]  set ["ADD"; "EQ2"] 
 
--------------------3---------------------- 
 
Program → ["ID"; "@"]  set ["EOF"] 
Term → ["ID"; "@"]  set ["ADD"; "EQ2"] 
 
--------------------4---------------------- 
 
Z → ["Program"; "@"; "EOF"]  set ["EOF"] 
 
--------------------5---------------------- 
 
Exp → ["Term"; "@"]  set ["ADD"; "EQ2"] 
 
--------------------6---------------------- 
 
Exp → ["Exp"; "ADD"; "@"; "Term"]  set ["ADD"; "EQ2"] 
Term → ["@"; "ID"]  set ["ADD"; "EQ2"] 
 
--------------------7---------------------- 
 
Program → ["Exp"; "EQ2"; "@"; "Exp"]  set ["EOF"] 
Exp → ["@"; "Exp"; "ADD"; "Term"]  set ["ADD"; "EOF"] 
Exp → ["@"; "Term"]  set ["ADD"; "EOF"] 
Term → ["@"; "ID"]  set ["ADD"; "EOF"] 
 
--------------------8---------------------- 
 
Term → ["ID"; "@"]  set ["ADD"; "EQ2"] 
 
--------------------9---------------------- 
 
Exp → ["Exp"; "ADD"; "Term"; "@"]  set ["ADD"; "EQ2"] 
 
--------------------10---------------------- 
 
Program → ["Exp"; "EQ2"; "Exp"; "@"]  set ["EOF"] 
Exp → ["Exp"; "@"; "ADD"; "Term"]  set ["ADD"; "EOF"] 
 
--------------------11---------------------- 
 
Term → ["ID"; "@"]  set ["ADD"; "EOF"] 
 
--------------------12---------------------- 
 
Exp → ["Term"; "@"]  set ["ADD"; "EOF"] 
 
--------------------13---------------------- 
 
Exp → ["Exp"; "ADD"; "@"; "Term"]  set ["ADD"; "EOF"] 
Term → ["@"; "ID"]  set ["ADD"; "EOF"] 
 
--------------------14---------------------- 
 
Exp → ["Exp"; "ADD"; "Term"; "@"]  set ["ADD"; "EOF"] 
 
構文解析表 
 
1029-0.jpg 
 
なお、前回と同じようなソフトを作ってみました。 
（実行図） 
 1029-1.jpg

 
コードは次の通りです。 

続きを読む

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

Pagetop
ホーム  次のページ »
Pagetop
プロフィール

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

最新記事
最新コメント
最新トラックバック
月別アーカイブ
カテゴリ
フリーエリア
フリーエリア
blogram投票ボタン
検索フォーム


RSSリンクの表示
リンク
このブログをリンクに追加する
Powered By FC2ブログ

今すぐブログを作ろう！

Powered By FC2ブログ

ブロとも申請フォーム

この人とブロともになる

ＱＲコード
ＱＲコード