Явная проблема с поведением подстроки в JavaScript

Question

Я пишу рекурсивный алгоритм для построения автомата конечного состояния путем разбора регулярного выражения. Автомат выполняет итерацию через выражение, выталкивая символы в стек и операторы в «стек оператора». Когда я сталкиваюсь с «(» (указывая операцию группировки), я нажимаю «вспомогательный автомат» в стек и передаю остальную часть шаблона на вспомогательный автомат для разбора. Когда этот автомат встречает «)», он передает остальную часть строка до родительского автомата, чтобы закончить синтаксический анализ. Вот код:

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)); 
    } 
    } 
}; 

Обратите внимание на область с надписью «TROUBLE SPOT». Учитывая регулярное выражение «(a | b) a», вызов this.parent.parse вызывается ровно один раз: когда подавтомат встречает «)». На этом этапе pattern.substring (i, pattern.length) = ") a". Это «работает», но это неверно, потому что мне нужно использовать «)», прежде чем передать строку в родительский автомат. Однако, если я изменяю вызов this.parent.parse (pattern.substring (i + 1, pattern.length), синтаксический анализ получает пустую строку! Я попытался пройти через код, и я не могу объяснить это поведение. Я пропустил?

По предложению Хуана я сделал быстрый jsfiddle, чтобы показать проблему при попытке разобрать «(a | b)» с помощью этого алгоритма. В случае «)» он заполняет пустой div с помощью подстроку в индексе i и подстроку в индексе i + 1. Он показывает, что, хотя в подстроке в i есть 2 символа, подстрока в i + 1 является пустой строкой! Вот ссылка: http://jsfiddle.net/XC6QM/1/

EDIT: Я отредактировал этот вопрос, чтобы отразить тот факт, что использование charAt (i) не изменяет поведения алгоритма.

Answer 1

Настоящая проблема заключается в том, что вы использовали for in для перебора символов строки. С циклом for in ваш i будет строкой, поэтому, когда вы попытаетесь сделать i+1, это будет строка конкатенации.

Если вы измените итерацию быть

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

Тогда все работает отлично http://jsfiddle.net/XC6QM/2/

ответ Скотта правильно определил эту проблему, но я думаю, что его решение (преобразование индексов чисел) не является идеальным. Вы лучше зацикливание с числовым индексом, чтобы начать с

Кроме того, вы не должны использовать скобки для доступа к символам в строке, that does not work in IE 7

switch(pattern[i]) { 

должен быть

switch(pattern.charAt(i)) { 

Answer 2

Я думаю, предыдущий ответ был на правильном пути. Но мне также кажется, что я ошибаюсь. Разве вы не должны увеличивать индекс своей подстроки? Вы не хотите включать «)» в родительский синтаксический разбор, верно?

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

Но это все равно не удастся из-за ошибки, упомянутой Хуаном. Быстрое временное решение, чтобы проверить это было бы преобразовать i в номер:

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

Это может сделать это для вас. Но вы, вероятно, должны вернуться назад и отключиться от цикла for-in на строке. Я думаю, что это вызывает вашу проблему.Поверните его в массив с str.split(''), а затем используйте целое число для цикла. Это предотвратит дальнейшие такие проблемы.