使用Haskell Parsec在一次传递中解析正则表达式

Question

初步解释

我正在尝试使用自定义正则表达式引擎进行一些测试,但我厌倦了手工编写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$"

即使最终的NFA可以包含循环,标签也允许Show和Eq实例.例如,为表达式建模

-- "^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构建这个结构,我阅读了这个网站上有关递归构建类似List的结构的条目,并提出了以下内容:

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].

问题

当我进入下一步时解决问题:解析'|' 或声明.这应该的方式是,一个字符串,如:

-- "(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构建"Literal"链似乎也是这样工作的.

也许我应该使用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

Answer 1

你可能没有得到很多答案,因为这是一个很大的问题,需要在任何人考虑写答案之前阅读一篇大论文.

话虽如此,巧合的是巧合,我本周碰巧正试图从正则表达式中建立NFA.;-)

好的,所以眼前的问题是

Couldn't match expected type `x -> y` with actual type `Parser`.

在英语中,这意味着你有一个函数而不是解析器.快速浏览一下代码就可以看出你写的了

where
  p = p_regex <*> p_end 1

但是p_regex需要1个参数,而你没有提供一个参数.这就是您的代码不进行类型检查的原因.

好的,所以退一步,你的实际问题是什么？您想要将正则表达式解析为NFA,但是本文要求您将正则表达式转换为后缀表示法,然后解析它,然后构建NFA？

它看起来应该是可能的.当我实现这个时,我将解析和NFA生成作为单独的步骤,纯粹因此我可以检查解析器是否正常工作以及NFA生成是否单独工作.但听起来应该是可能的.Parsec允许您拥有用户状态,因此您可以将其用作堆栈来存储NFA片段.(或者,如果您愿意,可以明确传递它.)

如果你想要一个更准确的答案,你可能需要将其减少到更小,更集中的问题.

Answer 2

好的，所以问题基本上是：给定一个递归数据结构（在问题中定义），我如何创建一个解析器来一次性构建我的表达式。我最初的尝试本质上是一种“应用性”。如果没有条件分支，我就能够构建递归结构。但对于正则表达式解析，需要分支，这就是为什么我的方法不适用于or语句。

所以为了解决这个问题，我需要有一些状态。在函数式语言中携带状态的一个好方法是使用部分应用函数。我已经为此奠定了基础，p_char上面的签名是：

p_char :: ExpParser (T.State Char -> T.State Char)

所以我需要将它们组合起来是将多个(T.State Char -> T.State Char)函数组合在一起的组合器。因此，有了这种洞察力，排序就变成了：

p_many1 :: ExpParser (T.State Char -> T.State Char) -> ExpParser (T.State Char -> T.State Char)
p_many1 p = do
    f <- p
    (p_many1 p >>= return . (f .)) <|> return f

现在，对于or语句，我们需要的是采用“a|b|c”这样的表达式并创建一个如下函数：

\e -> Split (Literal 1 'a' e) (Split (Literal 2 'b' e) (Literal 3 'c' e))

为此，我们可以使用以下方法：

p_splitBy1 :: ExpParser (T.State Char -> T.State Char) -> Parsec String ParserState Char -> ExpParser (T.State Char -> T.State Char)
p_splitBy1 p sep = do
    f <- p
    (sep >> p_splitBy1 p sep >>= return . (\f' e -> Split (f e) (f' e))) <|> return f

这确实创建了我需要的结构。因此，如果其他人将来遇到类似的问题，也许这个问题/答案会有用。