スポンサーサイト

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

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

 今回から上向き構文解析を始めたいと思います。 
まずは次のような簡単な文法の言語を考えます。 
 
a:Z = Program EOF 
b:Program=EX Exp 
c:Exp = NUM 
 
EX NUMが終端記号(実際にはトークンとして現れる)、Program,Expが非終端記号です。 
 
さてソースを解析する開始した時点では、読み込む場所は一番最初です。読み込み場所がどこにあるかを「マーカー」(記号@)で表すことにします。 
すると最初の時点ではZ → ["@"; "Program"; "EOF"] と表すことができます。 
またProgramの前にマーカーがあるということは文法のbよりProgram → ["@"; "EX"; "Exp"] の形にあるとも考えることができます。 
これら二つをまとめて 
 
--------------------1---------------------- 
 
Z → ["@"; "Program"; "EOF"]  
Program → ["@"; "EX"; "Exp"]  
 
と表し、遷移状態の1と呼ぶことにします。 
 
次にマーカーが移動した状態を考えます。 
Program → ["@"; "EX"; "Exp"] でマーカーが移動すると 
Program → ["EX"; "@"; "Exp"] となりますが、これは文法のbよりExp → ["@"; "NUM"] の形とも考えることができます。よってこの遷移状態を2番とします。 
 
--------------------2---------------------- 
 
Program → ["EX"; "@"; "Exp"]  
Exp → ["@"; "NUM"]  
 
またZ → ["@"; "Program"; "EOF"] でマーカーが移動するとZ → ["Program"; "@"; "EOF"] となるのでこれを遷移状態の3番とします。 
 
--------------------3---------------------- 
 
Z → ["Program"; "@"; "EOF"]  
 
2の上側のProgram → ["EX"; "@"; "Exp"] でマーカーが移動するとProgram → ["EX"; "Exp"; "@"]  となるのでこれを遷移状態の4番とします。 
 
--------------------4---------------------- 
 
Program → ["EX"; "Exp"; "@"]  
 
2の下側のExp → ["@"; "NUM"] でマーカーが移動するとExp → ["NUM"; "@"]  となるのでこれを遷移状態の5番とします。 
 
--------------------5---------------------- 
 
Exp → ["NUM"; "@"]  
 
さて、例えば状態2にあり、つぎにトークンNUMを読み込めば状態5に遷移します。このような遷移用の矢印を遷移状態に合わせたものを「オートマトン」といいます。上のオートマトンは次のようになります。 
 
  1→Program→3 
  ↓ 
  EX 
  ↓ 
  2→Exp→4 
  ↓ 
  NUM 
  ↓ 
  5 
   
ではこのオートマトンとスタックを利用して EX NUM というコードを構文解析してみます。 
 
最初スタックには状態番号1をのせます。入力記号の残りはソースコードの EX NUM およびEOFです。 
これを 
1 ["1"] <<->>["EX"; "NUM"; "EOF"]  
と表します。左端は作業step 次がスタック、右端のリストの内容が入力記号の残りです。 
ここで、状態番号1で、入力記号の残りの先頭をみるとEXなので、上のオートマトンの指示する通りEXを読み込んで状態2に遷移します。 
2 ["1"; "EX"; "2"] <<->>["NUM"; "EOF"]  
スタック内の状態番号はどの状態を動いて行ったかの軌跡を表します。 
この時点で状態番号は3で入力記号の残りの先頭をみるとNUMなので、オートマトンよりNUMを読み込んで状態5に遷移します。 
3 ["1"; "EX"; "2"; "NUM"; "5"] <<->>["EOF"]  
 
さてここで行き止まりになりますが、ここでは逆に文法規則の右辺を左辺に置き換える作業をおこないます。 
スタックの先頭をみると記号としてはNUMがあるのでNUM @ の状態です。 
LRオートマトンでは、スタックの最上部に載っている記号列が文法X→αの右辺に一致したときには、スタックから記号列αを取り除き構文規則の左辺の非終端記号Xを新たに入力記号列の先頭に付加します。 
(いわば抽象度をあげていくわけです。)(注意この例ではαはNUMで一つの終端記号ですが、一般に記号列です。)この操作を還元(reduction)とよびます。 
還元すると文法のcを用いて、スタックと入力文字列の残りは 
4 ["1"; "EX"; "2"] <<->>["Exp"; "EOF"]  
となります。また遷移状態は2に後戻りしたとみなします。 
次に状態2から非終端記号Expを読み込んで、状態4にシフトします。 
5 ["1"; "EX"; "2"; "Exp"; "4"] <<->>["EOF"]  
文法規則のbを使って還元して、状態1となります。 
6 ["1"] <<->>["Program"; "EOF"]  
次に文法規則aを使うと 
7 ["1"; "Program"; "3"] <<->>["EOF"]  
となり、トークン列全体がProgramに還元されたので、めでたく構文解析終了です。 
 
ここまでの動きをまとめると次のようになります。(下から上へみてください。) 
 
7 ["1"; "Program"; "3"] <<->>["EOF"]  
6 ["1"] <<->>["Program"; "EOF"]  
5 ["1"; "EX"; "2"; "Exp"; "4"] <<->>["EOF"]  
4 ["1"; "EX"; "2"] <<->>["Exp"; "EOF"]  
3 ["1"; "EX"; "2"; "NUM"; "5"] <<->>["EOF"]  
2 ["1"; "EX"; "2"] <<->>["NUM"; "EOF"]  
1 ["1"] <<->>["EX"; "NUM"; "EOF"]  
 
続きは次回にしたいと思いますが、最終的には次のようなソフトをつくります。 
 
1020-1.jpg

スポンサーサイト

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

コメントの投稿

非公開コメント

プロフィール

T GYOUTEN

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

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

この人とブロともになる

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