Parsec : backtracking not working

Question

F # 형식 구문을 구문 분석하려고합니다. 나는 [F] 파섹 문법을 쓰기 시작 문제로 실행, 그래서 나는이 아래로 the grammar을 단순화 : 나는 full chapter of a book dedicated to explaining it이 있기 때문에

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] 

그러나 문법이 왼쪽 재귀 적이므로 오버플로가 발생합니다. typeP가 identP을 시도하지 않습니다. arrowP을 계속해서 시도하기 때문입니다.

typeP = choice [try identP, arrowP] 

을하지만 내가 아무것도 (1) ​​스택 오버 플로우 또는 (2) 비 인식의 기본 동작을 변경 것 같다 - 식별자 다음 ">"다음 : 나는 예를 들어, 다양한 장소에서 try을 시도했다.

필자의 실수는 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 (올바르게 읽으면 정상적으로 읽는 것을 시도해보십시오.), 다양한 연구 논문의 예제 중 일부는 질문에 대한 문제와 관련하여 이야기합니다.