スポンサーサイト

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

F#で入門 コンパイラ、インタプリタ編 下向き構文解析

 前回で、構文規則を定義してデフォルトの文法 Z = Program EOFから出発して、最左導出でトークン列を生成しました。 
そのうちの一つの構文規則は次のようなものでした。 
(構文規則例3) 
0:Z = Program EOF 
1:Program = NUM Program2 
2:Program2 = PLUS Program 
3:Program2 = EPSILON    
 
0,1,2,1,2,1,3と導出するとトークン列として 
「NUM PLUS NUM PLUS NUM EPSILON EOF」が生成されました。 
使った構文規則も同時に入れると 
(0 (1 NUM (2 PLUS (1 NUM (2 PLUS (1 NUM (3 EPSILON 3) 1) 2) 1) 2) 1) EOF 0) 
という表現となり、この入れ子構造を木で表すと 
    ( 0)Z 
        ( 1)Program 
            NUM 
            ( 2)Program2 
                PLUS 
                ( 1)Program 
                    NUM 
                    ( 2)Program2 
                        PLUS 
                        ( 1)Program 
                            NUM 
                            ( 3)Program2 
                                EPSILON 
        EOF 
となるのでした。 
(「構文規則の右辺」のそれぞれの要素が「構文規則の左辺」ノードの枝となっています。) 
このような木を具象抽象木といいます。 
 
さて今回は「NUM PLUS NUM PLUS NUM EPSILON EOF」というようなトークン列から、具象抽象木を作る方法を考えます。 
 
「トークン種別」と「木の構造」を次の様に定義しておきます。 
 
>type TokenKind = 
    |NUM 
    |PLUS 
    |EPSILON 
    |EOF 
 
type embodyST = 
    |Leaf of TokenKind  
    |Node of list<embodyST> ;; 
 
(返答略) 
 
 
次にトークンリストを受け取って「担当する文法要素分」だけトークンを消費し、残りのリストと「担当する文法要素」に対応する木を返す関数を定義していきます。 
コードは次のようになります。 
 
> (*  0*)//非終端記号z担当部分(zから導出したトークン列)を消費して、zに対応する木を返す関数 
(*  1*)let rec z (remain:list<TokenKind>) = 
(*  2*)      let (rem2,madeNodeByProgram) = program remain //rem2は「非終端記号Program担当部分の関数を適用した残り」 
(*  3*)                                             //madeNodeByProgramは「非終端記号Program担当部分を木にしたもの」  
(*  4*)       
(*  5*)      if rem2 <> [EOF] then //rem2は「非終端記号Program担当部分の関数を適用した残り」なので[EOF]になるはず 
(*  6*)        failwith "構文エラー" 
(*  7*)      else 
(*  8*)        Node([madeNodeByProgram;Leaf(EOF)]) 
(*  9*)//非終端記号program担当部分(programから導出したトークン列)を適用(消費)して、 
(* 10*)//残りのトークンリストとzに対応する木をタプルで返す関数 
(* 11*)and program (remain:list<TokenKind>) = 
(* 12*)       match remain with 
(* 13*)       |NUM::rem2 -> let (rem3,madeNodeByProgram2) = program2 rem2 
(* 14*)                     (rem3,Node( [Leaf(NUM)] @ [madeNodeByProgram2]))  
(* 15*)       |_ ->  failwith "構文エラー" 
(* 16*)//非終端記号program2担当部分(program2から導出したトークン列)を適用(消費)して、 
(* 17*)//残りのトークンリストとzに対応する木をタプルで返す関数 
(* 18*)and program2 (remain:list<TokenKind>) = 
(* 19*)       match remain with 
(* 20*)       |PLUS::rem2 ->let (rem3,madeNodeByProgram) = program rem2 
(* 21*)                     (rem3,Node( [Leaf(PLUS)] @ [madeNodeByProgram]))  
(* 22*)       |EPSILON::rem2    ->(rem2,Leaf(EPSILON)) 
(* 23*)       |_ ->  failwith "構文エラー" 
;; 
 
val z : TokenKind list -> embodyST 
val program : TokenKind list -> TokenKind list * embodyST 
val program2 : TokenKind list -> TokenKind list * embodyST 
 
関数zが構文規則 0:Z = Program EOFに対応する関数で、まずりスト全体に対しProgram担当部分の関数を適用し、そのあと残ったEOFというトークンを処理します。 
関数programが構文規則 1:Program = NUM Program2に対応する関数であり、リストの最初にNUMがあるはずなので、NUMより後のトークン列をProgram2に渡します。 
関数program2が2:Program2 = PLUS Program および 3:Program2 = EPSILON  に対応する関数で、これまでと違うのはどちらの形になっているかの分岐をしなければならないというところです。 
この分岐が20,22行で、2の形になっているなら,これから処理するトークン列の最初がPLUS、3の形になっているなら、これから処理するトークン列の最初がEPSILONになっているなずなので、このことから判断して処理を進めています。このように一つの非終端記号の定義は複数にまたがる場合は、次のいくつかのトークンから、処理の分岐をします。いくつくかの続くトークン(終端記号)をよんで処理の分岐をすることを、「先読み(lookahead)」といい、先読みされる終端記号を「先読み記号」といいます。(この例では、先読み記号はひとつで、処理の分岐の判断をすることができました。) 
先読み記号が何ならこちらの処理という処理の選択は一般には難しいことも多いので後日詳しくやりたいと思います。 
このように、文法の形に即した下請関数に処理を下して行き、降り切った部分から、上に向けて結果を構築していく(この場合は木の構築)方法を、「下向き構文解析」といいます。 
 
 
では実行例です。 
> z [NUM;EPSILON;EOF];; 
val it : embodyST = Node [Node [Leaf NUM; Leaf EPSILON]; Leaf EOF] 
 
> z [NUM;PLUS;NUM;EPSILON;EOF];; 
val it : embodyST = 
  Node 
    [Node [Leaf NUM; Node [Leaf PLUS; Node [Leaf NUM; Leaf EPSILON]]]; 
     Leaf EOF] 
 
> z [NUM;PLUS;NUM;PLUS;NUM;EPSILON;EOF];; 
val it : embodyST = 
  Node 
    [Node 
       [Leaf NUM; 
        Node 
          [Leaf PLUS; 
           Node [Leaf NUM; Node [Leaf PLUS; Node [Leaf NUM; Leaf EPSILON]]]]]; 
     Leaf EOF] 
      
 
ε(EPSILO)は空列を表し、一般にはトークン列には含まれません。 
そこで[NUM;EOF]や[NUM;PLUS;NUM;EOF]や [NUM;PLUS;NUM;PLUS;NUM;EOF];を処理するように関数の定義を直しておきます。 
上の22行目を 
       |EPSILON::rem2    ->(rem2,Leaf(EPSILON)) 
       から 
       |EOF::rem2    ->(EOF::rem2,Leaf(EPSILON)) 
に変えるだけです。(先読み記号がEOFに変わる) 
 
この形に直して実行してみます。 
 
> z [NUM;PLUS;NUM;EOF];; 
val it : embodyST = 
  Node 
    [Node [Leaf NUM; Node [Leaf PLUS; Node [Leaf NUM; Leaf EPSILON]]]; 
     Leaf EOF] 
      
スポンサーサイト

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

コメントの投稿

非公開コメント

プロフィール

T GYOUTEN

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

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

この人とブロともになる

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