c++ - 正则表达式NFA，用于未定义的 token 顺序

This question is unlikely to help any future visitors; it is only relevant to a small geographic area, a specific moment in time, or an extraordinarily narrow situation that is not generally applicable to the worldwide audience of the internet. For help making this question more broadly applicable, visit the help center。
                            
                        
                    
                
                                6年前关闭。
            
                    
我正在编写一个创建NFA的简单正则表达式解析器。这不是字符串解析器，但用于验证字符串。从本文http://www.codeproject.com/Articles/5412/Writing-own-regular-expression-parser，我根据自己的要求掌握了基础知识。即。 OR运算符（token1 | token2）和AND运算符（token1，token2）。

下一位运算符使我感到盲目，主要是因为，并且我搜索了许多文章，没有简单的正则表达式。 EITHER运算符。

我想解析这样的东西（token3，token1，token2）。每个必须存在一个，但是顺序并不重要。

我不需要正则表达式，我需要知道如何将其实现到NFA中。节点应如何链接在一起。

请，没有过度的技术答案。我仍然在整个一分钱/小卵石和epsilon节点上保持着头脑。

让我重申一下这个问题。 NFA如何实施令牌匹配的非特定顺序？当我在上面提到节点时，我并不是在问代码，而是在谈论许多教程所使用的整个圆和一分钱的构造。

可能的解决方案：

笔和纸在手，回想起我第一次写红黑树的时候。我可以对节点进行颜色编码。在逐步通过NFA时，每个当前节点均可访问的每个节点都充满了存储桶。对于可选节点（a | b），将添加指向两个节点的指针，如果输入符合任一节点，则执行步骤，然后再次填充存储桶。我将其称为“可选节点”，也许是“绿色”。如果我更改颜色，将其更改为“严格节点”（也许是“琥珀色”），则可以使解析器在任何情况下都不退出，而是在存储桶为空时退出。

最佳答案

以下DFA将使用状态A .. J和最终状态Z识别（1,2,3）的任何顺序。我认为没有比基本枚举DFA或NFA中的所有订单更有效的方法了。

A ---- 1 --> B -- 2 --> E -- 3 --> Z
 \            \-- 3 --> F -- 2 --> Z
  \--- 2 --> C -- 1 --> G -- 3 --> Z
   \          \-- 3 --> H -- 1 --> Z
    \- 3 --> D -- 1 --> I -- 2 --> Z
              \-- 2 --> J -- 1 --> Z

关于c++ - 正则表达式NFA，用于未定义的 token 顺序，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/17246696/