parsing - EBNF to Scala parser combinator

parser-combinators

Question

Tengo el siguiente EBNF que quiero analizar:

PostfixExp      -> PrimaryExp ( "[" Exp "]" 
                                | . id "(" ExpList ")" 
                                | . length )*

Y esto es lo que obtuve:

def postfixExp: Parser[Expression] = (
    primaryExp ~ rep(
        "[" ~ expression ~ "]"
        | "." ~ ident ~"(" ~ repsep(expression, "," ) ~ ")" 
        | "." ~ "length") ^^ {
        case primary ~ list =>  list.foldLeft(primary)((prim,post) =>
                post match {
                    case "[" ~ length ~ "]" => ElementExpression(prim, length.asInstanceOf[Expression])
                    case "." ~ function ~"(" ~ arguments ~ ")" =>  CallMethodExpression(prim, function.asInstanceOf[String], arguments.asInstanceOf[List[Expression]])
                    case _ => LengthExpression(prim)
                }
            )
    })

Pero me gustaría saber si hay una mejor manera, preferiblemente sin tener que recurrir al casting (asInstanceOf).

Answer 1

Lo haría así:

type E = Expression

def postfixExp = primaryExp ~ rep(
    "[" ~> expr <~ "]" ^^ { e => ElementExpression(_:E, e) }
  | "." ~ "length" ^^^ LengthExpression
  | "." ~> ident ~ ("(" ~> repsep(expr, ",") <~ ")") ^^ flatten2 { (f, args) =>
      CallMethodExpression(_:E, f, args)
    }
) ^^ flatten2 { (e, ls) => collapse(ls)(e) }

def expr: Parser[E] = ...

def collapse(ls: List[E=>E])(e: E) = {
  ls.foldLeft(e) { (e, f) => f(e) }
}

expressions abreviadas a expr para abreviar, así como agregar el alias tipo E por el mismo motivo.

El truco que estoy usando aquí para evitar el feo análisis de casos es devolver un valor de función dentro de la producción interna. Esta función toma una Expression (que será la primary ) y luego devuelve una nueva Expression basada en la primera. Esto unifica los dos casos de expresiones de puntos y expresiones entre corchetes. Finalmente, el método de collapse se usa para fusionar la List lineal de valores de función en un AST apropiado, comenzando con la expresión primaria especificada.

Tenga en cuenta que LengthExpression simplemente se devuelve como un valor (usando ^^^ ) de su producción respectiva. Esto funciona porque los objetos complementarios para las clases de casos (suponiendo que LengthExpression sea ​​de hecho una clase de caso) amplían el valor de la función correspondiente delegando a su constructor. Por lo tanto, la función representada por LengthExpression toma una sola Expression y devuelve una nueva instancia de LengthExpression , que satisface nuestras necesidades para la construcción de árbol de orden superior.