如何在Haskell中编写一个回溯的连接解析器

Question

我正在尝试使用连接的解析器创建解析器来在parsec中回溯。

以下是代码：

ab = (try $ char 'a') <|> (try $ char 'b')
cd = (try $ char 'b') <|> (try $ char 'c')
abcd = (try $ many1 ab) >> (try cd)

这里，当我运行

parse abcd "parser"

使用输入“aaaaaaaaaaaaaac”时可以工作，但是在“aaaaaaaaaaaaab”上出现错误，这应该是可以接受的。有什么见解可以让它正常工作吗？谢谢提前。

- sakekasi

---

这是 CD 中的错别字吗？是不是应该是 D 而不是 B？ - DiegoNolan

Answer 1

你想在Haskell中编写正则表达式(a|b)+(b|c)？这是实现方法：

import Text.Parsec.String
import Text.Parsec

ab :: Parser Char
ab = char 'a' <|> char 'b'

bc :: Parser Char
bc = char 'b' <|> char 'c'

abc :: Parser String
abc = do
    a <- ab
    b <- bc
    return [a,b]

abbc :: Parser String
abbc = try abc <|> do
    c <- ab
    s <- abbc
    return (c:s)

parser :: String -> Either ParseError String
parser = parse abbc "(a|b)+(b|c)"

现在打开ghci，并按以下方式运行代码：

aaditmshah@home:~$ ghci
GHCi, version 7.6.3: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
Prelude> :load Test.hs
[1 of 1] Compiling Main             ( Test.hs, interpreted )
Ok, modules loaded: Main.
*Main> parser "aaaaaaaaaaaaaac"
Loading package array-0.4.0.1 ... linking ... done.
Loading package deepseq-1.3.0.1 ... linking ... done.
Loading package bytestring-0.10.0.2 ... linking ... done.
Loading package transformers-0.3.0.0 ... linking ... done.
Loading package mtl-2.1.2 ... linking ... done.
Loading package text-0.11.3.1 ... linking ... done.
Loading package parsec-3.1.5 ... linking ... done.
Right "aaaaaaaaaaaaaac"
*Main> parser "aaaaaaaaaaaaaab"
Right "aaaaaaaaaaaaaab"
*Main> 
Leaving GHCi.

这是如何工作的？让我们逐个解析器来理解：

ab :: Parser Char
ab = char 'a' <|> char 'b'

bc :: Parser Char
bc = char 'b' <|> char 'c'

这两个解析器很简单。它们分别对应正则表达式(a|b)和(b|c)。

abc :: Parser String
abc = do
    a <- ab
    b <- bc
    return [a,b]

这也比较简单。它对应于正则表达式(a|b)(b|c)。

abbc :: Parser String
abbc = try abc <|> do
    c <- ab
    s <- abbc
    return (c:s)

这是一件比较复杂的事情。该解析器执行以下操作：

1. 它尝试将输入与正则表达式 (a|b)(b|c) 匹配。
2. 如果匹配失败，则不消耗任何输入。相反，它会将输入的第一个字符与 (a|b) 匹配，然后返回步骤1以匹配剩余的输入。

因此它对应于正则表达式 (a|b)*(a|b)(b|c)，这与 (a|b)+(b|c) 相同。 try 组合子非常重要。如果没有它，解析器将尝试将输入与 (a|b)(b|c) 匹配。无法匹配时，它会抛出错误，而不是回溯并尝试替代条件。

- Aadit M Shah

---

顺便提一下，abc = sequence [ab, bc]，而 abbc = try abc <|> ((:) <$> ab <*> abbc)。 - max taldykin

@maxtaldykin 这很好，但我觉得单子代码比sequence或应用函子更容易解释。 - Aadit M Shah

是的，当然，这只是为了满足好奇读者的附注。 - max taldykin

如果我想要许多ab而不是许多1abc，我只需要abbc = try bc <|> ((:) <$> ab <*> abbc)？ - sakekasi

Answer 2

Aadit的回答很好。或者，如果你只想解析文本而不需要任何返回值，你可以使用manyTill:

import Text.Parsec
import Text.Parsec.Char
import Text.Parsec.String

ab :: Parser Char
ab = char 'a' <|> char 'b'

bc :: Parser Char
bc = char 'b' <|> char 'c'

abbc :: Parser ()
abbc = ab >> manyTill ab bc >> return ()

它有效：

> parse abbc "" "aaaaaaaaaaaaaac"
Right ()
> parse abbc "" "aaaaaaaaaaaaaab"
Right ()

然而，如果你实际上想要解析后的文本，那么manyTill并不是很方便，因为它只会返回第一个参数解析出的值，而不是第二个参数。 (在这个例子中，我通过调用return ()来丢弃了这些值。)

- Adam Dingle