你想在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)
匹配。无法匹配时,它会抛出错误,而不是回溯并尝试替代条件。