スポンサーサイト

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

F#で入門 コンパイラ、インタプリタ編 文法変換(左再帰除去、左括り出し)

 前回までで 1 + 2 + .. + 5 等の形のソースから、構文木を作る方法を考えました。 
構文規則としては 
0:Z = Program EOF 
1:Program = NUM Program2 
2:Program2 = PLUS Program 
3:Program2 = EPSILON   
 
を採用していました。 
今回は別の構文規則 
 
0:Z = Program EOF 
1:Program = NUM 
2:Program = Program PLUS NUM 
 
を採用したらどうなるかという話です。 
 
では前回と同様にコードを書くことを考え、2に対応する部分を書いているとします。 
 
//1:Program = NUM 
//2:Program = Program PLUS NUM 
and program (remain:list<TokenKind>) = 
       match remain with 
       |(1の場合)-> なんたらかんたら  
       |(2の場合)-> どーしたこーした 
 
まず困るのはremainの最初のトークンを先読みしても、どっちもNUMなので、1,2の場合分けができないということです。(ちなみに1個先読みして下向き構文解析できる文法をLL(1)文法といいます。) 
この場合は、2個先読みすればどっちの形か分かりますが、たとえばNUMが終端記号でなく、「どれだけの長さに導出されるかわからない、非終端記号NonTerminal1」であった場合、例えば次の構文規則 
Program = NonTerminal1 
Program = Program Plus NonTerminal1 
の場合などは、いくつ先読みしても、どちらの場合か把握することができません。 
ということで、このようなX→Xαという形の導出は、LL(1)文法ではないので、下向き構文解析するときは他の形の文法に変換して扱います。(εを使う文法に変換します。) 
(X→Xαという形の導出が存在するとき、その文法はXについて左再帰的といいます。) 
 
1:Program = NUM 
2:Program = Program PLUS NUM 
の左再帰を除去するには新しい非終端記号を導入して次のようにします。 
 
Program = NUM Program2  
Program2 = PLUS Program2 
Program2 = ε 
 
 
次に左括り出しですが次の文法をみてください。 
(1)Term = NUM  
(2)Term = NUM PLUS Term 
これも下向き構文解析するときにTermに対応する関数を書く場合に、共に先読み記号がNUMとなって場合分けに困ります。このような場合は、共通する接頭後を括り出し規則を書き直します。 
Term = NUM Term2 
Term2 = PLUS Term 
Term2 = ε 
 
この処理を左括り出しといいます。 
 
下向き構文解析するときは、このように左再帰性の除去と、左括り出しを施してから処理に入ります。 
スポンサーサイト

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

コメントの投稿

非公開コメント

プロフィール

T GYOUTEN

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

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

この人とブロともになる

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