Производная регулярных выражений DFA: это должно работать, но неожиданно ломается ⇐ C#

[Anonymous]

Я работаю над лексером на основе DFA, использующим производные регулярных выражений для токенизации лексем. Я создал установку, которая теоретически должна точно обрабатывать упрощение регулярных выражений и переходы DFA. По большей части всё идёт гладко... пока я не столкнулся с несколькими случаями, когда всё идёт не так. Как будто какие-то скрытые крайние случаи издеваются надо мной.
Логика выглядит убедительной (следуя теории производных Бжозовского, реализуя упрощения, логику перехода и т. д.), и я задокументировал весь вывод. историю, поэтому легко проследить, что происходит. Но время от времени выходные данные выходят за рамки сценария, появляются дополнительные состояния, упрощения не полностью сокращаются или переходы ведут себя не совсем так, как ожидалось.
Я не ищу здесь ответы с ложечки. Просто любопытно, смогут ли какие-нибудь энтузиасты регулярных выражений или DFA заметить, чего мне не хватает, или получить удовольствие от проверки этого. На самом деле это своего рода увлекательная головоломка. Все должно быть правильно, но некоторые случаи просто ускользают.
Код находится здесь: GitHub
Основная логика для вычисления производных регулярных выражений и упрощений:
public class RegexDerivativeCalculator
{
/* ... */

public IRegexNode Derive(IRegexNode node, char c)
{
IRegexNode derivative;

switch (node.Type)
{
// ...
}

/* add history for debugging */
History.AddDerivative(node, c, derivative);

/* simplify the derivative before returning it */
return Simplify(derivative);
}

public IRegexNode Simplify(IRegexNode node)
{
IRegexNode simplified;

switch (node.Type)
{
// ...
}

/* if the simplified node is the same as the original node, we don't need to add it to the history */
if (!simplified.Equals(node))
{
History.AddSimplification(node, simplified);
}

return simplified;
}

/* derivative calculation */

private IRegexNode DeriveEpsilonNode(EpsilonNode node, char c)
{
return new EmptySetNode();
}

private IRegexNode DeriveEmptySetNode(EmptySetNode node, char c)
{
return new EmptySetNode();
}

private IRegexNode DeriveLiteralNode(LiteralNode node, char c)
{
return c == node.Literal
? new EpsilonNode()
: new EmptySetNode()
;
}

private IRegexNode DeriveUnionNode(UnionNode node, char c)
{
var leftDerivative = Derive(node.Left, c);
var rightDerivative = Derive(node.Right, c);

return new UnionNode(leftDerivative, rightDerivative);
}

private IRegexNode DeriveConcatenationNode(ConcatenationNode node, char c)
{
var left = node.Left;
var right = node.Right;
var leftDerivative = Derive(left, c);
var rightDerivative = Derive(right, c);

if (left.ContainsEpsilon)
{
return new UnionNode(
new ConcatenationNode(leftDerivative, right),
rightDerivative
);
}
else
{
return new ConcatenationNode(leftDerivative, right);
}
}

private IRegexNode DeriveStarNode(StarNode node, char c)
{
var child = node.Child;
var derivative = Derive(child, c);

if (derivative.IsEmptySet())
{
return new EmptySetNode();
}

return new ConcatenationNode(derivative, new StarNode(child));
}

/* simplification */

private IRegexNode SimplifyEpsilonNode(EpsilonNode node)
{
return node;
}

private IRegexNode SimplifyEmptySetNode(EmptySetNode node)
{
return node;
}

private IRegexNode SimplifyLiteralNode(LiteralNode node)
{
return node;
}

private IRegexNode SimplifyUnionNode(UnionNode node)
{
var left = node.Left;
var right = node.Right;
var simplifiedLeft = Simplify(left);
var simplifiedRight = Simplify(right);

if (simplifiedLeft.IsEmptySet())
{
return simplifiedRight;
}
if (simplifiedRight.IsEmptySet())
{
return simplifiedLeft;
}

if (left.IsEpsilon() && simplifiedRight.ContainsEpsilon)
{
return simplifiedRight;
}
if (right.IsEpsilon() && simplifiedLeft.ContainsEpsilon)
{
return simplifiedLeft;
}

// Avoid duplicate terms (R ∪ R = R)
if (simplifiedLeft.Equals(simplifiedRight))
{
return simplifiedLeft;
}

return new UnionNode(simplifiedLeft, simplifiedRight);
}

private IRegexNode SimplifyConcatenationNode(ConcatenationNode node)
{
var left = node.Left;
var right = node.Right;
var simplifiedLeft = Simplify(left);
var simplifiedRight = Simplify(right);

// Concatenation with Empty Set (∅ ∘ R or R ∘ ∅ = ∅)
if (simplifiedLeft.IsEmptySet() || simplifiedRight.IsEmptySet())
{
return new EmptySetNode();
}

// Concatenation with Epsilon (ε ∘ R = R and R ∘ ε = R)
if (simplifiedLeft.IsEpsilon())
{
return simplifiedRight;
}
if (simplifiedRight.IsEpsilon())
{
return simplifiedLeft;
}

return new ConcatenationNode(simplifiedLeft, simplifiedRight);
}

private IRegexNode SimplifyStarNode(StarNode node)
{
var simplifiedChild = Simplify(node.Child);

// Star of Empty Set (∅*) simplifies to Epsilon (ε)
if (simplifiedChild.IsEmptySet())
{
return new EpsilonNode();
}

// Star of Epsilon (ε*) simplifies to Epsilon (ε)
if (simplifiedChild.IsEpsilon())
{
return new EpsilonNode();
}

// Avoid redundant nested stars (if the child is already a star, return the simplified child)
if (simplifiedChild.IsStar())
{
return simplifiedChild;
}

return new StarNode(simplifiedChild);
}

}

Обновление 1:
При дальнейшем рассмотрении я обнаружил, что шагом упрощения было удаление критических состояний принятия в DFA. Проблема возникала в таких случаях, как a|a(b)*, где после использования 'a' регулярное выражение приводило к ε|(b)* . Для любого символа, кроме 'b', регулярное выражение все равно должно принимать, поскольку оно создает ε, а производная дает пустой набор. Если используется 'b', производная переходит к (b)*.
Упрощение схлопывается ε| (b)* непосредственно на (b)*, предполагая, что ε уже подразумевалось в звезде 'b'. Однако это было неверно, поскольку состояние с ε необходимо для представления точки, в которой можно распознать лексему 'a'. Исправление заключалось в том, чтобы избежать этого упрощения в таких случаях, тем самым сохранив необходимые состояния принятия.
/*
* This simplification has been removed because it would eliminate accepting branches.
* For example, `a|a(b)*` becomes `ε|(b)*` after consuming 'a', and if 'b' is not seen,
* the regex should still accept.
*/
if (left.IsEpsilon() && simplifiedRight.ContainsEpsilon)
{
// return simplifiedRight
// .PropagateLexeme(node);
}

/*
* This simplification has been removed because it would eliminate accepting branches.
* For example, `a(b)*|a` becomes `(b)*|ε` after consuming 'a', and if 'b' is not seen,
* the regex should still accept.
*/
if (right.IsEpsilon() && simplifiedLeft.ContainsEpsilon)
{
// return simplifiedLeft
// .PropagateLexeme(node);
}


Подробнее здесь: https://stackoverflow.com/questions/791 ... ected-ways