PARSEC : 역 추적이 작동하지 않습니다
-
18-09-2019 - |
문제
F# 유형 구문을 구문 분석하려고합니다. 나는 [f] parsec 문법을 쓰기 시작했고 문제에 부딪쳤다. 그래서 나는 단순화했다 문법 이것까지 :
type ::= identifier | type -> type
identifier ::= [A-Za-z0-9.`]+
FPARSEC에 문제가 발생한 후 Parsec으로 전환했습니다. 그것을 설명하기 전의 책의 전체 장. 이 문법에 대한 내 코드는입니다
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을 재주문하는 것입니다.
typeP = choice [arrowP, identP]
그러나 문법이 왼쪽에있는 것이기 때문에 이것은 단지 오버플로 오버플로 스택입니다. 유형은 결코 시도하지 않습니다. identP
계속 노력하기 때문입니다 arrowP
계속해서. 다음으로 시도했습니다 try
예를 들어 다양한 장소에서 :
typeP = choice [try identP, arrowP]
그러나 내가하는 일은 (1) 스택 오버플로 또는 (2) 식별자에 따라 "->"의 인식이없는 기본 동작을 바꾸는 것 같지 않습니다.
내 실수는 아마도 Parsec 문법을 성공적으로 작성한 사람에게는 분명 할 것입니다. 누군가가 그것을 지적 할 수 있습니까?
해결책
나는 문제가 있다고 생각한다. 그리고 나는 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)"
다른 팁
문법에서 왼쪽 재귀를 고려해야한다고 생각합니다. 대신에
type ::= identifier | type -> type
identifier ::= [A-Za-z0-9.`]+
당신은 같은 것을 얻습니다
typeStart ::= identifier
type ::= typeStart (-> type)?
identifier ::= [A-Za-z0-9.`]+
그러면 이것은 Parsec으로 직접 번역하기가 더 쉬울 것이라고 생각합니다. (하나는 그것을 생각할 것입니다 try
효과가있을 것입니다. 어떻게 든 기대하지만 그렇습니다. 내 경험은 또한 내가 어디에 두어야할지 이해하기 전에 Parsec에서 허리 깊이 있어야한다는 것이 었습니다. try
"일을 작동시키기 위해.)
보는 것을 고려하십시오 F#의 모나디 한 파서 콤비네이터 일부 기본 사항에 대한 (7 개의 이전 C# 블로그 항목). 제 생각에는 Parsec Docs (여러 연구 논문의 일부 예제는 물론 질문의 문제에 대해 이야기하는 것뿐만 아니라 내가 올바르게 기억한다면, 그것들을 맨 위에 읽으십시오.
이것은 당신이 어디에서 잘못 될지 이해하는 데 도움이되지 않지만, 나는 사용을 바라 보는 것이 좋습니다. sepBy1
분리 된 유형을 구문 분석합니다 ->
기호. 이렇게하면 구문 분석 유형 목록이 제공되며 나중에 기능 유형으로 돌아갈 수 있습니다.