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（如果我沒有記錯的話，儘量只讀一下它們，它們都很體面），以及各種研究論文中的一些例子討論類似問題中的問題。