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

パターンマッチャー P の使い方(3)


7. stnum のアクションを編集する

前回 stnum のアクションを記述したが、かけ算の処理だけだった。今回、これを割り算にも拡張する。また、前回はアクションを別に作ったが、長いコードではないので、P.pat( patten, action ) の第2引数のアクションには無名関数を直接渡すことにした。コードは次のようになる。

var stnum = P.pat( function() {return star() && number()}, function() {
var a = parseFloat(P.pop()); var op = P.pop(); var b = parseFloat(P.pop())
if (op == "*") {
P.push("" + (a*b))
} else {
P.push("" + (b/a))
}
})

しかし、このままでは star パーサが / を認識しないので、これが * だけでなく / も認識するように、star パーサの定義を編集する。

var star = function() {return P.lex(/^[*/]/)() && spacing() }


8. term パーサの定義

また、このパーサだと 12 * 34 * 56 のように連続した計算はパースできないので P.many ( patten ) 関数を使って繰り返しの処理ができるようにして term というパーサを作る。P.many 関数は単に引数のパーサを0回以上繰り返し適用するだけだから、term の定義は次のようになる。

var term = function() {return number() && P.many( stnum )() }

このコードで P.many( stnum ) の引数 stnum には () が付いていないのに、P.many( stnum)() のように P.many( stnum ) 本体には () がつくのに注意してほしい。これは P.many( pattern ) の引数には関数を渡すが、無名関数の中に記述するのは P.many( stnum )() という関数の実行だからだ。このあたりがバグを引き起こすポイントになるので気をつけないといけない。

ここまでの編集の結果を次に示す。エディタで a_lert を alert に変更すればコピペで実行できる。

<script src="parse.js"></script>
<script>
var spacing = P.pat( P.lex(/^\s*/), P.pop )
var number = function() {return P.lex(/^[0-9]+/)() && spacing() }
var star = function() {return P.lex(/^[*/]/)() && spacing() }
var plus = function() {return P.lex(/^[+]/)() && spacing() }
var lparen = function() {return P.lex(/^[(]/)() && spacing() }
var rparen = function() {return P.lex(/^[)]/)() && spacing() }

var stnum = P.pat( function() {return star() && number()}, function() {
var a = parseFloat(P.pop()); var op = P.pop(); var b = parseFloat(P.pop())
if (op == "*") {
P.push("" + (a*b))
} else {
P.push("" + (b/a))
}
})

var term = function() {return number() && P.many( stnum )() }

P.setLine("2*6/4")
term()
a_lert( P.pop() )
</script>

9. expr パーサの定義

term (項)パーサが定義できたので、次は term + term - term + ... という式をパースする expr パーサを定義する。term は数値そのものではなく、いわば抽象的な数値とでもいうべきものだが、パーサのプログラムではこれをあたかも普通の数値であるかのように扱うことができる。そこで expr の定義には number パーサではなく term パーサを使うことにする。

ところで、expr パーサの構造は term パーサとほぼ同じなので、stnum パーサをコピーしたものを編集して adterm パーサを作り、term パーサをコピーしたものを編集して expr パーサを作る。

編集の結果が次のコードだ。こんな安易な方法で動くのだろうかと不安になったが、あっさりと動いてしまった。

<script src="parse.js"></script>
<script>
var spacing = P.pat( P.lex(/^\s*/), P.pop )
var number = function() {return P.lex(/^[0-9]+/)() && spacing() }
var star = function() {return P.lex(/^[*/]/)() && spacing() }
var plus = function() {return P.lex(/^[+-]/)() && spacing() }
var lparen = function() {return P.lex(/^[(]/)() && spacing() }
var rparen = function() {return P.lex(/^[)]/)() && spacing() }

var stnum = P.pat( function() {return star() && number()}, function() {
var a = parseFloat(P.pop()); var op = P.pop(); var b = parseFloat(P.pop())
if (op == "*") {
P.push("" + (a*b))
} else {
P.push("" + (b/a))
}
})

var term = function() {return number() && P.many( stnum )() }

var adterm = P.pat( function() {return plus() && term()}, function() {
var a = parseFloat(P.pop()); var op = P.pop(); var b = parseFloat(P.pop())
if (op == "+") {
P.push("" + (a+b))
} else {
P.push("" + (b-a))
}
})

var expr = function() {return term() && P.many( adterm )() }

P.setLine("12*3 + 4*5")
expr()
a_lert( P.pop() )
</script>

10. 括弧の処理

expr パーサで整数の四則演算はパースできるようになったが、まだ括弧が使えない。括弧を使うと ( 式 ) があたかも数値と同じように使うことができるようになる。このような再帰的定義をパースできるのがパーサの最大の利点だ。P モジュールでもこれができなければパターンマッチャーの意義が半減する。

そこで、number パーサと ( expr ) パーサを同じ primary というカテゴリーで使うことができるように primary パーサを記述することにする。まずは ( expr ) を表す paren パーサを記述した。コードは次のようになる。

var paren = P.pat( function() {return lparen() && expr() && rparen() }, function() {
P.pop(); var a = P.pop(); P.pop()
P.push( a )
})

paren パーサのアクションはスタックに収められている ( expr ) を取り出して、( と ) を読み捨てて、中身の expr だけをスタックへ戻す作業だ。

primary パーサの記述は次のようになる。number パーサが成功すれば、そのあとの paren パーサは実行せず、primary を呼び出したパーサの処理に戻る。number パーサの処理は再帰関数の base case になる。また、number パーサが成功しなければ、次の paren パーサを処理する。paren パーサの処理からさらに深い再帰関数の処理が始まる。たったこれだけの工夫で、括弧による再帰的な数式の処理ができるようになる。

var primary = function() {return number() || paren() }

最後の仕上げは、adterm パーサと、term パーサに存在している number パーサを primary パーサに置き換えることだ。これによって、number パーサの処理をしていたところに primary パーサの処理を置き換えることができる。

整数の四則演算のパーサの完成版は次のようになる。あっさりと動いたのには記述した本人も驚いてしまった。

<script src="parse.js"></script>
<script>
var spacing = P.pat( P.lex(/^\s*/), P.pop )
var number = function() {return P.lex(/^[0-9]+/)() && spacing() }
var star = function() {return P.lex(/^[*/]/)() && spacing() }
var plus = function() {return P.lex(/^[+-]/)() && spacing() }
var lparen = function() {return P.lex(/^[(]/)() && spacing() }
var rparen = function() {return P.lex(/^[)]/)() && spacing() }

var stnum = P.pat( function() {return star() && primary()}, function() {
var a = parseFloat(P.pop()); var op = P.pop(); var b = parseFloat(P.pop())
if (op == "*") {
P.push("" + (a*b))
} else {
P.push("" + (b/a))
}
})

var term = function() {return primary() && P.many( stnum )() }

var adterm = P.pat( function() {return plus() && term()}, function() {
var a = parseFloat(P.pop()); var op = P.pop(); var b = parseFloat(P.pop())
if (op == "+") {
P.push("" + (a+b))
} else {
P.push("" + (b-a))
}
})

var expr = function() {return term() && P.many( adterm )() }

var paren = P.pat( function() {return lparen() && expr() && rparen() }, function() {
P.pop(); var a = P.pop(); P.pop()
P.push( a )
})

var primary = function() {return number() || paren() }

P.setLine("(3 - 1) * ( 2 + 4)")
expr()
a_lert( P.pop() )
</script>

P モジュールを使ったパーサコンビネータのプログラムは、関数が 1st class citizen であることを最大限に活用しているため、デバッグが難しい面がある。しかし、この使い方の説明で述べたように、要素的なパーサの動作確認を行いながら、コピべを活用して、定型的な記述の多いパーサプログラムの性質を利用すれば、パーサのプログラミングはそう難しいものではないことがわかる。

by tnomura9 | 2016-02-13 17:37 | JavaScript | Comments(0)
<< 電卓パーサ(数値計算版) パターンマッチャー P の使... >>