Объясните, как работает грамматика регулярных выражений ECMAScript

@GoldenId · Регистрация: 11.11.2010

Студворк — интернет-сервис помощи студентам

Читаю раздел Alternatives документации по грамматике ECMAScript и не понимаю ни описание механизма работы данной реализации регулярных выражений, ни выдачи примера:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <cstddef>
#include <iostream>
#include <regex>
#include <string>
 
void show_matches(const std::string& in, const std::string& re)
{
    std::smatch m;
    std::regex_search(in, m, std::regex(re));
    if (!m.empty())
    {
        std::cout << "input=[" << in << "], regex=[" << re << "]\n  "
                     "prefix=[" << m.prefix() << "]\n  smatch: ";
        for (std::size_t n = 0; n < m.size(); ++n)
            std::cout << "m[" << n << "]=[" << m[n] << "] ";
        std::cout << "\n  suffix=[" << m.suffix() << "]\n";
    }
    else
        std::cout << "input=[" << in << "], regex=[" << re << "]: NO MATCH\n";
}
 
int main()
{
    show_matches("abcdef", "abc|def");
    show_matches("abc", "ab|abc"); // left Alernative matched first
 
    // Match of the input against the left Alternative (a) followed
    // by the remained of the regex (c|bc) succeeds, which results
    // in m[1]="a" and m[4]="bc".
    // The skipped Alternatives (ab) and (c) leave their submatches
    // m[3] and m[5] empty.
    show_matches("abc", "((a)|(ab))((c)|(bc))");
}

выдача:

Code
1
2
3
4
5
6
7
8
9
10
11
12
input=[abcdef], regex=[abc|def]
  prefix=[]
  smatch: m[0]=[abc]
  suffix=[def]
input=[abc], regex=[ab|abc]
  prefix=[]
  smatch: m[0]=[ab]
  suffix=[c]
input=[abc], regex=[((a)|(ab))((c)|(bc))]
  prefix=[]
  smatch: m[0]=[abc] m[1]=[a] m[2]=[a] m[3]=[] m[4]=[bc] m[5]=[] m[6]=[bc]
  suffix=[]

По крайней мере в последнем ( из 3 ) случае выдача ( по идее логики идеального автомата ) должна быть ( с точностью до порядка и повторений ) следующей:

Code
1
abc

,
Со следующим порядком работы:

Code
1
2
3
4
a+c - нет,
a+bc - в выдачу,
ab+c - в выдачу, повтор
ab+bc - нет.

Текст раздела прочитал несколько раз, в том числе с переводом на русский - - всё равно логика работы алгоритма не ясна.

@GoldenId · 14.02.2024, 12:39 **[ТС]**

Собственно текст раздела Alternatives документации по грамматике ECMAScript:

«A regular expression pattern is sequence of one or more Alternatives, separated by the disjunction operator | (in other words, the disjunction operator has the lowest precedence)

Pattern ::

Disjunction
Disjunction ::

Alternative
Alternative | Disjunction

The pattern first tries to skip the Disjunction and match the left Alternative followed by the rest of the regular expression (after the Disjunction).

If it fails, it tries to skip the left Alternative and match the right Disjunction (followed by the rest of the regular expression).

If the left Alternative, the right Disjunction, and the remainder of the regular expression all have choice points, all choices in the remainder of the expression are tried before moving on to the next choice in the left Alternative. If choices in the left Alternative are exhausted, the right Disjunction is tried instead of the left Alternative.

Any capturing parentheses inside a skipped Alternative produce empty submatches.».

@nmcf · 14.02.2024, 17:41

Что именно не ясно?

@GoldenId · 14.02.2024, 19:51 **[ТС]**

nmcf,

Что такое choice points?

Что такое choices?

Почему вызов:

C++
1
show_matches("abc", "((a)|(ab))((c)|(bc))");

даёт ( в частности ) вывод:

Code
1
 smatch: m[0]=[abc] m[1]=[a] m[2]=[a] m[3]=[] m[4]=[bc] m[5]=[] m[6]=[bc]

,

а не

Code
1
smatch: m[0]=[abc], m[1]=[abc]

по логике, описанной в конце заглавного поста?

@nmcf · 14.02.2024, 19:59

Ну как я понял, слева направо смотрит. m[0] - это весь шаблон. А дальше идут группы по вложенности.
m[1]: ((a)|(ab))
m[2], m[3]: (a), (ab)
Так же с ((c)|(bc)).

Добавлено через 1 минуту
Т. е. скобки эти дерево образуют.

@GoldenId · 18.02.2024, 12:00 **[ТС]**

nmcf, но ведь должна быть канкатенация?
Из "(a|ab)(c|bc)" есть два узла:
"(a|ab)" и "(c|bc)" - - две дизъюнкции, из каждой из которых должна быть выбрана одна альтернатива:
"(a|ab)" -> "a" либо "ab"
"(c|bc)" -> "c" либо "bc",
и дальше сканкатенировать их варианты так, чтобы в обрабатываемый сиквенс укладывалось, там было.
Разве не так?

@nmcf · 18.02.2024, 12:35

Не очень понимаю, о чём ты. Почему не получается ab+c? Потому что слева направо. Если найдено совпадение с левой частью, то правая уже не рассматривается.

Новые блоги и статьи Все статьи Все блоги /
Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Programma_Boinc 28.12.2025 Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / ********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / ********/ gallery/ bKBkQFf Пост отсюда. . .	Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США. Programma_Boinc 26.12.2025 Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .	Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Programma_Boinc 23.12.2025 Рецензия / Мнение/ Перевод Нашел на реддите интересную статью под названием The Thinkpad X220 Tablet is the best budget school laptop period . Ниже её машинный перевод. Thinkpad X220 Tablet —. . .	PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Как объединить две одинаковые БД Access с разными данными VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.
Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .	Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .

@GoldenId 142 / 143 / 64 Регистрация: 11.11.2010 Сообщений: 877 Записей в блоге: 10
	14.02.2024, 12:39 [ТС]
	Собственно текст раздела `Alternatives` документации по грамматике ECMAScript: «A regular expression pattern is sequence of one or more Alternatives, separated by the disjunction operator \| (in other words, the disjunction operator has the lowest precedence) Pattern :: Disjunction Disjunction :: Alternative Alternative \| Disjunction The pattern first tries to skip the Disjunction and match the left Alternative followed by the rest of the regular expression (after the Disjunction). If it fails, it tries to skip the left Alternative and match the right Disjunction (followed by the rest of the regular expression). If the left Alternative, the right Disjunction, and the remainder of the regular expression all have choice points, all choices in the remainder of the expression are tried before moving on to the next choice in the left Alternative. If choices in the left Alternative are exhausted, the right Disjunction is tried instead of the left Alternative. Any capturing parentheses inside a skipped Alternative produce empty submatches.». 0

@nmcf 7804 / 6568 / 2988 Регистрация: 14.04.2014 Сообщений: 28,705
	14.02.2024, 17:41
	Что именно не ясно? 0

@nmcf 7804 / 6568 / 2988 Регистрация: 14.04.2014 Сообщений: 28,705
	14.02.2024, 19:59
	Ну как я понял, слева направо смотрит. m[0] - это весь шаблон. А дальше идут группы по вложенности. m[1]: ((a)\|(ab)) m[2], m[3]: (a), (ab) Так же с ((c)\|(bc)). Добавлено через 1 минуту Т. е. скобки эти дерево образуют. 1

@GoldenId 142 / 143 / 64 Регистрация: 11.11.2010 Сообщений: 877 Записей в блоге: 10
	18.02.2024, 12:00 [ТС]
	nmcf, но ведь должна быть канкатенация? Из "(a\|ab)(c\|bc)" есть два узла: "(a\|ab)" и "(c\|bc)" - - две дизъюнкции, из каждой из которых должна быть выбрана одна альтернатива: "(a\|ab)" -> "a" либо "ab" "(c\|bc)" -> "c" либо "bc", и дальше сканкатенировать их варианты так, чтобы в обрабатываемый сиквенс укладывалось, там было. Разве не так? 0

@nmcf 7804 / 6568 / 2988 Регистрация: 14.04.2014 Сообщений: 28,705
	18.02.2024, 12:35
	Не очень понимаю, о чём ты. Почему не получается ab+c? Потому что слева направо. Если найдено совпадение с левой частью, то правая уже не рассматривается. 0