PARSEC : 역 추적이 작동하지 않습니다

StackOverflow https://stackoverflow.com/questions/2403873

문제

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 분리 된 유형을 구문 분석합니다 -> 기호. 이렇게하면 구문 분석 유형 목록이 제공되며 나중에 기능 유형으로 돌아갈 수 있습니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top