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)
