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

パターンの繰り返し (many)

パターンには e1e1e1e2e2 のようにパターンの繰り返しを定義することが多い。例えば 1 * 2 * 3 は number パターンと (* number) パターンの繰り返しからなっている。

この繰り返しを表現するために many( patern ) 高階関数を定義する。この関数は pattern を0回以上 line に複数回適用した時の戻り値のノードのリストを返す。コードは次のようになる。簡単な while ループで実現できる。

このコード例では戻り値をノードの配列にしたが、別に配列でなくても many 関数の中で木構造を作っても良い。many と名前をつけたが、単なる parser 関数を引数に取る高階関数だから、プログラマが自由に処理できる。この辺がいい加減なパーサの利点だ。かっちりしたパーサというより、パターンをプログラミングするためのツールキットだと思うと良い。

0回以上の繰り返しなのでマッチミスはない。また、引数の parser 関数が backtrack の面倒を見てくれるので、backtrack の処理もない。

<script>
function Node( value ) {
this.value = value
this.left = null
this.right = null
}

var line = ""

function lex( re ) {
return function() {
var match = line.match( re )
if ( match ) {
line = line.replace( re, "" )
return ( new Node( match ) )
}
return null
}
}

var e1 = lex( /^e1/ )
var e2 = lex( /^e2/ )

function many( parser ) {
retvalue = new Node("many")
var retvalues = []
var retval = null
while ( retval = parser() ) {
retvalues.push( retval )
}
return retvalues
}

line = "e1e1e1e2e2"
a_lert( many( e1 ).map( function(x) { return x.value }) )
</script>

by tnomura9 | 2016-02-06 18:57 | JavaScript | Comments(0)
<< パターンマッチツール パターンを強調した連接と選択 >>