人気ブログランキング | 話題のタグを見る

Racc の使い方 その4

アクション

英文を読むとき、英文自身はアルファベットが連続して並んだものだが、それを、単語や熟語、文といった単位に分割して解読していく。

数式の場合も同じで、12 + (345 / 5) のような数式も一連の数と記号の列だがこれを、12 や + や、(、345、/、5、) といったトークンに切り分け、さらにそれらのトークンの配列が文法に沿っているかどうかを構文解析プログラムで解析するという手順になる。

数式の記号列をトークンに切り分けるプログラムが字句解析プログラム。切り分けられたトークンが文法通りに配列されているかを調べるのが構文解析プログラムである。構文解析プログラムはそれ以外に正しい文法の文であれば、その文が指示する作業を行うという役割もある。文に関連させて行う処理をアクションといい、rule ~ end 文のなかの定義の横に書いてある { と } で囲まれた部分が実行される。calc.y の rule の部分を再掲しよう。

rule
target: exp
| /* none */ { result = 0 }

exp: exp '+' exp { result += val[2] }
| exp '-' exp { result -= val[2] }
| exp '*' exp { result *= val[2] }
| exp '/' exp { result /= val[2] }
| '(' exp ')' { result = val[1] }
| '-' NUMBER =UMINUS { result = -val[1] }
| NUMBER
end

exp: exp '+' exp の隣にある、{ result += val[2] } がアクションだ。構文解析プログラムが exp '+' exp というパターンを認識したとき、第3項目の exp の値を result の値に加算する処理を行う。result も val[] も Racc で決められた変数で、大まかに、result は式の値、val[0]は定義の第1項の値、val[1]は第2項の値、val[3]は第3項の値と考えておけばプログラムの改造もできる。

実は、これが分かるだけで calc.rb に累乗の計算を付け加えることができるのだ。

まず累乗の計算を示す演算子 '^' を calc.y に付け加えなければならない。'^' の優先順位は '*' より上なので prechigh に次のように登録する。ここで、left ディレクティブの代わりに、right ディレクティブが使われているのは累乗の場合 2^3^4 のような式は右から計算されるからだ。

prechigh
nonassoc UMINUS
right '^'
left '*' '/'
left '+' '-'
preclow

また、文法の rule にも累乗の規則を追加しなければならない。

rule
target: exp
| /* none */ { result = 0 }

exp: exp '+' exp { result += val[2] }
| exp '-' exp { result -= val[2] }
| exp '*' exp { result *= val[2] }
| exp '/' exp { result /= val[2] }
| exp '^' exp { result **= val[2] }
| '(' exp ')' { result = val[1] }
| '-' NUMBER =UMINUS { result = -val[1] }
| NUMBER
end

calc.rb に累乗の計算を追加するためにやることはたったこれだけだ。あとは racc -o calc.rb calc.y としてcalc.y をコンパイルしてみよう。コンパイルが成功したら ruby calc.rb として calc.rb を実行する。

? 2 ^ 3
= 9

のように表示されれば成功だ。
by tnomura9 | 2006-03-21 19:29 | Ruby | Comments(0)
<< Racc の使い方 その5 Racc の使い方 その3 >>