Parsec: dar marcha atrás no funciona

Question

Estoy tratando de analizar la sintaxis de tipo F #. Empecé a escribir una gramática [F] Parsec y me encontré con problemas, por lo que he simplificado la gramática a esto:

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

Después de ejecutar a tener problemas con FParsec, me pasa a Parsec, ya que tengo un completa capítulo de un libro dedicado a explicar que . Mi código para esta gramática es

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"

El problema es que Parsec no dar marcha atrás por defecto, así

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

Lo primero que intenté fue reordenar typep:

typeP = choice [arrowP, identP]

Pero esto sólo desbordamientos de pila, porque la gramática es de izquierda recursiva - typep nunca se vuelve a tratar identP porque sigue tratando arrowP una y otra vez. Después probé try en varios lugares, por ejemplo:

typeP = choice [try identP, arrowP]

Sin embargo, nada de lo que hago parece cambiar los comportamientos básicos de (1) desbordamiento de pila o (2) el no reconocimiento de "->". Siguiendo un identificador

Mi error es probablemente obvio para cualquiera que haya escrito correctamente una gramática Parsec. Alguien puede señalarlo?

Answer 1

Creo que el problema es que, y estoy haciendo una suposición para F # (porque yo no lo sé), las flechas son asociativos derecha. No estoy seguro de cómo se supone precisa la gramática vinculado a ser, como no estoy muy versado en diferentes gramáticas. Pero si podemos asumir flechas son asociativos derecho que hace que el problema sea más fácil.

Así que con esa suposición que trivialmente podemos hacer:

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

Así que:

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

Ampliando aún más, lo que podría resultar confuso que es que en la gramática que se dice de tipo -> tipo, lo que significa que podría tener una flecha en el lado izquierdo. Eso está bien, pero es necesario que haya entre paréntesis. Lo que ayuda, tal vez viendo el siguiente en la acción es útil. Me ayudó.

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

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

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

Ahora podemos escribir flechas de la izquierda o la derecha de una flecha:

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

Answer 2

Creo que debe factor de la recursividad por la izquierda fuera de la gramática. En lugar de

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

se obtiene algo así como

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

A continuación, esto será más fácil de traducir directamente en parsec, creo. (Uno podría pensar que try funcionaría, y espero que de alguna manera lo hace, pero sí, mi experiencia también era que tenía que ser al menos hasta la cintura en Parsec antes de que yo entendía "dónde poner try" para que todo funcione. )

Considere ver también Monádicos Analizador combinadores en F # ( así como las 7 entradas de blogs anteriores # C) para algunos conceptos básicos. Creo que el parsec docs (trate simplemente leerlos de arriba hacia abajo , que son decentes, si no recuerdo mal), así como algunos de los ejemplos en los diferentes trabajos de investigación hablan de temas como el de su pregunta.

Answer 3

Esto no le ayudará a entender dónde va mal, pero yo sugeriría que buscan en el uso de sepBy1 para analizar los tipos separados por los símbolos ->. Esto le dará una lista de los tipos analizados, que luego se puede convertir de nuevo en los tipos de función después.