初步解释
我正在尝试使用自定义正则表达式引擎进行一些测试，但我厌倦了手动编写 NFA，因此我尝试制作一个解析器，但收效甚微。通常当人们解析一个正则表达式时，他们会创建多个中间结构，这些结构最终会被转换成最终的机器。对于我简单的 NFA 定义，我相信解析实际上可以一次性完成，尽管我还没有确定 (a) 为什么它实际上不能或 (b) 怎么做，尽管我的解析器可以解析非常简单陈述。
（简化的）状态实体的定义如下 [1]：
type Tag = Int
data State a =
Literal Tag a (State a)
| Split (State a) (State a)
| OpenGroup Tag (State a)
| CloseGroup Tag (State a)
| Accept -- end of expression like "abc"
| Final -- end of expression like "abc$"
标签允许 Show 和 Eq 实例，即使最终 NFA 可以包含循环。例如，对表达式建模
-- "^a+(b*)c$"
我可以使用 [2]
c = Literal 3 'c' $ Final 1
b = OpenGroup 1 $ Literal 2 'b' bs
bs = Split b $ CloseGroup 1 c
expr = Literal 1 'a' $ Split expr bs
我通过将 Thompson NFA 实现的 C 实现移植到 Haskell 为这个语法（没有组标签）制作了一个功能性的基于堆栈机器的解析器，但这需要两次通过 [3] 来构建，并且需要第三次才能完成上述结构。
因此，为了通过 Parsec 构建这个结构，我阅读了这个网站上关于递归构建类似列表的结构的条目，并提出了以下内容：
import Control.Applicative
import Text.Parsec hiding (many, optional, (<|>))
import Text.ExpressionEngine.Types
import qualified Text.ExpressionEngine.Types as T
type ParserState = Int
type ExpParser = Parsec String ParserState
type ExpParserS a = ExpParser (T.State a)
parseExpression :: String -> T.State Char
parseExpression e = case runParser p 1 e e of
Left err -> error $ show err
Right r -> r
where
p = p_rec_many p_char $ p_end 1
p_rec_many :: ExpParser (T.State a -> T.State a) -> ExpParserS a -> ExpParserS a
p_rec_many p e = many'
where
many' = p_some <|> e
p_some = p <*> many'
p_end :: Int -> ExpParserS a
p_end n = (Final n <$ char '$') <|> (Accept n <$ eof)
step_index :: ExpParser Int
step_index = do
index <- getState
updateState succ
return index
p_char = do
c <- noneOf "^.[$()|*+?{\\"
i <- step_index
return $ Literal i c
这足以解析像“ab”和“abc$”这样的字符串[4]。
问题
当我进入下一步时，问题就来了：解析'|' for 或语句。这应该工作的方式是一个字符串，如：
-- "(a|b|c)$"
应该创建以下结构：
final = Final 1
c = Literal 3 'c' final
b = Split (Literal 2 'b' final) c
a = Split (Literal 1 'a' final) b
所以这意味着将构建或语句的解析器必须采用它之后的替代表达式并将其传递给所有分支（我不相信将 Split 更改为采用列表会改变任何东西，因为每个条目仍然必须接收相同的以下表达式）。我的尝试是：
p_regex :: T.State Char -> ExpParser (T.State Char)
p_regex e = do
first <- p_rec_many p_char $ pure e
(Split first <$> (char '|' *> p_regex e)) <|> return first
主解析器更改为：
parseExpression :: String -> T.State Char
parseExpression e = case runParser p 1 e e of
Left err -> error $ show err
Right r -> r
where
p = p_regex <*> p_end 1
但这无法键入检查 [5]。我希望这是正确的，因为 p_regex 必须有一个构建的（状态 a）对象提供给它，并且使用 p_rec_many 构建“文字”链似乎也可以这种方式工作。
也许我应该使用 buildExpressionTable？这可能有助于解决这个特定问题，因为我可以将 ('$' <|> eof) 设为最高优先级。我开始尝试它，但我无法想象我将如何处理诸如星号加号和问号运算符之类的事情，因为它们都必须引用自己。
（编辑：我再次尝试使用 buildExpressionTable，在我看来，这对于我想要做的事情来说太简单了。它不能原生处理堆叠的后缀运算符 [例如“a？*”]，以及我的制作计划"'$' <|> eof" 最高优先级也不起作用，因为它只会附加到最后一个解析的'term'，而不是整个字符串。即使我可以做到，'$' 运算符也会是向后应用：它应该是最后一个解析的术语并馈送到前一个术语。我使用这个越多，我就越想知道我是否不应该在解析之前反转表达式字符串。）
问题
那么，我做错了什么？我确信有一种方法可以做我想做的事情，但到目前为止我还没有弄清楚。感谢您的时间。
脚注
[1] 如果您想确切了解我实际使用的内容，可以在此处找到。
[2] Open/CloseGroup 标签的想法是在 NFA 运行时跟踪组匹配。列出的表达式中的位置可能不完全正确，但是如果遇到 CloseGroup 标签，这种方式会正常工作，仅在找到相应的 OpenGroup 时才创建捕获组（即在上面的示例中，我们只会在至少一个时创建捕获'b' 被看到）。
所有其他标签构造都是正确的，我已经测试过这个 NFA 与预期的字符串匹配。
[3]这里描述了 Thompson 实现，我的移植版本可以在这里看到。这完美地构建了 NFA 子集，但在生成的结构中，每个下一个状态都将被包裹在 Just 中。这是因为我使用 Nothing 来表示悬空指针，后面的步骤将在正确的下一步中修补。我可以通过将所有（Just state）条目转换为（state）条目来将此结构转换为上面列出的结构，但这将是第三遍。此实现已经需要第一次将正则表达式转换为后缀表示法。
[4] 导致
Literal 1 'a' (Literal 2 'b' (Accept 1))
和
Literal 1 'a' (Literal 2 'b' (Literal 3 'c' (Final 1)))
分别。
[5]
Couldn't match expected type `a0 -> b0'
with actual type `ExpParser (T.State Char)'
Expected type: T.State Char -> a0 -> b0
Actual type: T.State Char -> ExpParser (T.State Char)
In the first argument of `(<*>)', namely `p_regex'
In the expression: p_regex <*> p_end 1