Parsec：回溯不工作

Question

我想解析F＃类型的语法。我开始写一个[F]秒差距语法，遇到了问题，所以我简化the grammar到这一点：

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

运行与FParsec问题之后，我切换到秒差距，因为我有一个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" 

的问题是，秒差距默认不走回头路，所以

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

Answer 2

这不会帮助你理解错误的位置，但是我建议你考虑使用sepBy1来解析由->符号分隔的类型。这会给你一个经过分析的类型列表，然后你可以回到函数类型。

Answer 3

我想你应该因式分解左递归出来的语法。取而代之的

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

你喜欢的东西

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

那么这将是更容易直接转化为秒差距，我想。 （人们会认为try会起作用，我希望它能以某种方式发挥作用，但是，我的经验也是，在我懂得“在哪里投入try”以使事情顺利运作之前，我必须至少在Parsec中腰缠万贯。 ）

考虑一下也看Monadic Parser Combinators in F#（以及7个以前的C＃博客条目）的一些基本知识。我认为parsec docs（如果我没有记错的话，尽量只读一下它们，它们都很体面），以及各种研究论文中的一些例子讨论类似问题中的问题。