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

正規表現で構文解析

このブログで紹介したパターンマッチャー P モジュールの構文解析は、幾つかの機能のコンポーネントに分けることができる。それは、モジュールが、要素的なパーサの連接、優先順位付き選択、繰り返しを定義できるということだ。

ところが、このパターンの連接、選択、繰り返しの定義は正規表現でもできる。それでは、正規表現で、ソースの生の文字列ではなく、字句解析を行った後のトークンの種別を対象に解析すれば、構文解析ができるのではないかと思い立った。そこで、次のようなソースを書いてみた。

<script>
var number = 'number'
var star = '[*]'
var plus = '[+]'

var term = number + '(' + star + number + ')*'
var expression = term + '(' + plus + term + ')*'

parser = new RegExp( expression )
d_ocument.write(parser.toString()+'<br>')
function parse(string) {
result = string.search(parser)
if (result != -1) {
return true
} else {
return false
}
}

string = "number*number*number+number*number"
d_ocument.write( parse( string ))
d_ocument.close()
</script>

これなら、正規表現を利用して、電卓の構文解析をほぼ文法の通りに記述できる。このプログラムはこのブログで以前に紹介した Code Mirror HTML Editor にコピペして実験してみることができる。このプログラムを実行すると次のようになって文法のチェックだけだが、四則演算の構文解析ができる。

/number([*]number)*([+]number([*]number)*)*/
true

しかし、文法定義を次のように括弧の処理を含む再帰的定義にしたら正規表現では動作しなかった。

var term = primary + '(' + star + primary + ')*'
var expression = term + '(' + plus + term + ')*'
var primary = number + '|' + '(' + expression + ')'

つまり、正規表現で再帰的定義ができれば、構文解析も可能であるということだ。これは、Pモジュールでは、正規表現と違って処理対象が文字列ではなく要素的なパーサ関数の列であるが、連接、選択、繰り返しという処理については正規表現と同じようなイメージでプログラムできることを意味している。ただ、P モジュールの場合は、正規表現と違って、再帰的定義が行えるところが本質的に異なっている。

要するに、構文解析のパーサは再帰的定義もできる正規表現なのだというイメージをつかむことができれば、その働きがわかりやすくなる。プログラム言語の構文解析は、言語の文法をどうやって、要素的なパーサの連接、選択、繰り返しで表現できるかを考えればいいだけだからだ。

また、P モジュールの意味も、要素的なパーサの列の連接、選択、繰り返しのパターンを記述するためのものだと理解することで、利用法のイメージがスッキリする。文字列に対して正規表現が行っていることを、P モジュールの利用では、対象を文字列からパーサ関数の列に置き換えればいいだけだからだからだ。

P モジュールでやっているのは、パーサの連接を function() {return parser1() && parser2() && .. } で表現し、パーサの選択を funnction() {return parser1() || parser2() || ... } で表現し、パーサの0回以上の繰り返しを many( parser ) で表現しているだけだからだ。また、このような複合パーサは要素的なパーサと同列に扱うことができるから、正規表現ではできなかった再帰的定義も利用することができる(ただし、再帰的な展開を止める base case を意識していないと無限再帰を引き起こしてしまうが... )。さらに、パーサがマッチした時のアクションを P.pat() 関数でペアリングできるので、パターンのマッチだけではなく、直接処理や構文木の構築もできる。

P. モジュールの記述があまりにも単純なので、これで大丈夫なのだろうかと少々不安だったが、先読みつきLLパーサの構文解析はそれほど複雑なことをやっているわけではないのかもしれない。

P モジュールでは先読みをした時のバックトラックの処理や、パーサがマッチした時の文字列の消費の処理で文字列のコピーを行ってしまうので、オーバーヘッドが大きく、プログラム言語のパーサを作るのは難しいだろうが、正規表現では表現できない再帰的定義を含んだパターンの解析を手軽に行うという用途には便利ではないかと思う。

ただし、JavaScript の正規表現の適用が、文字列へのキャラクターポインターから開始できるようになれば、ソースの文字列をコピーしなくても良くなるので、結構実用的なパーサも作れるのではないかと思っている。

もっと良いのは先読みつきLLパーサを JavaScript の仕様に取り込んでくれることだ。これについては、正規表現を拡張して再帰的定義も含む変数の使用ができるようにして、さらに正規表現のマッチが起きた時のアクションをペアリングすることができるようにすれば、正規表現だけでシームレスに字句解析からパーサまで書けるようになるので便利だろう。

by tnomura9 | 2016-02-21 09:38 | JavaScript | Comments(0)
<< 正規表現とは何か フルスペック PEG パーサジ... >>