Packrat Parser in Scala hangs indefinitely even though there are no elements left in input

52 views Asked by At

I've a custom packrat parser written to handle some tokens. However when running the parser it hangs indefinitely even though all tokens were matched successfully by the parser. However changing the return type of one matcher to Parser from PackratParser fixes the issue. Not sure what is causing this infinite loop.

Code:

import scala.util.parsing.combinator.{PackratParsers, Parsers}
import scala.util.parsing.input.{NoPosition, Position, Positional, Reader}

sealed trait MyToken extends Positional
case class STMT_START(str: String) extends MyToken
case class STMT_END(str: String) extends MyToken

case class Start(str: String) extends MyToken
case class End(str: String) extends MyToken
case class Statement(tokens: Seq[Start], endTokens: Seq[End]) extends MyToken
case class AllStatements(stmts: Seq[Statement]) extends MyToken

class MyParser extends Parsers with PackratParsers {
  override type Elem = MyToken

  class TokenReader(tokens: Seq[MyToken]) extends Reader[MyToken] {
    override def first: MyToken = tokens.head
    override def atEnd: Boolean = tokens.isEmpty
    override def pos: Position =
      tokens.headOption.map(_.pos).getOrElse(NoPosition)
    override def rest: Reader[MyToken] = new TokenReader(tokens.tail)
  }

  def block: PackratParser[Statement] = {
    positioned {
      statementStart ~ statementEnd ^^ {
        case STMT_START(str) ~ STMT_END(endStr) ⇒
          Statement(
            Start(str) :: Nil,
            End(endStr) :: Nil
          )
      }
    }
  }

  def myexpressions: PackratParser[AllStatements] = {
    rep(block) ^^ { exprs ⇒
      println(s"matched expressions - expr $exprs ")
      AllStatements(exprs)
    }
  }

  def statementStart: PackratParser[STMT_START] =
    positioned {
      accept(
        "statementStart",
        {
          case jj @ STMT_START(_) =>
            println(s"PARSE: statementStart $jj")
            jj
        }
      )
    }

  def statementEnd: PackratParser[STMT_END] =
    positioned {
      accept(
        "statementEnd",
        {
          case jj @ STMT_END(_) =>
            println(s"PARSE: statementEnd $jj")
            jj
        }
      )
    }

  def parse[T](tokens: List[MyToken], func: Input ⇒ ParseResult[T]): Unit = {
    val reader = new PackratReader(new TokenReader(tokens))
    func(reader) match {
      case NoSuccess(msg, _) ⇒
        println(s"Failed $msg")
      case Success(result, next) ⇒
        if (next.atEnd) println(s"result of parsing - $result")
        else println("end of input expected")
    }
  }
}

object ParserTest {
  def main(args: Array[String]): Unit = {
    val test = new MyParser
    val tokens = List(
      STMT_START("   started"),
      STMT_END("bla"),
      STMT_START("   completed"),
      STMT_END("bla")
    )
    test.parse(tokens, test.myexpressions)
  }
}

Output:

PARSE: statementStart STMT_START(   started)
PARSE: statementEnd STMT_END(bla)
PARSE: statementStart STMT_START(   completed)
PARSE: statementEnd STMT_END(bla)

After this the program completely hangs, even though it prints that all 4 tokens were matched by the parser blocks.

Now in the same program if def block: PackratParser[Statement] is modified to def block: Parser[Statement] then the program runs fine and exists successfully.

Output:

PARSE: statementStart STMT_START(   started)
PARSE: statementEnd STMT_END(bla)
PARSE: statementStart STMT_START(   completed)
PARSE: statementEnd STMT_END(bla)
matched expressions - expr List(Statement(List(Start(   started)),List(End(bla))), Statement(List(Start(   completed)),List(End(bla)))) 
result of parsing - AllStatements(List(Statement(List(Start(   started)),List(End(bla))), Statement(List(Start(   completed)),List(End(bla)))))

Any idea what is causing this hang?

0

There are 0 answers