Parsec:回溯不起作用

Question

我试图解析F#类型的语法.我开始编写[F] Parsec语法并遇到问题,所以我将语法简化为:

type ::= identifier | type -> type
identifier ::= [A-Za-z0-9.`]+

在遇到FParsec的问题之后,我转到了Parsec,因为我有一本专门解释它的书的完整章节.我的语法代码是

typeP = choice [identP, arrowP]
identP = do
   id <- many1 (digit <|> letter <|> char '.' <|> char '`')
   -- more complicated code here later
   return id
arrowP = do
  domain <- typeP
  string "->"
  range <- typeP
  return $ "("++domain++" -> "++range++")"
run = parse (do t <- typeP
                eof
                return t) "F# type syntax"

问题是Parsec默认情况下没有回溯,所以

> run "int"
Right "int"
-- works! 
> run "int->int"
Left "F# type syntax"
unexpected "-"
expecting digit, letter, ".", "`" or end of input
-- doesn't work!

我尝试的第一件事是重新排序typeP:

typeP = choice [arrowP, identP]

但这只是堆栈溢出,因为语法是左递归的 - typeP永远不会尝试,identP因为它一直在尝试arrowP.接下来我尝试try了各种各样的地方,例如:

typeP = choice [try identP, arrowP]

但我所做的一切似乎都没有改变(1)堆栈溢出或(2)在标识符后面不识别" - >"的基本行为.

对于任何成功编写Parsec语法的人来说,我的错误可能是显而易见的.有人能说出来吗？

Answer 1

我认为问题在于,我正在为F#做一个假设(因为我不知道),箭头是正确的关联.我不确定链接语法应该有多精确,因为我不熟悉不同的语法.但是,如果我们可以假设箭头是正确的关联,使问题更容易.

因此,通过这种假设,我们可以做到:

identP = many1 (digit <|> letter <|> char '.' <|> char '`')

typeP = try arrowP <|> identP

arrowP = do
  i <- identP
  string "->"
  t <- typeP
  return $ "(" ++ i ++ " -> " ++ t ++ ")"

run = flip parse "F# type syntax" $ do
        t <- typeP
        eof
        return t

所以:

Haskell> run "int"
Right "int"
Haskell> run "int->int"
Right "(int -> int)"
Haskell> run "int->int->int->int"
Right "(int -> (int -> (int -> int)))"

进一步扩展,可能令你感到困惑的是,在那个语法中它表示类型 - >类型,这意味着你可以在左侧有一个箭头.那没关系,但需要在括号中.这有帮助,也许看到以下实际行动是有帮助的.它帮助了我.

typeP = try arrowP <|> parens typeP <|> identP

arrowP = do
 i <- parens typeP <|> identP
 string "->"
 t <- typeP
 return $ "(" ++ i ++ " -> " ++ t ++ ")"

parens p  = between (char '(') (char ')') p

现在我们可以在箭头的左侧或右侧写下箭头:

Haskell> run "int->int->int"
Right "(int -> (int -> int))"
Haskell> run "(int->int)->int"
Right "((int -> int) -> int)"