秒差距:回溯不工作

Question

我试图分析F#类型的语法。我开始写作的一个[F]秒差距的语法和遇到的问题，因此我简化 语法 下：

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

运行之后入问题FParsec，我切换到秒差距，由于我有一个 完整章的一本书，专门用于解释它.我的代码这种语法

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]

但是，这只是堆溢出，因为语法是左-recursive--typeP永远不会尝试 identP 因为它一直试图 arrowP 一遍又一遍。接下来我想 try 在各种地方，例如：

typeP = choice [try identP, arrowP]

但没有我这样做似乎改变基本的行为(1)堆溢出或(2)不承认的"->"下一个标识符。

我的错误可能是显而易见的人已成功地编写一个秒差距语法。有人可以指出它?

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

我觉得你应该因素的左递归的语法。而不是的

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

你喜欢的东西

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

然后这将更容易直接翻译成秒差距，我想。(有人会认为 try 会工作，我期望它在某种程度上，但是，是的，我的经验也是，我必须至少在齐腰深秒差距之前，我曾经以理解的"放在哪里 try"做事的工作。)

考虑看到也 元分析器组合子在F# (及7个现有C#博客)对一些基础知识。我认为的 秒差距的文档 (尝试只是读取他们顶下，他们是体面的，如果我记忆正确地)以及某些实例中的各种研究文件谈论的问题一样，在你的问题。

Answer 3

这不会帮你理解你要去哪里错了，但我建议寻找使用 sepBy1 分析类型分开 -> 符号。这会给你一个列表中的分析类型，然后你就可以变回功能的类型之后。