1

正規表現を解析して有限状態オートマトンを構築する再帰アルゴリズムを書いています。オートマトンは式を繰り返し処理し、文字をスタックにプッシュし、演算子を「演算子スタック」にプッシュします。「（」（グループ化操作を示す）に遭遇すると、「サブオートマトン」をスタックにプッシュし、パターンの残りをサブオートマトンに渡して解析します。そのオートマトンが「）」に遭遇すると、残りの部分を渡します。解析を終了する親オートマトンまでの文字列。コードは次のとおりです。

var NFA = function(par) {
  this.stack = [];
  this.op_stack = [];
  this.parent = par;

};

NFA.prototype.parse = function(pattern) {
  var done = false;
  for(var i in pattern) {
    if (done === true) {
      break;
    }
    switch(pattern.charAt(i)) {
      case "(":
        var sub_nfa = new NFA(this);
        this.stack.push(sub_nfa);
        sub_nfa.parse(pattern.substring(i+1, pattern.length));
        done = true;
        break;
      case ")":
        if (this.parent !== null) {
          var len = pattern.length;
          /*TROUBLE SPOT*/
          this.parent.parse(pattern.substring(i, pattern.length));
          done = true;
          break;
        }
      case "*":
        this.op_stack.push(operator.KLEENE);
        break;
      case "|":
        this.op_stack.push(operator.UNION);
        break;
      default:
        if(this.stack.length > 0) {
          //only push concat after we see at least one symbol
          this.op_stack.push(operator.CONCAT);        
        }
        this.stack.push(pattern.charAt(i));
    }
  }
};

「TROUBLESPOT」とマークされた領域に注意してください。正規表現"（a | b）a"が与えられた場合、this.parent.parseの呼び出しは、サブオートマトンが "）"に遭遇したときに1回だけ呼び出されます。この時点で、pattern.substring（i、pattern.length）= "）a"です。これは「機能」しますが、文字列を親オートマトンに渡す前に「）」入力を消費する必要があるため、正しくありません。ただし、this.parent.parse（pattern.substring（i + 1、pattern.length））の呼び出しを変更すると、parseは空の文字列を渡されます！コードをステップ実行しようとしましたが、この動作を説明できません。私は行方不明ですか？

Juanの提案で、このアルゴリズムで「（a | b）a」を解析しようとしたときの問題を示すために、簡単なjsfiddleを作成しました。「）」の場合、空のdivにiインデックスのサブストリングとi+1インデックスのサブストリングが入力されます。iの部分文字列には2文字ありますが、i+1の部分文字列は空の文字列であることを示しています。リンクは次のとおりです：http：//jsfiddle.net/XC6QM/1/

編集：charAt（i）を使用してもアルゴリズムの動作が変わらないという事実を反映するために、この質問を編集しました。

4

2 に答える 2

1

前の答えは正しい方向に進んでいたと思います。しかし、私には1つずつエラーがあるようにも見えます。サブストリングのインデックスを増やすべきではありませんか？親の解析に「）」を含めたくないですよね？

this.parent.parse(pattern.substring(i + 1, pattern.length));

しかし、フアンが述べたエラーのため、これはまだ失敗します。iこれをテストするための簡単な一時的な修正は、を数値に変換することです。

this.parent.parse(pattern.substring(+i + 1, pattern.length));

これはあなたのためにそれをするかもしれません。ただし、おそらく戻っfor-inて、文字列のループから離れる必要があります。それがあなたの問題を引き起こしていると思います。で配列に変換してstr.split('')から、整数を使用してループします。それはそれ以上のそのような問題を防ぐでしょう。

于 2013-02-19T19:15:54.040 に答える
0

for in本当の問題は、文字列の文字を反復処理するためにを使用していたという事実です。for in ループを使用iすると、文字列になります。したがって、実行しようとするとi+1、文字列の連結が行われます。

反復を次のように変更した場合

for(var i=0; i < pattern.length; i++) {

その後、すべて正常に動作しますhttp://jsfiddle.net/XC6QM/2/

スコットの答えは問題を正しく特定しましたが、彼の解決策（インデックスを数値に変換する）は理想的ではないと思います。最初に数値インデックスでループする方が良いです

また、 IE7では機能しない文字列内の文字にアクセスするために角かっこを使用しないでください。 

 switch(pattern[i]) {

する必要があります

 switch(pattern.charAt(i)) {
于 2013-02-19T18:46:59.917 に答える