Оператор чередования регулярных выражений Java "|"поведение кажется нарушенным - PullRequest
Новая
       34

Оператор чередования регулярных выражений Java "|"поведение кажется нарушенным

11 голосов
/ 23 декабря 2010

Попытка написать регулярное выражение для римских чисел. В sed (который я считаю «стандартным» для регулярных выражений?), Если у вас есть несколько опций, разделенных оператором альтернирования, он будет соответствовать самому длинному. А именно, "I|II|III|IV" будет соответствовать "IV" для "IV" и "III" для "III"

В Java один и тот же шаблон соответствует «I» для «IV» и «I» для «III». Оказывается, Java выбирает между чередованием совпадений слева направо; то есть, потому что «I» появляется перед «III» в регулярном выражении, оно совпадает. Если я изменю регулярное выражение на "IV|III|II|I", поведение будет исправлено, но это, очевидно, не является решением в целом.

Есть ли способ заставить Java выбирать самое длинное совпадение из группы альтернатив вместо выбора первого?

Пример кода для наглядности: 

public static void main(String[] args)
{
    Pattern p = Pattern.compile("six|sixty");
    Matcher m = p.matcher("The year was nineteen sixty five.");
    if (m.find())
    {
        System.out.println(m.group());
    }
    else
    {
        System.out.println("wtf?");
    }
}

Это выводит "six"

Ответы [ 2 ]

18 голосов
/ 23 декабря 2010

Нет, он ведет себя правильно. В Java используется NFA или разновидность, ориентированная на регулярные выражения, например Perl, .NET, JavaScript и т. Д., И в отличие от sed, grep или awk. Ожидается, что чередование прекратится, как только совпадет одна из альтернатив, и не продержится дольше всего.

Вы можете принудительно продолжить его, добавив условие после чередования, которое не может быть выполнено, пока не будет использован весь токен. Что это может быть за условие, зависит от контекста; самым простым вариантом будет привязка ($) или граница слова (\b). 

"\\b(I|II|III|IV)\\b"

РЕДАКТИРОВАТЬ: я должен упомянуть, что, хотя grep, sed, awk и другие традиционно используют текстовые (или DFA) движки, вы также можете найти версии некоторых из них, которые используют движки NFA, или даже гибриды двух.

3 голосов
/ 23 декабря 2010

Я думаю, что шаблон, который будет работать, похож на

IV|I{1,3}

См. Раздел «Жадные квантификаторы» в http://download.oracle.com/javase/1.4.2/docs/api/java/util/regex/Pattern.html

Редактировать: в ответ наВаш комментарий, я думаю, что общая проблема заключается в том, что вы продолжаете использовать чередование, когда это не правильно.В вашем новом примере вы пытаетесь сопоставить «шесть» или «шестьдесят»;правильный шаблон для использования - six(ty)?, а не six|sixty.В общем, если у вас когда-либо есть два члена группы альтернатив, так что один является префиксом другого, вам следует переписать регулярное выражение, чтобы устранить его.В противном случае вы не сможете жаловаться, что движок делает не то, что нужно, поскольку семантика чередования ничего не говорит о самом длинном совпадении.

Правка 2: буквальный ответ на ваш вопрос - нет,это не может быть принудительно (и мой комментарий заключается в том, что вам никогда не нужно такое поведение).

Редактировать 3: больше думая о предмете, мне пришло в голову, что шаблон чередования, где одна строка являетсяпрефикс другого нежелателен по другой причине;а именно, это будет медленнее, если базовый автомат не будет создан для учета префиксов (и учитывая, что Java выбирает первое совпадение в шаблоне, я бы предположил, что это не так).

...