есть ли функция C для регулярного выражения с использованием детерминированного автомата?

1. да. 2. Это вопрос простой алгебры. 3. Здесь

https://github.com/RockBrentwood/RegEx

(первоначально в архиве comp.compilers.)

Вот раннее описание comp.compilers, от которого это в конечном итоге произошло.

https://compilers.iecc.com/comparch/article/93-05- 083

https://compilers.iecc.com/comparch/article/93-10- 022

https://www.cs.cmu.edu/afs/cs/project/ai-repository/ai/areas/nlp/parsing/regex

Я попытаюсь ретконить поток эволюции 1993–2021 годов в текущий моментальный снимок GitHub, чтобы у вас была вся история, а не только моментальный снимок последних версий. (Кстати, было бы неплохо, если бы GitHub поддерживал ретконнинг и модификацию потоков истории.)

Автомат — это не более чем графическое изображение конечной линейной справа системы неравенств. Каждое рациональное выражение является решением такой системы с наименьшими фиксированными точками, которое может быть развернуто из выражения чисто алгебраическими средствами.

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

Я пытаюсь адаптировать расчет в {nfa,dfa}.c для обработки как входных, так и выходных данных. Есть несколько мест, где делается конкретное предположение, что алгебра Клини является свободной алгеброй Клини (= алгебра регулярных выражений). И это должно быть изменено, чтобы его можно было обобщить на несвободные алгебры Клини, такие как рациональные преобразования.

Регулярные выражения над алфавитом $X$ составляют алгебру Клини $ℜX^*$ рациональных подмножеств свободного моноида $X^*$, порожденного $X$. Соответственно, $ℜX^*$ — это свободная алгебра Клини, порожденная $X$.

Лежащая в основе теория (в отношении которой имеется в виду свобода) может быть 1-го или 2-го порядка.

Теория 1-го порядка (несмотря на результат Конвея об отсутствии конечной аксиоматизации, неверно сформулированный и неправильно примененный как теорема из фольклора) представляет собой конечно аксиоматизированную алгебру, состоящую из (а) аксиом для полукольца с идемпотентной суммой $x + x = x$ (обычно обозначается $x | x$) ... т.е. диоид, и (b) соответствующее отношение частичного порядка, определяемое как ($x ≥ y ⇔ (∃z) x = z + y ⇔ x = x + y $); (c) оператор звездочки Клини $x ↦ x^*$, который (d) дает решения наименьшей фиксированной точки $b^* ac^* = µx (x ≥ a + bx + xc)$ . (Набор аксиом, воплощающих (d), состоит в следующем: $x^* = 1 + xx^*$ и $x ≥ a + bx + xc ⇒ x ≥ b^* ac^*$.) Это датируется серединой 1990-х гг. Козен.

Алгебра, представляемая теорией 1-го порядка, не замкнута относительно соотношений конгруэнтности (поскольку фактически все вычисления могут быть представлены алгеброй Клини, взятой над подходящим образом определенным нетривиальным моноидом; таким образом, проблема слов тоже не разрешима). Формулировка 2-го порядка, которая предшествует формулировке 1-го порядка, представляет собой замыкание формулировки 1-го порядка по конгруэнтности. Он имеет (а) аксиомы диоида и (б) наименьшие неподвижные точки всех рациональных подмножеств и (в) дистрибутивность по отношению к рациональной наименьшей неподвижной точке. Последние две аксиомы можно сузить и объединить в одну аксиому для наименьшей неподвижной точки: $µ_{n≥0}(ab^nc) = ab^*c$.

Используя терминологию LNCS 4988 (https://link.springer.com/chapter/10.1007%2F978-3-540-78913-0_14), сюда входит категория рациональных диоидов = рационально замкнутых идемпотентных полуколец. У него есть тензорный продукт ⊗, который был частью набора дополнительной инфраструктуры и расширенной терминологии, изложенных в LNCS11194 (стр. 21-36, 37-52) https://dblp.org/db/conf/RelMiCS/ramics2018.html.

Программное обеспечение требует и использует только формулировку 1-го порядка.

Аналогично, рациональные преобразования над входным алфавитом $X$ и выходным алфавитом $Y$ содержат рациональные подмножества $ℜ(X^* × Y^*)$ моноида произведения $X^* × Y^*$; а в категории рациональных диоидов алгебра рационального преобразования представляет собой тензорное произведение $ℜ(X^* × Y^*) = ℜX^* ⊗ ℜY^*$ соответствующих алгебр регулярных выражений.

В свою очередь, эта алгебра фактически является просто алгеброй регулярных выражений над несвязным объединением $X$ и $Y$ по модулю правила коммутативности $xy = yx$ для $x ∈ X, y ∈ Y$, так что процесс может быть адаптировано и обобщенно адаптировано к:

(a) преобразователи - где присутствуют и X, и Y,

б) генераторы, где присутствует только $Y$ и $X = {1}$,

в) распознаватели, где присутствует только $X$ и $Y = {1}$ и даже

(d) их обобщения, где разрешено несколько входных и/или выходных каналов.

Пример: алгебра Клини $ℜX_0^* ⊗ ℜX_1^* ⊗ ℜY_0^* ⊗ ℜY_1^*$ будет для преобразователей с двумя входными каналами (один с алфавитом $X_0$, другой с алфавитом $X_1$) и двумя выходными каналами ( с соответствующими алфавитами $Y_0$ и $Y_1$).