видел в драконьей книге как недетерминированный КА превращают в детерминированный
а что делать если есть квантификация?
если недетерминированный интерпретировать то всё понятно — или самое короткое или самое длинное вхождение
а как быть с этим преобразованием? или он с квантификацией не дружит?
Здравствуйте, VjcheslavV, Вы писали:
VV>видел в драконьей книге как недетерминированный КА превращают в детерминированный VV>а что делать если есть квантификация?
Я тоже читал драконью книгу, и даже представляю, как недетерминированный КА превращают в детерминированный (ну т.е., пробовал такое делать в боевой программе).
Однако слово квантификация мне ничего не говорит. Может, введешь в курс дела?
если просто преобразовывать в лоб то в состояниях будет и ревнивая и жадная квантифакация...
вот только что потом с ней делать? или что-то делать до преобразования?
А, понятно. Обрати внимание, у тебя содержательно есть только один "интересный" символ, это бесконечный повтор. Остальные разворачиваются так (e — это epsilon, примитив регулярного выражения, всегда сопоставляющийся с пустой строкой):
X? -> X | e
X+ -> X X*
X{n} -> X X X ... X
X{m,n} -> X X X ... X (X | e) (X | e) ... (X | e)
Т.е., все эти красивые штучки — это синтаксический сахар в общепринятой записи регулярных выражений. Содержательно, у тебя есть только три операции: конкатенация, альтернация и бесконечный повтор.
При преобразовании в детерминированный КА эти красивые штучки не порождают прохода по одним и тем же символам в разных состояниях, а порождают сложный автомат в виде развесистой клюквы, в котором повторяющиеся фрагменты регулярного выражения порождают повторяющиеся фрагменты в графе состояний.
Ну и учти еще, что POSIX regexp, из-за возможности ссылаться на уже насканированное, не является регулярным языком по Хомскому, и обычно реализуется в виде автомата с возвратами и стеком состояний.
VV>видел в драконьей книге как недетерминированный КА превращают в детерминированный VV>а что делать если есть квантификация? VV>если недетерминированный интерпретировать то всё понятно — или самое короткое или самое длинное вхождение VV>а как быть с этим преобразованием? или он с квантификацией не дружит?
Любая конечная или бесконечная итерация выражается через либо конечное объединение, либо через звезду Клини.
Их можно преобразовать в ε-НКА (3.2.3. Преобразование регулярного выражения в автомат в «Введение в теорию автоматов, языков и вычислений»)
Любой ε-НКА же, как утверждается в той же книге (2.5.5. Устранение ε-переходов), преобразуется в ДКА.
Здравствуйте, σ, Вы писали:
σ>Любая конечная или бесконечная итерация выражается через либо конечное объединение, либо через звезду Клини. σ>Их можно преобразовать в ε-НКА (3.2.3. Преобразование регулярного выражения в автомат в «Введение в теорию автоматов, языков и вычислений») σ>Любой ε-НКА же, как утверждается в той же книге (2.5.5. Устранение ε-переходов), преобразуется в ДКА.
глянул как-то не на наглядном примере объяснено ...
там повторяются только цифры а после них идёт точка или конец (то есть квантификация не где, ни на что не повлияет)
как я понял чтобы построить детерминированный автомат всегда строят эквивалентный не детерминированный?
вот был бы пример с квантификацией ...
Здравствуйте, Pzz, Вы писали:
Pzz>Причем, что характерно, если не полениться сделать минимализацию, то всегда одним и тем же образом, с точностью то поворотов в графе.
Здравствуйте, VjcheslavV, Вы писали:
Pzz>>Причем, что характерно, если не полениться сделать минимализацию, то всегда одним и тем же образом, с точностью то поворотов в графе.
VV>а причём тут оптимизация?
Не оптимизация, а минимализация машины состояний. Один и тот же регулярный язык может быть представлен разными конечными автоматами. Но при этом минимальный автомат однозначно определяется языком.
Здравствуйте, VjcheslavV, Вы писали:
VV>весь интернет прогуглил но про квантификацию ничего не нашёл... VV>как её всё таки делают в регулярных выражениях? ума не приложу...
В чём проблема-то? Что именно тебе не понятно? Pzz вроде всё доступно изложил.
Здравствуйте, Pzz, Вы писали:
Pzz>Ну и учти еще, что POSIX regexp, из-за возможности ссылаться на уже насканированное, не является регулярным языком по Хомскому, и обычно реализуется в виде автомата с возвратами и стеком состояний.
Насколько я помню, с регвырами несложно построить выражение, которое при реализации через КА построит КА то ли экспоненциального то ли около того размера. В общем большой КА получится. Получается, что НКА в худшем случае долго работает, а КА в худшем случае требует очень много памяти. Ну и НКА более богатый и на практике с вырожденными случаями сталкиваться приходится редко. Поэтому НКА и используют для реализации, хотя есть и реализации на КА, если действительно важна O(N) производительность.
VV>весь интернет прогуглил но про квантификацию ничего не нашёл... VV>как её всё таки делают в регулярных выражениях? ума не приложу... https://swtch.com/~rsc/regexp/
vsb>В чём проблема-то? Что именно тебе не понятно? Pzz вроде всё доступно изложил.
действительно я ничего не понял ...
я понял что якобы это не по теме — там вроде не было как задаются жадная или ленивая квантификация...
Pzz>X? -> X | e
Pzz>X+ -> X X*
Pzz>X{n} -> X X X ... X
Pzz>X{m,n} -> X X X ... X (X | e) (X | e) ... (X | e)
Pzz>
Pzz>Т.е., все эти красивые штучки — это синтаксический сахар в общепринятой записи регулярных выражений. Содержательно, у тебя есть только три операции: конкатенация, альтернация и бесконечный повтор.
Здравствуйте, VjcheslavV, Вы писали:
vsb>>В чём проблема-то? Что именно тебе не понятно? Pzz вроде всё доступно изложил. VV>действительно я ничего не понял ... VV>я понял что якобы это не по теме — там вроде не было как задаются жадная или ленивая квантификация...
Ну сразу бы и написал, что тебе нужна эта жадность или ленивость. В классических алгоритмах такого понятия нет. Там или есть совпадение, или нет. Для этого нужны более продвинутые алгоритмы, можешь попробовать почитать труд "NFAs with Tagged Transitions, their Conversion to Deterministic Automata and Application to Regular Expressions".
Здравствуйте, vsb, Вы писали:
vsb>Ну сразу бы и написал, что тебе нужна эта жадность или ленивость. В классических алгоритмах такого понятия нет. Там или есть совпадение, или нет. Для этого нужны более продвинутые алгоритмы, можешь попробовать почитать труд "NFAs with Tagged Transitions, their Conversion to Deterministic Automata and Application to Regular Expressions".
продвинутые алгоритмы???
я офигиваю ... а на русском чтонибудь есть?
а эти алгоритмы с детерминированным KA или только с недетерминированным?
Здравствуйте, VjcheslavV, Вы писали:
vsb>>Ну сразу бы и написал, что тебе нужна эта жадность или ленивость. В классических алгоритмах такого понятия нет. Там или есть совпадение, или нет. Для этого нужны более продвинутые алгоритмы, можешь попробовать почитать труд "NFAs with Tagged Transitions, their Conversion to Deterministic Automata and Application to Regular Expressions".
VV>продвинутые алгоритмы??? VV>я офигиваю ... а на русском чтонибудь есть?
Сомневаюсь, на русском вообще мало что есть кроме совсем уж классических трудов, а уж малоизвестные исследования — тем более, кому надо их переводить.
VV>а эти алгоритмы с детерминированным KA или только с недетерминированным?
Deterministic Automata это и есть детерминированный автомат. Так что да — с детерминированным.
Pzz>>X? -> X | e
Pzz>>X+ -> X X*
Pzz>>X{n} -> X X X ... X
Pzz>>X{m,n} -> X X X ... X (X | e) (X | e) ... (X | e)
Pzz>>
VV>а можно для "X{n}?" и для "X{n}+" ?
Любое выражение вида X{n} преобразуется в XXX...XX. То бишь такой синтаксис в контексте данных алгоритмов специально обрабатывать не нужно. Перед обработкой выражения проводится его упрощение, оно преобразовывается в максимально простую форму перед созданием НКА и ДКА.
Выражение Y+ преобразовывается в YY*. Соответственно X{N}+ преобразовывается в X{N}X{N}*, а далее (например если n = 5) в XXXXX(XXXXX)*
VV>e вроде просто убирается — какой с неё толк?
Здравствуйте, vsb, Вы писали:
vsb>Сомневаюсь, на русском вообще мало что есть кроме совсем уж классических трудов, а уж малоизвестные исследования — тем более, кому надо их переводить.
во всех регулярных выражениях используется и малоизвестное ... как так?
vsb>Deterministic Automata это и есть детерминированный автомат. Так что да — с детерминированным.
как я понял эта статья научная ? а ссылкой не поделитесь ?
Здравствуйте, VjcheslavV, Вы писали:
vsb>>Сомневаюсь, на русском вообще мало что есть кроме совсем уж классических трудов, а уж малоизвестные исследования — тем более, кому надо их переводить.
VV>во всех регулярных выражениях используется и малоизвестное ... как так?
ДКА в регулярных выражениях на практике используются очень редко. Обычно используются НКА и алгоритм с обратным отслеживанием (backtracking).
vsb>>Deterministic Automata это и есть детерминированный автомат. Так что да — с детерминированным.
VV>как я понял эта статья научная ? а ссылкой не поделитесь ?
Здравствуйте, vsb, Вы писали:
vsb>ДКА в регулярных выражениях на практике используются очень редко. Обычно используются НКА и алгоритм с обратным отслеживанием (backtracking).
а в лексерах? где-то читал что lex/flex детерминированные конечные автоматы
алгоритм с обратным отслеживанием — никогда о нём не слышал — он тоже только на английском?
Здравствуйте, VjcheslavV, Вы писали:
vsb>>ДКА в регулярных выражениях на практике используются очень редко. Обычно используются НКА и алгоритм с обратным отслеживанием (backtracking).
VV>а в лексерах? где-то читал что lex/flex детерминированные конечные автоматы
Тут точно не знаю. Вообще на практике это всё зачастую пишут руками как придётся, а не генерируют. Ну лексеры наверное таки строят DFA, тут в этом есть смысл.
Здравствуйте, VjcheslavV, Вы писали:
vsb>>ДКА в регулярных выражениях на практике используются очень редко. Обычно используются НКА и алгоритм с обратным отслеживанием (backtracking).
VV>а в лексерах? где-то читал что lex/flex детерминированные конечные автоматы
VV>алгоритм с обратным отслеживанием — никогда о нём не слышал — он тоже только на английском?
Да вряд ли. Наверное корректней его называть алгоритм поиска с возвратом. Просто проверяешь первый вариант, если он не подходит — возвращаешься и проверяешь второй вариант и тд, пока не получится найти совпадение (или не найти). Ничего особого.
Здравствуйте, VjcheslavV, Вы писали:
VV>а в лексерах? где-то читал что lex/flex детерминированные конечные автоматы
В лексерах набор квантификаторов ограничен теми, которые разобрал Pzz (man lex/info flex). В них нет квантификаторов жадности/ленивости. Поэтому их и можно разбирать теми алгоритмами, которые описаны в учебниках по построению компиляторов. В библиотеках общего назначения регулярные выражения более богатые но и разбираются по-другому.
Здравствуйте, vsb, Вы писали:
vsb>Здравствуйте, VjcheslavV, Вы писали:
vsb>Тут точно не знаю. Вообще на практике это всё зачастую пишут руками как придётся, а не генерируют. Ну лексеры наверное таки строят DFA, тут в этом есть смысл.
а DFA они сразу строят или через недетерминированный автомат?
в алгоритме Томсана неудобно то что он под конец может возвратить несколько состояний
Не знаите как с этим боротся? темболее не угодаешь когда его завершить...
Здравствуйте, VjcheslavV, Вы писали:
VV>а DFA они сразу строят или через недетерминированный автомат?
Все зависит от точки зрения. Не факт, что там будет явно модель "недетерминированного автомата". Но, с другой стороны, сама по себе исходная грамматика эквивалентна недетерминированному автомату. Так что в реализации будет что-то очень похожее на алгоритм Томсона. Плюс дополнительные специфические вещи. Например, lex/flex поддерживают "состояния разбора", в которых применяются разные наборы правил. Самый простой пример — разбор символов внутри строки. В результате получается композиция из нескольких недетерминированных автоматов и каждый детерминируется отдельно.
VV>в алгоритме Томсана неудобно то что он под конец может возвратить несколько состояний
Это не проблема алгоритма, это проблема исходной грамматики. Ввод, приводящий в такое состояние, является валидным префиксом или выводом (зависит от того, промежуточные или конечные состояния НКА входят в состояние ДКА) сразу нескольких правил исходной грамматики. Более того, по получившемуся ДКА можно строить примеры ввода, которые будут соответсвовать сразу нескольким правилам исходной грамматики.
VV>Не знаите как с этим боротся? темболее не угодаешь когда его завершить...
Так в интернете все есть (5-я глава на странице). Если в ДКА-правиле только промежуточные состояния исходного НКА, вообще ничего делать не надо. Если в ДКА только конечные состояния, "первое" из НКА-состояний (входящих в текущее состояние ДКА) объявляется результатом разбора. Первое — это первое по тексту определения для lex. Такое поведение используется для ключевых слов, которые также обычно попадают под правила для идентификаторов. Самый интересный случай, когда в ДКА-состояние входят как конечные так и промежуточные состояния НКА. В этом случае текущая позиция и состояние отмечаются, как "возможный вывод" и разбор продолжается дальше. Когда дальше двигаться нельзя, берется последний "возможный вывод" (т.е. самую длинную последовательность ввода, подходящую под какое-либо правило), объявляется результатом. Текущая позиция разбора тоже возвращается назад, туда, где было встречено правило. В теории, это может приводить к квадратичной сложности разбора. Например, если есть правила shortId := [abc], longId := [a].*[b] (т.е. короткий идентификатор — символ, длиннй — несколько символов, где первый a и последний b). В этом случае разбор последовательности aaa...aaaa должен проийти ее всю (вдруг там b встретится?) и потом трактовать первый символ как shortId. В принципе, это можно оптимизировать до O(len*states) где len — длина ввода, states — количество состояний автомата. Но на практике так вряд ли кто-то делает. Для типичной грамматики возвраты скорее всего будут не нужны. А если и нужны, то очень короткие (вообще ограниченные константой).
Здравствуйте, VjcheslavV, Вы писали:
VV>видел в драконьей книге как недетерминированный КА превращают в детерминированный VV>а что делать если есть квантификация? VV>если недетерминированный интерпретировать то всё понятно — или самое короткое или самое длинное вхождение VV>а как быть с этим преобразованием? или он с квантификацией не дружит?
А в чем трудность? Квантификаторы с конечными пределами R{k.l} это просто последовательная склейка автомата для R l раз. При это, начиная с k-го автомата все допускающие состояния автомата для R объявляем допускающими в новом автомате. Ну, или если используем эпсилон-автоматы, добавляем эпсилон-переходы в допускающее состояние. Для выражения типа R{,l} все то же самое, только допускающими объявляем все конечные состояния автомата для R. Для выражения R{k,} склеиваем автомат для R k раз, объявляем допускающими последние допускающие состояния автомата для R и добавляем циклический переход для в начальные состояния последнего автомата для R. Например,
a{2,3}
a: 0 -- a -> (1)
aa: 0 -- a -> 1 -- a -> (2)
aa|aaa: 0 -- a -> 1 -- a -> (2) -- a -> (3)
