Parsec: retrocesso não funciona

Question

Eu estou tentando analisar F # tipo de sintaxe. Eu comecei a escrever um [F] Parsec gramática e passou a ter problemas, então eu simplificado a gramática resume a isto:

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

Depois de correr em problemas com FParsec, mudei para Parsec, desde que eu tenho um completo capítulo de um livro dedicado a explicar que . Meu código para esta gramática é

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"

O problema é que Parsec não volta atrás por padrão, então

> run "int"
Right "int"
-- works! 
> run "int->int"
Left "F# type syntax"
unexpected "-"
expecting digit, letter, ".", "`" or end of input
-- doesn't work!

A primeira coisa que eu tentei foi typeP reordenar:

typeP = choice [arrowP, identP]

Mas isso só pilha excede porque a gramática é deixado-recursiva - typeP nunca chega a tentar identP porque mantém tentando arrowP mais e mais. Em seguida eu tentei try em vários lugares, por exemplo:

typeP = choice [try identP, arrowP]

Mas nada que eu faça parece mudar os comportamentos básicos de (1) estouro de pilha ou (2) não reconhecimento de "->". Seguindo um identificador

Meu erro é provavelmente óbvio para qualquer pessoa que tenha gravado com êxito uma gramática Parsec. Pode apontar alguém para fora?

Answer 1

Eu acho que o problema é que, e eu estou fazendo uma suposição de F # (porque eu não soubesse), flechas são associativos à direita. Eu não tenho certeza de como precisa a gramática ligada é suposto ser, como eu não estou bem versado em diferentes gramáticas. Mas se podemos assumir flechas são associativos à direita que torna o problema mais fácil.

Assim, com essa suposição podemos trivialmente fazer:

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

Assim:

Haskell> run "int"
Right "int"
Haskell> run "int->int"
Right "(int -> int)"
Haskell> run "int->int->int->int"
Right "(int -> (int -> (int -> int)))"

expandir ainda mais, o que pode ser confuso é que em que a gramática diz tipo -> tipo, o que significa que você poderia ter uma seta no lado esquerdo. Isso é bom, mas precisa estar em parênteses. O que ajuda, talvez vendo o seguinte em ação é útil. Ele me ajudou.

typeP = try arrowP <|> parens typeP <|> identP

arrowP = do
 i <- parens typeP <|> identP
 string "->"
 t <- typeP
 return $ "(" ++ i ++ " -> " ++ t ++ ")"

parens p  = between (char '(') (char ')') p

Agora podemos escrever setas à esquerda ou à direita de uma seta:

Haskell> run "int->int->int"
Right "(int -> (int -> int))"
Haskell> run "(int->int)->int"
Right "((int -> int) -> int)"

Answer 2

Eu acho que você deve fator a recursão esquerda para fora da gramática. Em vez de

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

você começa algo como

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

Então este será mais fácil de traduzir diretamente em parsec, eu acho. (Alguém poderia pensar que try iria funcionar, e espero que de alguma forma faz, mas sim, a minha experiência também foi que eu tinha que ser, pelo menos até a cintura na Parsec antes de eu nunca entendeu "onde colocar try" para fazer as coisas funcionarem. )

Considere vendo também monádicas Parser Combinadores em F # ( bem como os 7 entradas de blog C # anteriores) para algumas noções básicas. Eu acho que a parsec docs (tentar apenas lendo-os de cima para baixo , eles são decentes, se bem me lembro), bem como alguns dos exemplos dos vários trabalhos de pesquisa falar sobre questões como a de sua pergunta.

Answer 3

Isso não vai ajudar você a entender onde você está indo errado, mas eu sugiro olhando para usar sepBy1 a tipos de análise separados por símbolos ->. Isto lhe dará uma lista de tipos analisada, que você pode então voltar atrás em tipos de função depois.