Проверьте, является ли строка префиксом Javascript RegExp - PullRequest
Новая
       13

Проверьте, является ли строка префиксом Javascript RegExp

13 голосов
/ 06 января 2009

В Javascript я определил регулярное выражение, и теперь пользователь печатает строку. Я хочу сказать ему, может ли его строка все еще соответствовать RegExp, если он продолжает печатать или он уже ошибается. Например: 

var re = /a*b/;

"a".isPrefixOf( re ); // true
"x".isPrefixOf( re ); // false

Как может выглядеть реализация isPrefixOf?

Обновление: Спасибо за ваши ответы, кажется, что хороший обходной путь, по мнению Брэда, - сделать доказательство регулярного выражения регулярным. Но я все еще пытаюсь найти общее решение.

Может быть, так: мы создаем новое регулярное выражение с пользовательским вводом, за которым следует .*. Это регулярное выражение описывает все слова, которые пользователь еще может ввести. Если пересечение этого созданного регулярного выражения и исходного регулярного выражения пусто, то пользователь уже находится на неправильном пути. Если нет, то у него все хорошо. Например: 

var re = /a*b/;
var sInput = "a";
var reInput = new RegExp( sInput + ".*" );

reIntersection = re.intersect( reInput );
reIntersection.isEmpty(); // false

intersect() возвращает новое регулярное выражение, которое принимает только слова, которые могут принять и re, и reInput. Функция еще не существует, но мы можем реализовать ее, используя предварительный просмотр: 

RegExp.prototype.intersect = function( pattern2 ) { 
    return new RegExp( '(?=' + this.source  + ')' + pattern2.source );
}

Что остается открытым, так это функция isEmpty(). Как мы можем проверить, соответствует ли регулярное выражение Javascript какому-либо слову или оно пустое?

Ответы [ 5 ]

4 голосов
/ 06 января 2009

Люди, похоже, делятся поровну на то, как они интерпретируют этот вопрос, поэтому я продемонстрирую концепцию на примере Java. 

import java.util.regex.*;

public class Test
{

  public static void main(String[] args) throws Exception
  {
    tryMatch("^a*b+$", "a", "ab", "abc");
  }

  public static void tryMatch(String regex, String... targets)
  {
    Pattern p = Pattern.compile(regex);
    Matcher m = p.matcher("");
    System.out.printf("%nregex: %s%n", regex);
    System.out.printf("target | matches() | hitEnd()%n");
    for (String str : targets)
    {
      m.reset(str);
      System.out.printf("%-6s | %-9B | %-9B%n",
          str, m.matches(), m.hitEnd());
    }
  }
}

выход: 

regex: ^a*b+$
target | matches() | hitEnd()
a      | FALSE     | TRUE
ab     | TRUE      | TRUE
abc    | FALSE     | FALSE

Целевая строка «a» не совпадает, поскольку регулярному выражению требуется хотя бы один b, но это может быть префикс успешного совпадения, поэтому hitEnd() возвращает true. Строка «ab» содержит все, что требуется для совпадения, но оно также будет соответствовать, если мы добавим больше b в конец, поэтому hitEnd() по-прежнему возвращает true. При использовании «abc» попытка сопоставления завершается неудачно, пока не достигнет конца целевой строки, поэтому регулярное выражение не может найти соответствие ни одной строке, начинающейся с «abc».

Насколько я знаю, в Javascript нет ничего похожего на Java hitEnd() метод, но может быть возможно его подделать. Если кто-нибудь знает как, то это будет тот вопиющий задира Стивен Левитан .

3 голосов
/ 06 января 2009

Я думаю, что вам лучше всего сделать так, чтобы ваш Regex был защищен от префиксов. Для примера, который вы привели, /a*b/, я думаю, вы могли бы использовать /a*b?/.test(userinput). Для более сложных шаблонов это может становиться все труднее, но я все еще думаю, что это можно сделать, вложив каждое подвыражение в серию необязательных квантификаторов (?). Например: 

/a*bcd*e/

Префиксное регулярное выражение может быть: 

/a*(b(c(d*e?)?)?)?/

Это немного грязно, но, я думаю, это решит твою проблему.

2 голосов
/ 06 января 2009

Очень интересный вопрос. В моем быстром поиске я не нашел ничего предопределенного (даже в Perl), которое решает эту проблему.

РЕДАКТИРОВАТЬ: Ой, похоже, у Java есть нечто подобное, называется hitEnd () - см. Ответ Алана М. HitEnd () говорит, что результат match () (true или false) может быть изменен дополнительным вводом. В книге «Освоение регулярных выражений» говорится, что она не очень надежна (не знаю почему, страница 392 недоступна в книгах Google).

В зависимости от того, какие функции регулярных выражений вы используете, быстрый взлом, например, написание каких-то префиксов вашего регулярного выражения:

например. для a + a * b + c ваши префиксы будут: 

a+
a+a*
a+a*b+
a+a*b+c

и попытайтесь сопоставить любой из них с вашей строкой, может сработать. Этот быстрый взлом усложняется, если вы используете оператор выбора, если вы используете оператор диапазона {n, m} или обратные ссылки.

При этом, я думаю, хорошее решение - это немного изменить алгоритм сопоставления.

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

При этом вам, вероятно, придется реализовать алгоритм в JavaScript. Надеюсь, это станет частью таких библиотек, как Jquery.

Дополнительную информацию и теорию алгоритма можно найти в этой статье:

http://swtch.com/~rsc/regexp/regexp1.html

(даже если он рассматривает алгоритм обратного отслеживания и предлагает алгоритм на основе FA (но FA не может обрабатывать обратные ссылки)).

0 голосов
/ 06 января 2009

Одним из способов сделать это может быть привязка к событию onKeyUp текстового поля и .test текста к регулярному выражению. Конечно, я предполагаю, что вы хотите выполнить сопоставление с регулярным выражением. Я не уверен, что это именно то, что вам нужно, на самом деле ваш код: 

"a".isPrefixOf( re ); // true

никогда не будет совпадать, поскольку требуется также иметь последующий символ "b" (вы можете захотеть изменить регулярное выражение). Например, этот код будет проверять любую строку, соответствующую этому формату: 

a-n(n)-b

Вот код, сохраните его как страницу и загрузите в браузере: 

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="it">
<body>
    <input type="text" size="20" id="txtData" onkeyup="showResult()" />
    <div id="dvResult" />
</body>
</html>
<script type="text/javascript">
//<![CDATA[

    theRegExp = /^a\-\d{1,2}\-b$/;

    function isPrefixOf( aText, aRegExp )
    {
        return aRegExp.test( aText );
    }

    function showResult()
    {
        res = document.getElementById( "dvResult" );
        res.innerHTML = isPrefixOf( document.getElementById( "txtData" ).value, theRegExp ) ? "Correct" : "Bad input";
    }

//]]>
</script>
0 голосов
/ 06 января 2009

Сначала вы определяете свое регулярное выражение как: var re = new RegExp (/ ^ (regexp здесь) $ /);

в событии onKeypress вы проверяете регулярное выражение следующим образом:

text.match (regexp) - где текст является введенной строкой.

Это ясно?

...