構文解析と云えば、BNF か ABNF か EBNFかな?作れたのは字句解析まで・・・orz

JavaScriptでRegExpだけで ソースコードの構文を構文解析しようとすれば、すぐに無理が来る。
昔から構文の説明する時にはBNF(バッカス・ナウア記法)が使われてきた。
ABC ::= A B C
な感じの書き方なので、本当に難しそうな文法の教科書向き。
しかし、繰り返し表現が無く
数字 ::= 0|1|2|3 … |9
数値 ::= 数字, 数値 | 数字
の様に再起表現に頼らざるを得ないので、どうしても説明が長くなるが、右寄せあるいは左寄せのいづれか一方のみの再起表現を使用すると制限を加えればパーサーは作りやすい仕様になっている。
EBNFは、
ABC = “A” , “B”,  “C” ;
な感じに書き方で、{ …} な繰り返し表現もあり、簡単な表現でパーサが書けそう。
本のBNFの記述でも {…} は0回以上の繰り返し可能なブロック、[…]は省略可能なブロック な表現を見かけたが、そう云うよく見かける拡張機能を組み込んだのがEBNFなのだろう。
XMLの文法を表現するために作られたという話もあるし、
誰もが心の中でBNFを勝手に拡張しているのは間違いない。
ただ、拡張の仕方は皆バラバラで方向性もマチマチなので、BNFを規約という形で拡張する様なことはC++の規約化と同様に「厳密にイミフな表現が可能」になり、愚の骨頂と云える様な結末に至るだろう。
※UTF-8で多国語のテキストを1つのHTMLにまとめることが出来るようになった、だからと云って万人がそれを読みこなせるハズも無く、多国語テキストの方向性に使い倒せるの人は極わずか人ダケということだ。
ABNFは、
ABC = %65  %66  %67 ;  コメント
な感じに書き方で、主に通信プロトコルの説明に向いているそうだ。
確かにアナライザーのログとにらめっこをするなら A や 漢 の文字表現より、 コード表現の方が便利そうだ。
・・・
まじめにパーサを作るならいづれかを選択するのが筋だろう。
でも、JavaScriptのRegExpのexecを字句解析に使う場合には
一般的なパーサの文法に縛られる必要な無いので、
“%%”
事前に定義したいJavaScriptのソースのコード
“%%”
トークン名=    (?: (“/” RegExpの字句解析のパターン “/”)  | ( トークン名) ){1,99}   “;”  “%%” returnでパーサーに答えを返す処理 “%%”

※RegExpの字句解析のパターンを複数書く場合はスペースで区切る。
※トークンの構文に対応するJavaScriptのソース;では字句解析のパターン中の(…)に対応する変数$1…$99 や $_や$@なども使える。
※少し工夫すれば、xxx: ([A-Z0-9_]+) ;  シンボル { return $1; } と書いても何とかなるハズ。
※処理を”%%”で括るのは、RegExpの/mでやっつけで処理したいから・・・(笑
・・・で、十分な気がする。
鋭意作成中・・・
謎の現象が発生。
1.{ 処理・・・処理 }
正規表現 (\{)((?:\\\{|\\\}|[^{}])+)(\}) が
1個目の{ ~最後の} までを処理してしまい、
“{“、その他、”}”、?EOT? と、解釈してしまった。
処理の結果は不可解だけど、
このパターンなら、途中の}に目もくれずできる限り遠くの}まで探索してくれることを覚えておいて損は無いだろう。
とりあえず、 (\{)([^{]+)(\}) で済ませたが、(\\{)((?:\\\\}|[^\\}])*)(\\}) が正解のようだ。
$1…$nに割り当てない文字のグループ表現(?: … )を使い、
}のエスケープシーケンス または }以外の文字を (?:\\\\}|[^\\}]) と表現すれば * で繰り返せばOK
2./RegExpのパターン/
(\/((?:\\\/|[^\/])+)\/) が1と同様に、
1個目の{ ~最後の} までを処理してしまい、
“/”、その他、”/”、?EOT? と、解釈してしまった。
とりあえず、 (\/([^\/]+)\/) で済ませるがが、やはり、(\\/)((?:\\\\/|[^\\/])*)(\\/) が正解のようだ。
3.字句解析の2周目の結果が・・・
NULL・・・NULL、””となって、無限ループ。
とりあえず、
最初にNULL以外で見つかった字句が空文字列の場合は
無視してlastIndexを1文字進める。
・・・
※正規表現の\\が多いのはnew RegExpのパラメータの文字列として組み込むため、\単体ではjavascriptのテキストのエスケープシーケンス扱いになるので\\と書いて\の文字扱いしてもらうため。
4.改行が空白として処理される
改行より手前に空白のトークンを宣言すると、空白扱いになっていたので、順を入れ替える。
正規表現を1つにまとめexecの結果で最初に文字列が入っている位置でトークンを分類する場合、トークンの順番を入れ替えるとexecの結果も入れ替わるので、各トークンの正規表現のテストパターンをトークン登録前のチェックでexecの結果の長さから、推定できるようにメモを取っておく。
やっと変な挙動の症状は落ち着いてきた。
最初は、{ 処理リスト } としていたが、処理リストの中のの{や}を¥{、¥}で書くのはやはり面倒。
{{処理リスト}}に変えてみると、”{”演算子が反応してしまったので・・・
%%処理リスト%%に変えてたのが・・・
想定外の文字列が混入していてもRegExp.exec( ) は、ガン無視するので
トークン:「その他」を追加。
RegExpの説明を読んでいると、

/<.*?>/ は “<foo> <bar>” の “<foo>” にマッチしますが、/<.*>/ は “<foo> <bar>” にマッチします。

というのを発見。.*の使用は要注意らしい。
もっとも、パターンの末尾以外に .* を使うと最後まで突っ走りそう、しかも今回はregExpのマルチラインモード(m)なので実質的に .* の使い道がないと思ってたので[^ストッパー文字]*[ストッパー文字]な感じに書いているので .*?[.*を止めるストッパー文字] で済むならストッパー文字を2度書きせずに済む。
但し、”*****************” は、'(“.*?”)’ と書けそうだが ”********\”*********” で破綻してしまうので、'(\\”(?:\\\\”|[^\\”])*\\”)’になっている。
各トークンの情報は格納できるようになった。
しかし、各トークンにパーサーの処理を組み込もうとするとやはり難しい。
トークンの名前が = の左側か右側かで、やるべきことが違うからだ。
なので、
1.RegExp.execでトークンに分解。
2.各トークンの処理はセルフチェックに抑える。
3.下記のEBNFの文法を・・・

%%処理リスト%%

トークン名宣言= (引用符文字列 | 正規表現 | トークン名参照) { 演算子   (引用符文字列 | 正規表現 | トークン名参照) }  “;” %%処理リスト%%

・・・

トークン名宣言= (引用符文字列 | 正規表現 | トークン名参照) { 演算子   (引用符文字列 | 正規表現 | トークン名参照) }  “;” %%処理リスト%%

サブルーチンの呼び出しで、なぞっていくことにする。
そうすることでトークン名を宣言版と参照版に事前に区別して呼び出すことができるからだ。
と大きく路線変更を決めた様な気がしたけど
トークン情報のリストに【メタな表現】のトークンが増えるだけなんだなぁ~(笑
4. 連想配列を多用していると、急にJavascriptが無効化される
とりあえず、jQUeryの初期化処理に $(‘#result’).val(“- – -“); を入れてJavascriptが無効化されたら何も出ないので判るようにした。
よーくみると、

{

‘name’:   null,

‘pattern’:     /RegExp/g

}

のハズが

{

‘name’:   null;

‘pattern’:     /RegExp/g;

}

と区切り方を間違えていた。
ブラウザのコンソールにエラーが出ないので、原因を掴むのが結構面倒。
根本的な原因はJavaScriptのどこかにtry…catch…を書くと、開発ツールのコンソール・タグに文法エラーすら出てこなくなる様だ。
なので、出来るだけtry…catch…をあてにしない様にしないと、括弧の付け忘れすら見つけるのが大変だ。(大笑
もっとも、それが原因で文法チェックしかできなくていいから自作のパーサーが欲しいなぁと思ってしまったんだけどね。
こうなると、行数がどんどん増えてくると、ケアレスミスすら捕まえるのが難しい。
トークンのパターンの括弧の扱いをどうしようか・・・のあたりで諦めた。
try…catch 無しで考え直すしかなさそう。
だが、他にも
コピペしたコードの消し忘れで
var msg = ‘message’ : “…”;
と 妙なところに : を書いてしまったり、
EBnf.prototype.parseEbnf = function(grammer) {
の最後の { を付け忘れても、ダンマリ(JavaScriptが動かない)ケースがあった。
また、とりあえず一時的にtry…catch を無効にしたい場合は

//    try {

・・・

/*   }  catch (ex) {

・・・

      }  */

が手っ取り早いが、

/*%%    try {   %%*/

・・・

/*%%   }  catch (ex) {

・・・

      }  %%*/

と*を*%%などあまり使わない表現を混ぜるとテキストエディタの正規表現検索で探しやすく、戻し忘れも防ぎやすいでお勧め。
そんな感じなので、ケアレスミスのチェックに手間取り、パーサーの進捗ははかどっていない。
まだまだ完成には程遠いが、ソース中の正規表現だけはすぐに使い回しが利きそうな気がしているので、EBNF書式のテキストを色付けするだけのサンプルを残す。字句解析しかないけど・・・
字句解析しかないから、
しっかりとRegExpのパターンを作り、適切な登録順で組み合わせれば、
JavaScript用も作れたので残しておく。(字句解析しかしてないけどね。
selfCheckの呼び出しもRegExpのパターン情報をコピーしたtknを呼び出し、
rc = tkn.selfCheck( this, tkns[offset], tkns[offset+1], tkns[offset+2] );
と変えたので、特定の用語だけ色を変えることも可能なハズ。
想定外のパターンに出会えば【その他】が反応し、背景色:赤、文字色:黄で派手にしてあるのでデバッグも容易。(大笑
/* … */ なコメントも追加。予想通り /RegExpパターン/が先に反応したので それより先に配置。コメント解析がいくつもあるのも嫌なので、( //…  |  /*…*/  |  (*…*)  )を1つにまとめてみると
(/{2}.*$|\\/\\*(?:\\*(?!\\))|[^\\*])+\\*\\/|\\(\\*(?:\\*(?!\\))|[^\\*])+\\*\\))
コメントを判定するダケの正規表現なのに・・・明らかにイミフだ。(大笑

ソース・コードのコメントに色付けしたいダケ

なら、

ソースコード.replace(

/(/{2}.*$|\\/\\*(?:\\*(?!\\))|[^\\*])+\\*\\/|\\(\\*(?:\\*(?!\\))|[^\\*])+\\*\\))/mg ,

function ($0,$1) {

  return “<span style=\”color=#00ff00\”>” + $1 + “</span>”;

});

とでも書けばいいのかな?
コメントの種類ごとに色訳けしたいなら

ソースコード.replace(/(/{2}.*$)/mg ,function ($0,$1) {

  return “<span style=\”color=#00ff00\”>” + $1 + “</span>”;

}) . replace(/(\\/\\*(?:\\*(?!\\))|[^\\*])+\\*\\/)/mg ,function ($0,$1) {

  return “<span style=\”color=#0000ff\”>” + $1 + “</span>”;

}) . replace(/(\\(\\*(?:\\*(?!\\))|[^\\*])+\\*\\))/mg ,function ($0,$1) {

  return “<span style=\”color=#ff0000\”>” + $1 + “</span>”;

});

とreplaceを結合すればいいのだろう。
※コメントはよく行をまたぐので、最後のは必須。
これでもいいのかもしれないが
こんな風にRegExpで頑張るよりも
パーサー・コンビネーターで、
ノソノソと解析させた方が可読性は格段に高いハズ。
字句解析を連想配列化しているが、構文解析はついついハードコードしてしまい1000行オーバーな雰囲気から抜け出ないので連想配列化した方がいいのかな

{

name:  式,

pattern:    “項 [ 演算子 式 ] | ‘(‘ 式 ‘) ‘”,

testpattern: “1+2”,

proc: function(p1,p2) {

return  p1+p2;

}

}

な雰囲気で並べて動かせばゴソっと行数は減るような気もするが、構文パターンの中の演算子” | “やグループやオプション表現はやはりハードコードになるのかな。勿論、このpattern用の字句解析の連想配列も作っておこう。




コメントを残す

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

CAPTCHA