La comprensión de la tilde en el analizador de Scala combinadores

Question

Soy bastante nuevo a Scala y al leer acerca de combinadores de analizadores sintácticos (The Magic Behind Parser Combinators, Domain-Specific Languages in Scala) me encontré con definiciones de métodos como esto:

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

He estado leyendo el throught API doc de scala.util.parsing.Parsers que define un método llamado (tilde) pero todavía no entiendo su uso en el ejemplo anterior. En ese ejemplo (tilde) es un método que se invoca 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?

Estaría feliz si alguien pudiera darme una pista para entender qué está pasando aquí. ¡Muchas gracias de antemano!

Ene

Answer 1

La estructura aquí es un poco complicada. Primero, observe que siempre define estas cosas dentro de una subclase de algún analizador, p. class MyParser extends RegexParsers. Ahora, es posible que tenga en cuenta dos definiciones implícitas dentro RegexParsers:

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

Lo que estos van a hacer es tomar cualquier cadena o expresión regular y convertirlos en un analizador que coincida con esa cadena o expresión regular que como una muestra. Están implícitos, por lo que se aplicarán cada vez que sean necesarios (por ejemplo, si llama a un método en Parser[String] que no tiene String (o Regex)).

Pero, ¿qué es esto Parser cosa?Es una clase interna definida en el interior Parsers, la supertrait para RegexParser:

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

parece que es una función que toma la entrada y lo asigna a un resultado. Bueno, eso tiene sentido! Y puede ver la documentación para él here.

Ahora sólo 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'. 

Por lo tanto, si vemos algo así como

def seaFacts = "fish" ~ "swim" 

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

Answer 2

Debe pago y envío 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ás leyendo el Scaladoc.

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

Hay an implicit conversion definido en RegexParsers que crea automáticamente un analizador a partir de un valor 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 analizador desde un valor Regex. Por lo tanto, 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 la expresión regular ID de forma secuencial. Hay otros métodos como | y |||. Para obtener más información, lea Programming in Scala.

Answer 3

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 combinado de más de dos analizadores, que estaría muy bien. Sin embargo, si encadena tres de ellos, p1, p2, p3, con tipos de retorno T1, T2, T3, a continuación, p1 ~ p2 ~ p3, lo que significa p1.~(p2).~(p3) es de tipo Parser[((T1, T2), T3)]. Y si combina cinco de ellos como en su ejemplo, eso sería Parser[((((T1, T2), T3), T4), T5)]. Luego, cuando el patrón coincida con el resultado, también tendrá todas esas parantheses:

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

Esto es bastante incómodo.

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

Así el método ~ en Analizador devuelve una Parser[~[T,U]] en lugar de un Parser[(T,U)], por lo que puede coincidir con el patrón fácilmente en el resultado de múltiples ~. Además de eso, ~[T,U] y (T,U) son prácticamente lo mismo, lo más isomorfo que se puede obtener.

El mismo nombre se elige 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 del resultado se relaciona con los elementos de la regla de la gramática.

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

Tilda se elige porque su prioridad (que se une fuertemente) juega muy bien con los demás operadores del analizador.

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

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

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