Scala parser combinator, large file issue

Question

I have written a parser as follows:

class LogParser extends JavaTokenParsers {

  def invertedIndex: Parser[Array[Array[(Int, Int)]]] = {
    num ~> num ~> num ~> rep(postingsList) ^^ {
      _.toArray
    }
  }

  def postingsList: Parser[Array[(Int, Int)]] = {
    num ~> rep(entry) ^^ {
      _.toArray
    }
  }

  def entry = {
    num ~ "," ~ num ^^ {
      case docID ~ "," ~ count => (docID.toInt, count.toInt)
    }
  }

  def num = wholeNumber ^^ (_.toInt)

}

If I parse from a (270MB) file with a FileReader as follows:

val index = parseAll(invertedIndex, new FileReader("path/to/file")).get

I get an Exception in thread "main" java.lang.StackOverflowError (I have also tried wrapping in a BufferedReader) but I can fix it by first reading the file into a String like so:

val input = io.Source.fromFile("path/to/file")
val str = input.mkString
input.close()
val index = parseAll(invertedIndex, str).get

Why is this the case? Is there any way to avoid reading it as a String first, it seems a waste?

What's the current size of your stack, and how much larger do you have to make your stack to avoid the StackOverflowException? How much smaller must the stack be to make the String version overflow? (You can set your stack to 16MB by launching like so: scala -J-Xss16M) — DaoWen
– DaoWen, Commented Nov 3, 2012 at 23:34
I was just using the default stack size, but when I set it to 16M the program was still running 30mins later... — Robert
– Robert, Commented Nov 4, 2012 at 13:02
Looking at the bug @DonRoby liked to and thinking about how parser combinators work, I think the backtracking mechanism would require the parser to have the entire file in memory to enable backtracking anyway. This does sound like a bug in the PagedSeq bug, so you're probably best off just reading it into a string. — DaoWen
– DaoWen, Commented Nov 4, 2012 at 21:21
I've run into this problem before, and have also used the string workaround. I've also just created a new issue (SI-6612; with an example that isn't parser combinator-specific), since this seems fairly distinct from SI-6520—the problem is blowing the stack, not running out of memory. — Travis Brown
– Travis Brown, Commented Nov 5, 2012 at 4:01

Ivan Meredith · Accepted Answer · 2012-11-16 02:14:01Z

1

There is another library[1] that is a lot like the scala parser combinators that supports Trampolining which is what you need to stop the stackoverflow errors.

[1] https://github.com/djspiewak/gll-combinators

answered Nov 16, 2012 at 2:14

Ivan Meredith

2,22214 silver badges13 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Scala parser combinator, large file issue

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related