scala parser-combinators

Entendiendo la tilde en los combinadores de parser de Scala



parser-combinators (3)

Soy bastante nuevo en Scala y mientras leía acerca de los combinadores de analizadores (los combinadores de analizadores de Magic Behind , lenguajes específicos de dominio en Scala ) encontré definiciones de métodos como esta:

def classPrefix = "class" ~ ID ~ "(" ~ formals ~ ")"

He estado leyendo la documentación de la API de scala.util.parsing.Parsers que define un método llamado (tilde) pero aún no entiendo su uso en el ejemplo anterior. En ese ejemplo (tilde) es un método que se llama en java.lang.String que no tiene ese método y hace que el compilador falle. Sé que (tilde) se define como

case class ~ [+a, +b] (_1: a, _2: b)

¿Pero cómo ayuda esto en el ejemplo anterior?

Me alegraría que alguien me diera una pista para entender qué está pasando aquí. ¡Muchas gracias por adelantado!

ene


El método ~ en el analizador combina dos analizadores en uno que aplica los dos analizadores originales sucesivamente y devuelve los dos resultados. Eso podría ser simplemente (en Parser[T] )

def ~[U](q: =>Parser[U]): Parser[(T,U)].

Si nunca combinó más de dos analizadores, eso estaría bien. Sin embargo, si encadena tres de ellos, p1 , p2 , p3 , con los tipos de retorno T1 , T2 , T3 , luego p1 ~ p2 ~ p3 , que significa p1.~(p2).~(p3) es de tipo Parser[((T1, T2), T3)] . Y si combina cinco de ellos como en su ejemplo, sería Parser[((((T1, T2), T3), T4), T5)] . Luego, cuando establezca un patrón de coincidencia en el resultado, también tendrá todos esos paréntesis:

case ((((_, id), _), formals), _) => ...

Esto es bastante incómodo.

Luego viene un truco sintáctico inteligente. Cuando una clase de caso tiene dos parámetros, puede aparecer en una posición de infijo en lugar de prefijo en un patrón. Es decir, si tiene un case class X(a: A, b: B) , puede hacer coincidir el patrón con el case X(a, b) , pero también con el case a X b . (Eso es lo que se hace con un patrón x::xs para coincidir con una Lista no vacía, :: es una clase de caso). Cuando escribe el caso a ~ b ~ c , significa case ~(~(a,b), c) , pero es mucho más agradable y más agradable que el case ((a,b), c) también, lo cual es complicado para hacerlo bien

Por lo tanto, el método ~ en el analizador devuelve un Parser[~[T,U]] lugar de un Parser[(T,U)] , por lo que puede hacer coincidir el patrón fácilmente en el resultado de múltiples ~. Además de eso, ~[T,U] y (T,U) son casi lo mismo, por lo isomórfico que puedas obtener.

Se elige el mismo nombre para el método de combinación en el analizador y para el tipo de resultado, porque el código resultante es natural de leer. Uno ve inmediatamente cómo cada parte en el procesamiento de resultados se relaciona con los elementos de la regla gramatical.

parser1 ~ parser2 ~ parser3 ^^ {case part1 ~ part2 ~ part3 => ...}

Se elige Tilda porque su precedencia (se une fuertemente) juega bien con los otros operadores en el analizador.

Un último punto, hay operadores auxiliares ~> y <~ que descartan el resultado de uno de los operandos, típicamente las partes constantes en la regla que no tienen datos útiles. Así que uno preferiría escribir

"class" ~> ID <~ ")" ~ formals <~ ")"

y obtener solo los valores de ID y formales en el resultado.


La estructura aquí es un poco complicada. Primero, observe que siempre define estas cosas dentro de una subclase de algún analizador, por ejemplo, la class MyParser extends RegexParsers . Ahora, puede observar dos definiciones implícitas dentro de RegexParsers :

implicit def literal (s: String): Parser[String] implicit def regex (r: Regex): Parser[String]

Lo que estos harán es tomar cualquier cadena o expresión regular y convertirlas en un analizador que coincida con esa cadena o esa expresión regular como un token. Son implícitos, por lo que se aplicarán cada vez que se necesiten (por ejemplo, si llama a un método en Parser[String] que String (o Regex ) no tiene).

Pero, ¿qué es esta cosa Parser ? Es una clase interna definida dentro de Parsers , el RegexParser para RegexParser :

class Parser [+T] extends (Input) ⇒ ParseResult[T]

Parece que es una función que toma entradas y las asigna a un resultado. Bueno, eso tiene sentido! Y puedes ver la documentación here .

Ahora solo podemos buscar el método ~

def ~ [U] (q: ⇒ Parser[U]): Parser[~[T, U]] A parser combinator for sequential composition p ~ q'' succeeds if p'' succeeds and q'' succeeds on the input left over by p''.

Entonces, si vemos algo como

def seaFacts = "fish" ~ "swim"

lo que sucede es, primero, "fish" no tiene el método ~ , por lo que se convierte implícitamente a Parser[String] que sí lo tiene. El método ~ luego quiere un argumento de tipo Parser[U] , por lo que implícitamente convertimos "swim" en Parser[String] (es decir, U == String ). Ahora tenemos algo que coincidirá con una entrada "fish" , y todo lo que quede en la entrada debe coincidir con "swim" , y si ambos son el caso, entonces seaFacts tendrá éxito en su coincidencia.


Usted debe Parsers.Parser . Scala a veces define el método y la clase de caso con el mismo nombre para ayudar a la coincidencia de patrones, etc., y es un poco confuso si está leyendo el Scaladoc.

En particular, "class" ~ ID es igual que "class".~(ID) . ~ es un método que combina el analizador con otro analizador de forma secuencial.

Hay una conversión implícita definida en RegexParsers que crea automáticamente un analizador a partir de un valor de String . Por lo tanto, "class" se convierte automáticamente en una instancia de Parser[String] .

val ID = """[a-zA-Z]([a-zA-Z0-9]|_[a-zA-Z0-9])*"""r

RegexParsers también define otra conversión implícita que crea automáticamente un analizador a partir de un valor Regex . Entonces, ID se convierte automáticamente en una instancia de Parser[String] también.

Al combinar dos analizadores, "class" ~ ID devuelve un Parser[String] que coincide con la "clase" literal y luego aparece de manera secuencial el ID expresión regular. Hay otros métodos como | y ||| . Para más información, lea Programación en Scala .