[ブログ]パーサーコンビネータ

parser.js

//最初に読んだ時の俺の感想
//死ぬｗｗｗｗｗなんだこれｗｗｗｗ高階関数のオーバーライドｗｗｗ


//基礎知識
//function (){return function(){ return function(){}}}//再帰
/*
function A(){
  return function Achild(hoge){
  
  }
}
function B(tes){
  return function Bchild(){
   tes("hogehoge");//この時点でAchildのreturnが返ってくる(↓の実行の仕方をした時)
  }
}
B(A("tes"))()
1.B(A("tes"))//Aの返り値（Achild）をBに渡す
2.Bの返り値(Bchild)の中でAchildがこねくり回される
*/


/*
 * 
 * この画面は JavaScript スクラッチパッドです。
 *
 * JavaScript を入力して、右クリックまたは [実行] メニューを選択してください。
 * 1. 実行: 選択したコードを実行します。(Ctrl+R)
 * 2. 調査: 実行結果をオブジェクトインスペクタで表示します。(Ctrl+I)
 * 3. 表示: 選択したコードの後ろに、実行結果をコメント形式で挿入します。(Ctrl+L)
 */

/*
パーサーコンビネーターを書いてみる
関数を渡していじる

パーサコンビネータでは、パーサを関数として扱っていくが、その関数はどのような入力と出力を取るのだろうか? どのようなパーサコンビネータのライブラリでも基本的にはパーサは以下のよう入力と出力をベースにしている。

    入力: パースする文字列、現在の読み取り位置
    出力: パースが成功したかどうか、パースされた結果、新しい読み取り位置

この辺は自分でかってに定義した
定義：パーサー（パーサー関数）。。。文字列を受け取り関数を返す
定義：コンビネータ（パーサーパーサー）。。。パーサーを受け取り連続処理したりする関数を返す。
*/
/** パーサーを受け取り、実行した後受け取って失敗（文字列が見つからないとか）し
てもtrueにする
 * @param {Function} parser
 * @return {Function}
 */
function option(parser) {
  console.log("option")
  return function(target, position) {
    console.log("optionin")
    var result = parser(target, position);
    if (result[0]) {
      return result;
    } else {
      return [true, null, position];
    }
  };
}
/*
文字列targetからパース式(正規表現式)strでフィルターするパーサーを返す
@param {string} str パース式（正規表現式)
@return {function} parser(target,length) パーサーを返す
@param {string} target - 文字列そのもの（といっても再帰でどんどん小さくなってくけどね
@param {int} len なん文字目から？
*/
function token(str){
  console.log("token")
  return function(target,posi){ 
    console.log("tokenin")
    let rensyu1,rensyu2;
    rensyu1=target.substr(posi,str.length);//posiからlength文字分
    rensyu2=target.substring(posi,posi+str.length);//posiからlength－１まで  
    //substr  一番目の引数から2番めの引数をプラスしたとこまで
    //substring 1から2-1まで
    let boolean;
    let resulttext;
    let newposi;
    if(rensyu1==str&&rensyu1==rensyu2){
      boolean=true;
      resulttext=str;
      newposi=posi+4;
    }else{
      boolean=false;
      resulttext=null;
      newposi=posi;
    }
    return [boolean,resulttext,newposi];
  }
}

/**受け取った順に実行して一つでも失敗するとfalseを返す./(foo|bar)baz/みたいな
感じで最初から順に
 * @param {Array} parsers... 結合するパーサの配列
 * @return {Function} パーサ
 */
function seq(/* parsers... */) {
  console.log("seq")
  var parsers = arguments;
  return function(target, position) {
    console.log("seqin");
    var result = [];
    for (var i = 0; i < parsers.length; i++) {
      var parsed = parsers[i](target, position);

      if (parsed[0]) {
        result.push(parsed[1]);
        position = parsed[2];
      } else {
        // 一つでも失敗を返せば、このパーサ自体が失敗を返す
        return [false, null, position];
      }
      
    }
    return [true, result, position];
  };
}

/*
遅延評価らしい。
パーサーAreturnを受け取りlazyreturn内でAreturnを実行した後そのreturnを返す。
function A(){
	return function Achild(){
		return Achildchild(){
		//ここがlazyのreturn時に実行される
		}
	}
}
lazy(A("string"));

*/
function lazy(callback) {
  console.log("lazy");
  var parse;
  return function(target, position) {
    if (!parse) {
     console.log("lazyinnner");
      parse = callback();
    }    
    return parse(target, position);
  };
}
console.log("root");
var parse=option(seq(token("hoge"),lazy(function(){return parse;})));
//parse("hoge",0);
console.log("initend")
//console.log(parse)
parse('hogehogehoge', 0); // => [true, ['hoge', ['hoge', ['hoge', null]]], 12]が返る
console.log("end");

/*

https://teratail.com/questions/20423

var ptrf=function tes(){return ptrf;}
alert(ptrf());//tes関数オブジェクト
上にも書いてあるがポインターとして考えるとわかりやすい
まあ上の質問者はおれなんだけどね
return ptrfの中にはtes関数への参照が入っている


これをparseに適用すると、parseの中にはoption(...)への参照が入っている
return parseの直前にconsole.log(parse)をするとoptionが表示されるし
initendの直後にもoptionが入ってる。

実行順序

root Scratchpad/4:117:1
token Scratchpad/4:56:3
lazy Scratchpad/4:107:3
seq Scratchpad/4:85:3
option Scratchpad/4:37:3
initend Scratchpad/4:120:1
optionin Scratchpad/4:39:5
seqin Scratchpad/4:88:5
tokenin Scratchpad/4:58:5
lazyinnner Scratchpad/4:111:6
optionin Scratchpad/4:39:5
seqin Scratchpad/4:88:5
tokenin Scratchpad/4:58:5
optionin Scratchpad/4:39:5
seqin Scratchpad/4:88:5
tokenin Scratchpad/4:58:5
optionin Scratchpad/4:39:5
seqin Scratchpad/4:88:5
tokenin Scratchpad/4:58:5
end

lazyのexampleの動き
1とりあえずtokenparseで"hoge"正規表現式を標的にするパーサをリターン
2.lazyもfunctionをリターン
3,この帰ってきたfunctionたちを引数にしてseqを実行。functionを返す。環境は保存される。
4,optionもfunctionを返す。
5,parseはoptionから帰ってきたfunction
6,jsのイベントバブリングみたいにする
7,optionの高階関数、seqの高階関数、tokenの高階関数、lazyの高階関数の順に実行（◯◯inと呼ぶ）


7,seqまでtargetとpositionはそのまま渡される(seqはひとつずつ実行してひとつでも失敗するとfalseを返す)
8,tokeninにもtargetとpositionはそのままいってtrueを返す。posisionは4になる[true,"hoge",4]



9,lazyのreturn parseは自分を返す。

  return function(target, position) {
    if (!parse) {
     console.log("lazyinnner")
      parse = callback();
    }    
    return parse(target, position);
  };
がseq()から引数"hogehogehoge"と0を渡されて呼び出される
callbackにはparseが入っている

9,lazyにもtargetとpositionが渡るが内部のcallbackでparseが返されそれが実行される(parseの中身は上を参照)
10,7~9を繰り返す。
11,最後にhogeがこれ以上ないのでtokenがfalseを返してseqは一つでも失敗するとfalseを返すのでoptionに入ってtrueに書き換えられる
12,optionから実行結果の配列が帰ってきて終わり。
*/
/*
true,hoge,hoge,hoge,,12
*/