djspiewak / parseback

A Scala implementation of parsing with derivatives
http://parseback.io
Apache License 2.0
197 stars 22 forks source link

No parse when using filter for associativity disambiguation + explicit parenthesis #34

Open danleh opened 6 years ago

danleh commented 6 years ago

Given the following test case

import cats.Eval
import parseback._
import parseback.ast._
import parseback.compat.cats._

object Testcase extends App {

  sealed trait Expr extends Node
  case class Identifier(name: String) extends Expr with LeafNode
  case class Application(left: Expr, right: Expr) extends Expr with BinaryNode {
    override def assocLeft: Boolean = true
    override def sym: Symbol = 'app
  }

  lazy val expr: Parser[Expr] = (
    """[a-zA-Z0-9]+""".r ^^ { (_, name) => Identifier(name) }
      | expr ~ " " ~ expr ^^ { (_, fun, _, arg) => Application(fun, arg) }
      | "(" ~> expr <~ ")"
    ) filter prec(Application)

  // Test 1, correct: gives the left assoc. AST
  println(expr(LineStream[Eval]("function1 function2 argument")).value.map(_.toList))

  // Test 2, bug? gives no error but an empty list of ASTs
  println(expr(LineStream[Eval]("function1 (function2 argument)")).value.map(_.toList))
}

where we define a simple grammar with just Identifiers and function Application. I intend application to be left-associative and thus write filter prec(Application) with BinaryNode and def assocLeft: Boolean = true.

The first example works fine, only the left-associative AST is returned. However, in the second example where we use parentheses, an empty list is returned (where we would expect the right-associative AST).

Am I using filter and/or BinaryNode wrong? Or is this a bug?

djspiewak commented 6 years ago

Hey! I'm back. :-) Sorry, longest not-seeing-of-an-issue ever. This definitely looks like a bug to me. You're using things correctly. Honestly, an empty list of results should never happen. The disambiguation filters are designed in such a way that they should never eliminate all results unless the grammar itself encodes precedence in an opposite way from the filters (that isn't happening here). I'll look into it.