Здравствуйте, Mamut, Вы писали:

M>То есть
M>

M>rule <- .* (12|23) .*
M>

M>вроде ведь тоже неоднозначно вроде?
В ПЕГе нет неоднозначностей. Вообще.
В ПЕГе операторы жадные и не уступчивые.
Таким образом первый же .* сожрет весь текст и (12|23) никогда не сматчиться.
После чего все правило откатиться.
Если тебе хочется такое распарсить то нужно делать так

rule <- (!(12|23) .)* (12|23) .*

Таким образом первая * будет матчить пока не встретится (12|23). После чего будет сматчено (12|23) и дальше будет сожрана вся строка.

Здравствуйте, mefrill, Вы писали:

M>Решил создать новую тему, чтобы сообщение не затерялось в монстрообразных ветках предыдущих обсуждений.
Ты опять о сфероконях в вакууме.
Ибо как только появляются группы вся твоя идилия рушится. А бекреференсы ее совсем убивают.

M>Предположим, у нас имеется регулярное выражени (a|b)c+, построим по нему ДКА:
Как они у тебя страшно отформатированы...
У меня тут есть код для посторения минимальных автоматов из тру-регесксов. Так что я им и воспользуюсь.
Словом start обозначается стартовое состояние (не обязательно нулевое) словом ok обозначено допускающее состояние.

    printFsm(
      FSMBuilder.Seq
        ([FSMBuilder.Choice
            ([FSMBuilder.Symbol('a')
            , FSMBuilder.Symbol('b')
            ])
        , FSMBuilder.RepeatMin(1, FSMBuilder.Symbol('c'))
        ])
    );

0  start
-> 1 ['a'..'b']

1
-> 2 ['c']

2  ok
-> 2 ['c']

M>Смысл такого добавления состоит в том, что при нахождении в каком-то состоянии автомат одновременно начинает считывать строку с начального состояния. В результате может получиться недетерминированный автомат. Построим поисковый автомат для автомата выше:

    printFsm(
      FSMBuilder.Seq
        ([FSMBuilder.RepeatMin(0, FSMBuilder.Symbol(RangeSet().AddRange('\x0000', '\xFFFF')))//превращаем в поисковый
        , FSMBuilder.Choice
            ([FSMBuilder.Symbol('a')
            , FSMBuilder.Symbol('b')
            ])
        , FSMBuilder.RepeatMin(1, FSMBuilder.Symbol('c'))
        ])
    );

0
-> 0 ['a'..'b']
-> 1 ['c']
-> 2 ['\0'..'`', 'd'.. char.MaxValue]

1  ok
-> 0 ['a'..'b']
-> 1 ['c']
-> 2 ['\0'..'`', 'd'.. char.MaxValue]

2  start
-> 0 ['a'..'b']
-> 2 ['\0'..'`', 'c'.. char.MaxValue]

Вот только тут есть одна маленькая проблема о котой ты не упомянул... этот автомат найдет все концы строк.
Далее нам придется искать еще и начала.
Вопрос в том как?
У меня только одна идея: реверснуть все последовательности в регулярном выражении. Построить ДКА по перевернотому регексу. И начиная с каждого конца искать начало этим автоматом.
И тут мы сразу получаем квадратичное время в общем случае.
Если у нас есть группы становится еще веселее.

M>Рассмотрим, например, выражение (ax?){3,10}. Мы должны найти все подстроки от 3 до 10 символов a, необязательно разделенных символом x. При построении поискового автомата состояния вырастут экспоненциально правой границе интервала, в данном случае 10.
А мой код говорит что линейно.
И честно говоря я не понял откуда ты экспоненту вытащил.

    printFsm(
      FSMBuilder.RepeatMinMax(3, 5,
        FSMBuilder.Seq
          ([FSMBuilder.Symbol('a')
          , FSMBuilder.Option(FSMBuilder.Symbol('x'))
          ])
        )
    );

	Скрытый текст
	0 -> 8 ['a'] 1 -> 8 ['a'] -> 0 ['x'] 2 ok -> 4 ['a'] -> 3 ['x'] 3 ok -> 4 ['a'] 4 ok -> 5 ['x'] 5 ok 6 -> 1 ['a'] 7 -> 1 ['a'] -> 6 ['x'] 8 ok -> 2 ['a'] -> 9 ['x'] 9 ok -> 2 ['a'] 10 start -> 7 ['a'] 3 10 0 -> 19 ['a'] 1 -> 19 ['a'] -> 0 ['x'] 2 ok -> 4 ['a'] -> 3 ['x'] 3 ok -> 4 ['a'] 4 ok -> 5 ['x'] 5 ok 6 -> 1 ['a'] 7 -> 1 ['a'] -> 6 ['x'] 8 ok -> 2 ['a'] -> 9 ['x'] 9 ok -> 2 ['a'] 10 start -> 7 ['a'] 11 ok -> 8 ['a'] -> 12 ['x'] 12 ok -> 8 ['a'] 13 ok -> 11 ['a'] -> 14 ['x'] 14 ok -> 11 ['a'] 15 ok -> 13 ['a'] -> 16 ['x'] 16 ok -> 13 ['a'] 17 ok -> 15 ['a'] -> 18 ['x'] 18 ok -> 15 ['a'] 19 ok -> 17 ['a'] -> 20 ['x'] 20 ok -> 17 ['a']

А поисковый автомат вообще веселый получается

    printFsm(
      FSMBuilder.Seq
        ([FSMBuilder.RepeatMin(0, any),
          FSMBuilder.RepeatMinMax(3, 100,
            FSMBuilder.Seq
              ([FSMBuilder.Symbol('a')
              , FSMBuilder.Option(FSMBuilder.Symbol('x'))
              ])
            )
        ])
    );

0
-> 4 ['a']
-> 5 ['\0'..'`', 'b'.. char.MaxValue]

1  ok
-> 4 ['a']
-> 5 ['\0'..'`', 'b'.. char.MaxValue]

2
-> 3 ['a']
-> 5 ['\0'..'`', 'b'.. char.MaxValue]

3
-> 4 ['a']
-> 0 ['x']
-> 5 ['\0'..'`', 'b'..'w', 'y'.. char.MaxValue]

4  ok
-> 4 ['a']
-> 1 ['x']
-> 5 ['\0'..'`', 'b'..'w', 'y'.. char.MaxValue]

5  start
-> 6 ['a']
-> 5 ['\0'..'`', 'b'.. char.MaxValue]

6
-> 3 ['a']
-> 2 ['x']
-> 5 ['\0'..'`', 'b'..'w', 'y'.. char.MaxValue]

6 состояний для любой верхней граници...
Растет линейно относительно нижней граници.

M>Таким образом, кроме вырожденных случаев, легко построить поисковый ДКА, который будет находить все возможные подстроки за минимально возможное время. Как в этом случае с PEG.
Это если забыть про то что нужно еще и начало первой найденной подстроки найти...
Плюс мы в очередной раз выяснили что из людей получаются плохие компиляторы.

M>PS: Ничего не имею против PEG, но считаю, что каждому инструменту -- своя область применения. PEG предназначен для синтаксического анализа, т.е. для построения из текста дерева разбора, но не для поиска.
Пег может и искать и дерево строить.

M>Алгроитм PEG описывает разбор конкретного текста, т.е. то, что называется match, но не поиск.
match это какраз регекс.
С поиском у регексов все какраз грустно.

Привет,

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

Мне интересно, как парсер на основе рекурсивного спуска можно использовать для поиска подстрок в некотором тексте. Для регулярных выражений все очень просто:
1. Создаем по регулярке детерминированный конечный автомат.
2. Превращаем этот автомат в поисковый.
3. Идем по строке скармливаем его автомату. При переходе в допускающее состояние печатаем найденную подстроку.

Первый пункт -- это известное преобразование, корректно ввиду истинности теоремы Клини. Немного о втором пункте и о том, что такое поисковый автомат.

Предположим, у нас имеется регулярное выражени (a|b)c+, построим по нему ДКА:

             a       b     c
--> 0     1      2     --
       1     --     --     3
       2     --     --     3
   *  3     --      --    3

Этот ДКА не поисковый, чтобы найти по нему что-то в тексте abbccacc, надо запускать автомат с каждого символа текста сначала. Это затратная операция, надо поддерживать список состояний для каждого символа теста (до тех пор, пока в автомате есть переходы с этой позиции в тексте). Чтобы этого избежать добавляем в автомат переходы по следующему принципу:

Для каждого состояния q автомата, если из начального состояния имеется переход по символу X в состояние q', добавляем переход по этому символу в состояние q'.

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

             a       b     c
--> 0     1      2     --
       1     1     2     3
       2     1     2     3
   *  3     1     2     3

Данный автомат даже остался детерминирвоанным, хотя добавились дополнительные шесть переходов. Этот автомат позволяет искать в тексте любую подстроку, удовлетворяющую регулярному выражению (a|b)c+. Это легко проверить, я этого делать здесь не буду.

В общем случае, поисковый автомат может стать НКА. Построить из такого НКА ДКА можно стандартным способом, хотя в некоторых случаях в результате может быть довольно много состояний. Рассмотрим, например, выражение (ax?){3,10}. Мы должны найти все подстроки от 3 до 10 символов a, необязательно разделенных символом x. При построении поискового автомата состояния вырастут экспоненциально правой границе интервала, в данном случае 10. Для больших выражений состояний может быть сотни тысяч. Поэтому, в некоторых случаях поисковый автомат построить трудно, можно вести поиск непосредственно по НКА.

Таким образом, кроме вырожденных случаев, легко построить поисковый ДКА, который будет находить все возможные подстроки за минимально возможное время. Как в этом случае с PEG.

PS: Ничего не имею против PEG, но считаю, что каждому инструменту -- своя область применения. PEG предназначен для синтаксического анализа, т.е. для построения из текста дерева разбора, но не для поиска. Регулярные выражения были введены конкретно для поиска и представляют собой удобный инструмент для описания отношения "быть рядом", которое естественно для поисковых шаблонов. Грамматика PEG -- косвенное описание отношения иерархии, через спецификацию алгоритма разбора, которую на самом деле представляет собой грамматика PEG. Алгроитм PEG описывает разбор конкретного текста, т.е. то, что называется match, но не поиск. Поэтому использовать его вместо РВ для поиска не хорошо. Использовать PEG для match по регуляркам мне кажется также не очень хорошо. В алгоритм PEG неявно встроено отношение иерархии, т.е. "быть частью". Пользователь же в абсолютном большинстве случаев использует отношение "быть рядом", которое выражается РВ очень удобно. Таким образом, здесь мы имеем нарушение принципа "не плоди сущности без нужды", заставляя пользователя использовать инструмент, семантика которого намного богаче того, что необходимо пользователю.

С уважением,
ВЛ.

что такое "задача поиска"? сценарии, используемые инструменты?

Здравствуйте, WolfHound, Вы писали:

WH>Здравствуйте, mefrill, Вы писали:

M>>Решил создать новую тему, чтобы сообщение не затерялось в монстрообразных ветках предыдущих обсуждений.
WH>Ты опять о сфероконях в вакууме.
WH>Ибо как только появляются группы вся твоя идилия рушится. А бекреференсы ее совсем убивают.

Снова про бэкреференсы. Я же сказал, что рассматриваю нормальные регулярные выражения, без перловых расширений. Это вполне реальный синтаксис, который используется в Яндексе, Гугле и даже, не побоюсь этого слова, в компании ИнфоВотч, в которой я сейчас работаю. Для выделения групп достаточно атрибутов состояний, при переходе в которые запоминаются позиции начала и конца групы в тексте. Если мы разрешаем неоднозначность выделения группы жадным алгоритмом, что делается в абсолютном большинстве реализаций, то никаких проблем нет, поиск линейный.

M>>Смысл такого добавления состоит в том, что при нахождении в каком-то состоянии автомат одновременно начинает считывать строку с начального состояния. В результате может получиться недетерминированный автомат. Построим поисковый автомат для автомата выше:
WH>

WH>    printFsm(
WH>      FSMBuilder.Seq
WH>        ([FSMBuilder.RepeatMin(0, FSMBuilder.Symbol(RangeSet().AddRange('\x0000', '\xFFFF')))//превращаем в поисковый
WH>        , FSMBuilder.Choice
WH>            ([FSMBuilder.Symbol('a')
WH>            , FSMBuilder.Symbol('b')
WH>            ])
WH>        , FSMBuilder.RepeatMin(1, FSMBuilder.Symbol('c'))
WH>        ])
WH>    );
WH>

0
-> 0 ['a'..'b']
-> 1 ['c']
-> 2 ['\0'..'`', 'd'.. char.MaxValue]

1  ok
-> 0 ['a'..'b']
-> 1 ['c']
-> 2 ['\0'..'`', 'd'.. char.MaxValue]

2  start
-> 0 ['a'..'b']
-> 2 ['\0'..'`', 'c'.. char.MaxValue]

Зачем переходы по ['\0'..'`', 'd'.. char.MaxValue]? Достаточно возвращать номер начального состояния, если из текущего нет переходов. При поиске достаточно запоминать позицию последнего допускающего состояния и позицию последнего начального, это и будет выделенный текст. То же самое можно делать для выделения групп.

M>>Рассмотрим, например, выражение (ax?){3,10}. Мы должны найти все подстроки от 3 до 10 символов a, необязательно разделенных символом x. При построении поискового автомата состояния вырастут экспоненциально правой границе интервала, в данном случае 10.
WH>А мой код говорит что линейно.

Хреновый какой-то автомат, с багами. Например, у тебя состояния 2 и 9 допускающие, хотя в девятое состояние автомат приходит прочитав строку ax, а во второе -- по строкам aa или axa. Дальше смотреть даже не стал.

WH>А поисковый автомат вообще веселый получается
WH>6 состояний для любой верхней граници...
WH>Растет линейно относительно нижней граници.

Он левый совершенно. Ты сам подумай, надо выделить последовательность из 10 символов "a", как это можно сделать с шестью состояниями? У тебя баги там в коде, надо проверять, прежде, чем постить.

M>>Таким образом, кроме вырожденных случаев, легко построить поисковый ДКА, который будет находить все возможные подстроки за минимально возможное время. Как в этом случае с PEG.
WH>Это если забыть про то что нужно еще и начало первой найденной подстроки найти...

В чем проблема? Алгоритм поиска жадный как вправо, так и влево. Иначе никакого смысла в поиске вообще нет.

WH>Плюс мы в очередной раз выяснили что из людей получаются плохие компиляторы.

Мне кажется, мы пока выяснили, что чаще плохие компиляторы получаются из машин.

M>>PS: Ничего не имею против PEG, но считаю, что каждому инструменту -- своя область применения. PEG предназначен для синтаксического анализа, т.е. для построения из текста дерева разбора, но не для поиска.
WH>Пег может и искать и дерево строить.

Если для поиска он строит конечный автомат, то в чем разница?!

M>>Алгроитм PEG описывает разбор конкретного текста, т.е. то, что называется match, но не поиск.
WH>match это какраз регекс.
WH>С поиском у регексов все какраз грустно.

Грустно только при недостатке знаний. Надо бы поглядеть на реализации от Яндекса и Гугла, там не дураки работают. Код открыт, разбирайся и реализовывай.

Здравствуйте, mefrill, Вы писали:

M>Снова про бэкреференсы. Я же сказал, что рассматриваю нормальные регулярные выражения, без перловых расширений.
А во всех соседних топиках говорят про перловые.

M>Это вполне реальный синтаксис, который используется в Яндексе, Гугле и даже, не побоюсь этого слова, в компании ИнфоВотч, в которой я сейчас работаю. Для выделения групп достаточно атрибутов состояний, при переходе в которые запоминаются позиции начала и конца групы в тексте. Если мы разрешаем неоднозначность выделения группы жадным алгоритмом, что делается в абсолютном большинстве реализаций, то никаких проблем нет, поиск линейный.
Расскажи пожалуйста как ты это делаешь.

M>Зачем переходы по ['\0'..'`', 'd'.. char.MaxValue]?
За тем что это делала машина.

M>Достаточно возвращать номер начального состояния, если из текущего нет переходов.
Так этот переход именно это и делает.

M>При поиске достаточно запоминать позицию последнего допускающего состояния и позицию последнего начального, это и будет выделенный текст. То же самое можно делать для выделения групп.
Чего?
Мы вроде как применяем автомат к каждому символу.
Так что эти позиции равны.
А вот как найти последнюю стартувую позицию которая матчит текст это вопрос.
Более того люди обычно хотят не последнюю кратчайшую, а первую длиннейшую.

M>Хреновый какой-то автомат, с багами. Например, у тебя состояния 2 и 9 допускающие, хотя в девятое состояние автомат приходит прочитав строку ax, а во второе -- по строкам aa или axa. Дальше смотреть даже не стал.
Это не автомат хреновый.
Это ты не читаешь что тебе пишут.

Словом start обозначается стартовое состояние (не обязательно нулевое) словом ok обозначено допускающее состояние.

Теперь надеюсь ты это прочитаешь посмотришь что там происходит. Но начнешь не с нулевого, а в данном случае 10ого.

M>Он левый совершенно. Ты сам подумай, надо выделить последовательность из 10 символов "a", как это можно сделать с шестью состояниями? У тебя баги там в коде, надо проверять, прежде, чем постить.
Там все правильно.
Он ищет ax? которое повторяется от 3х до 100раз.
На строке из 100 ax будет 98 срабатываний.

В данном случае у нас ограничитель минимум. Ибо два ax мы сматчить не должны.
И для этого нужно именно что 6 состояний.

Повторяю еще раз: Из людей хреновые компиляторы.

M>В чем проблема? Алгоритм поиска жадный как вправо, так и влево. Иначе никакого смысла в поиске вообще нет.
Я в принципе придумал.
Строим перевернутый регекс и начиная с конци поисковым регексом находим начало первой подстроки.
Потом прямым регексом находим конец первой подстроки.

M>Мне кажется, мы пока выяснили, что чаще плохие компиляторы получаются из машин.
Мы вяснили что ты не читаешь то что тебе пишут.

M>Если для поиска он строит конечный автомат, то в чем разница?!
В семантеке.
Построить автоматы для регулярных частей ПЕГа это вообще говоря задачка не простая именно из за различной семантики.
Ибо в регексах операторы повторения жадные и уступчивые, а в ПЕГе жадные и не уступчивые. Плюс выбор детерминированный.
Короче веселья там много.

M>Грустно только при недостатке знаний. Надо бы поглядеть на реализации от Яндекса и Гугла, там не дураки работают. Код открыт, разбирайся и реализовывай.
Ну проходом задом на перед можно найти все начала подстрок и потом с каждого начала нужно запускать прямой проход для того чтобы найти конец.
В общем случае сложность квадратичная. Ибо подстрока может начинаться в каждой позиции и длиться до конца строки. Хотя на практике все будет конечно не так печально.

Здравствуйте, WolfHound, Вы писали:

M>>Это вполне реальный синтаксис, который используется в Яндексе, Гугле и даже, не побоюсь этого слова, в компании ИнфоВотч, в которой я сейчас работаю. Для выделения групп достаточно атрибутов состояний, при переходе в которые запоминаются позиции начала и конца групы в тексте. Если мы разрешаем неоднозначность выделения группы жадным алгоритмом, что делается в абсолютном большинстве реализаций, то никаких проблем нет, поиск линейный.
WH>Расскажи пожалуйста как ты это делаешь.

Выделяем в автомате состояния, который обозначают начало группы в регулярке. Запоминаем их как атрибуты состояний, которые потом наследуем при всех слияниях и минимизациях. При поиске, когда первый раз входим в состояние с таким атрибутом, запоминаем позицию символа в тексте, когда доходим до состояния, которое выходит из группы, запоминаем позицию в группе. Когда нет переходов или длина допустимого выделяемого текста превышена, то печатаем тексты групп и сбрасываем все позиции для них. Тот же подход и для всего выражения. Только входом в группу служит начальное состояние, а выходом -- каждое допускающее.

M>>Зачем переходы по ['\0'..'`', 'd'.. char.MaxValue]?
WH>За тем что это делала машина.

Ну машину же кто-то запрограммировал? Можно запрограммировать и другое. Реализация переходов по дополнению алфавита очень затратна, даже если используется интервал. Самая простая реализация -- это массив номеров состояний, индексированный символами и заполненный номером начального состояния там, где нет перехода. Для конкретной регулярки алфавит обычно небольшой, запрограммировать проверку диапазона и переход по символу, попадающему в этот диапазон, совсем просто. Для таких переходов как у тебя, таблицей не запрограммируешь.

M>>При поиске достаточно запоминать позицию последнего допускающего состояния и позицию последнего начального, это и будет выделенный текст. То же самое можно делать для выделения групп.
WH>Чего?
WH>Мы вроде как применяем автомат к каждому символу.
WH>Так что эти позиции равны.
WH>А вот как найти последнюю стартувую позицию которая матчит текст это вопрос.
WH>Более того люди обычно хотят не последнюю кратчайшую, а первую длиннейшую.

Мы видимо на разных языках говорим. Ты о чем? Имеем поисковый автомат, каждый раз, когда переходим в начальное состояние, запоминаем позицию символа в строке. Каждый раз, когда переходим в допускающее, запоминаем позицию символа в строке, затирая предыдущую. Когда нет переходов, вытаскиваем эти позиции, -- это текст, выделенный жадным алгоритмом, после чего сбрасываем позицию для допускающих состояний, и запоминаем новую позицию начала.


M>>Он левый совершенно. Ты сам подумай, надо выделить последовательность из 10 символов "a", как это можно сделать с шестью состояниями? У тебя баги там в коде, надо проверять, прежде, чем постить.
WH>Там все правильно.
WH>Он ищет ax? которое повторяется от 3х до 100раз.
WH>На строке из 100 ax будет 98 срабатываний.

Ужас какой. Нормальный поисковый автомат должен выделить одну строку, т.е. заматчить всю строку. Реализация некорректна, т.к. только часть языка, описываемого данной регуляркой, находится.

WH>В данном случае у нас ограничитель минимум. Ибо два ax мы сматчить не должны.
WH>И для этого нужно именно что 6 состояний.

Это плохая реализация, надо находить наидлиннейшую подходящую строку. Иначе вообще непонятно, как я могу найти номер телефона ([0-9]\-?){3,8}. Вместо номера мне будет выдавать его куски.

M>>Если для поиска он строит конечный автомат, то в чем разница?!
WH>В семантеке.
WH>Построить автоматы для регулярных частей ПЕГа это вообще говоря задачка не простая именно из за различной семантики.
WH>Ибо в регексах операторы повторения жадные и уступчивые, а в ПЕГе жадные и не уступчивые. Плюс выбор детерминированный.
WH>Короче веселья там много.

Ну тогда тем более непонятно о чем спор. ПЕГ для парсинга (матчинга), регулярки для поиска.

M>>Грустно только при недостатке знаний. Надо бы поглядеть на реализации от Яндекса и Гугла, там не дураки работают. Код открыт, разбирайся и реализовывай.
WH>Ну проходом задом на перед можно найти все начала подстрок и потом с каждого начала нужно запускать прямой проход для того чтобы найти конец.
WH>В общем случае сложность квадратичная. Ибо подстрока может начинаться в каждой позиции и длиться до конца строки. Хотя на практике все будет конечно не так печально.

Не понимаю про проходы.

имо, у вас разные автоматы.
у mefril-а — автомат который запоминает стартовую позицию искомой строки, а у WH — который это не делает.
отсюда и все разночтения.

Здравствуйте, mefrill, Вы писали:

M>Выделяем в автомате состояния, который обозначают начало группы в регулярке. Запоминаем их как атрибуты состояний, которые потом наследуем при всех слияниях и минимизациях. При поиске, когда первый раз входим в состояние с таким атрибутом, запоминаем позицию символа в тексте, когда доходим до состояния, которое выходит из группы, запоминаем позицию в группе. Когда нет переходов или длина допустимого выделяемого текста превышена, то печатаем тексты групп и сбрасываем все позиции для них. Тот же подход и для всего выражения. Только входом в группу служит начальное состояние, а выходом -- каждое допускающее.
Вот тебе текст и 3 регекса. Объясни что и почему сматчит твой алгоритм.
0012300
Тут все понятно.
0*(12|23).*
Тут тоже ясно что должно быть найдено. Но не ясно как это сработает согласно твоему алгоритму.
.*(12|23)0*
Тут вообще не однозначность. Какой вариант и почему найдет твой алгоритм?
.*(12|23).*

M>Ну машину же кто-то запрограммировал? Можно запрограммировать и другое.
Ты опять путаешь теплое с мягким.
Это чисто трансформатор. Кодогенератор отдельно и там все весьма не плохо оптимизируется.
Таблици мне не подходят ибо юникод.
А будет еще лучше. Просто у меня руки пока не дошли.

M>Ужас какой. Нормальный поисковый автомат должен выделить одну строку, т.е. заматчить всю строку. Реализация некорректна, т.к. только часть языка, описываемого данной регуляркой, находится.
Нет. Корректна.
Ибо пока автомат бежит по строке он 98 раз попадет в допускающее состяние.
В любом случае.

M>Это плохая реализация, надо находить наидлиннейшую подходящую строку.
Это N^2.
Как ни крутись.
Нам надо будет с каждого конечного состояния запустить обратный регекс. Только так можно найти длиннейшую последовательность.

M>Ну тогда тем более непонятно о чем спор. ПЕГ для парсинга (матчинга), регулярки для поиска.
А чем группы не матчинг? А поиск сводится к .*(any regex).*

M>Не понимаю про проходы.
У нас есть регекс 12|23 обратный регекс у нас получается вот таким 21|32. Его можно искать сканируя нашу строку задом на перед.
Допускающие состояния обратного регекса будут совпадать со стартовымми состояниями прямого регекса.
Пройдя задом на перед мы получим все позиции в которых может начинаться наш регекс.
Далее в каждой начальной позиции мы запускаем прямой регекс и получаем для каждой начальной позиции одну или несколько конечных позиций.
Это будет полное множество подстрок которые можно сматчить нашим регексом.
Если не хочешь все то можно для каждой стартовой позиции брать только самую длинную подстроку.

Здравствуйте, mefrill, Вы писали:

M>Привет,

M>Решил создать новую тему, чтобы сообщение не затерялось в монстрообразных ветках предыдущих обсуждений.

M>Мне интересно, как парсер на основе рекурсивного спуска можно использовать для поиска подстрок в некотором тексте. Для регулярных выражений все очень просто:
M> 1. Создаем по регулярке детерминированный конечный автомат.
M> 2. Превращаем этот автомат в поисковый.
M> 3. Идем по строке скармливаем его автомату. При переходе в допускающее состояние печатаем найденную подстроку.

Может быть будет полезно для дискуссий

Поиск сабматчей за линейное относительно длины строки время через НКА:
http://swtch.com/~rsc/regexp/regexp2.html

Оптимизация для солидного класса частных случаев: (искать фразу Use a one-pass NFA if possible)
http://swtch.com/~rsc/regexp/regexp3.html

WH>Тут вообще не однозначность. Какой вариант и почему найдет твой алгоритм?
WH>.*(12|23).*


Я тут ковыряю PEG потихоньку. И как раз почти в связи с похожим возник вопрос: а как такое записывается в PEG'е?

То есть

rule <- .* (12|23) .*

вроде ведь тоже неоднозначно вроде?