如何在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"

使用输入“ aaaaaaaaaaaaaaaac”，但它在“ aaaaaaaaaaaaaaab”上出错，应该可以接受。

关于如何使它正常工作的任何见解

提前感谢

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)

这是使事情变得复杂的地方。该解析器执行以下操作：
它试图将输入与正则表达式(a|b)(b|c)匹配。
如果失败，则不消耗任何输入。相反，它将输入的第一个字符与(a|b)匹配，然后返回到步骤1以匹配其余的输入。

因此，它对应于与(a|b)*(a|b)(b|c)相同的正则表达式(a|b)+(b|c)。

try组合器很重要。没有它，解析器将尝试使输入与(a|b)(b|c)匹配。否则，将抛出错误，而不是回溯并尝试其他条件。

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 ()放弃了这些值。）