代码之家 › 专栏 › 技术社区 › Nathan Shively-Sanders

parsec:回溯不起作用

backtracking parsec f# haskell

Nathan Shively-Sanders · 技术社区 · 15 年前

我正在尝试分析f type语法。我开始写语法分析,遇到了一些问题,所以我简化了 the grammar 具体来说:

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

在遇到fparsec的问题之后,我切换到parsec,因为我有一个 full chapter of a book dedicated to explaining it . 我的语法代码是

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 = choice [arrowP, identP]

但这只是堆栈溢出,因为语法是递归的——typep永远无法尝试 identP 因为它一直在努力 arrowP 一遍又一遍。接下来我尝试 try 在不同的地方,例如:

typeP = choice [try identP, arrowP]

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

我的错误对于任何一个成功编写语法分析器的人来说都是显而易见的。有人能指出吗?

3 回复 | 直到 15 年前

Christopher Done 15 年前

我认为问题在于,我假设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)))"

进一步展开,可能会让您感到困惑的是,在该语法中,它表示type->type,这意味着您可以在左侧有一个箭头。没关系,但必须放在括号里。这有帮助,也许看到下面的行动是有帮助的。它帮助了我。

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)"

Brian 15 年前

我认为你应该把左递归排除在语法之外。而不是

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

你得到一些像

typeStart ::= identifier 
type ::= typeStart (-> type)?
identifier ::= [A-Za-z0-9.`]+

我认为这将更容易直接翻译成parsec。(人们会认为 try 会起作用的,我希望它会起作用,但是的,我的经验是,在我理解“放在哪里”之前,我必须至少深入到parsec的腰部。 尝试 “让事情运转起来。)

也可以考虑看看 Monadic Parser Combinators in F# (以及之前7篇C博客文章)了解一些基本信息。我认为 parsec docs (如果我没记错的话,试着自上而下地读一下,它们很不错)以及各种研究论文中的一些例子都谈到了一些问题,比如你的问题。

kvb 15 年前

这不会帮助你理解哪里出错,但我建议你考虑使用 sepBy1 分析由分隔的类型 -> 符号。这将为您提供一个已解析类型的列表,然后您可以将其转换回函数类型。