Scala Parser Combinators: Parsing in a stream

Question

I'm using the native parser combinator library in scala, and I'd like to use it to parse a number of large files. I have my combinators set up, but the file that I'm trying to parse is too large to be read into memory all at once. I'd like to be able to stream from an input file through my parser and read it back to disk so that I don't need to store it all in memory at once.My current system looks something like this:

val f = Source.fromFile("myfile")
parser.parse(parser.document.+, f.reader).get.map{_.writeToFile}
f.close

This reads the whole file in as it parses, which I'd like to avoid.

J Cracknell · Accepted Answer · 2013-09-26 05:29:00Z

7

There is no easy or built-in way to accomplish this using scala's parser combinators, which provide a facility for implementing parsing expression grammars.

Operators such as ||| (longest match) are largely incompatible with a stream parsing model, as they require extensive backtracking capabilities. In order to accomplish what you are trying to do, you would need to re-formulate your grammar such that no backtracking is required, ever. This is generally much harder than it sounds.

As mentioned by others, your best bet would be to look into a preliminary phase where you chunk your input (e.g. by line) so that you can handle a portion of the stream at a time.

answered Sep 26, 2013 at 5:29

J Cracknell

3,5471 gold badge22 silver badges13 bronze badges

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

2 Comments

John Sullivan Over a year ago

That makes sense. Is there any way to take advantage of the fact that my top-level combinator is just a repetition? That is, could I read in the stream in chunks of the size of a single document?

J Cracknell Over a year ago

So long as you can figure out a way to (manually) split up the documents, yes. Then you would hand off each document to your grammar individually. Most PEG operators (including repetition) actually rely on backtracking, as the expressiveness of a PEG is predicated on being able to say "try this, and if that doesn't work we'll try something else".

Jens Egholm · Accepted Answer · 2013-09-25 20:39:32Z

0

One easy way of doing it is to grab an Iterator from the Source object and then walk through the lines like so:

val source = Source.fromFile("myFile")
val lines = source.getLines
for (line <- lines) {
    // Do magic with the line-value
}
source.close // Close the file

But you will need to be able to use the lines one by one in your parser of course.

Source: https://groups.google.com/forum/#!topic/scala-user/LPzpXo3sUVE

answered Sep 25, 2013 at 20:39

Jens Egholm

2,7103 gold badges24 silver badges35 bronze badges

Comments

Keith Pinson · Accepted Answer · 2013-09-25 21:56:20Z

0

You might try the StreamReader class that is part of the parsing package.

You would use it something like:

val f = StreamReader( fromFile("myfile","UTF-8").reader() )

parseAll( parser, f )

edited Sep 25, 2013 at 21:56

answered Sep 25, 2013 at 21:33

Keith Pinson

1,7251 gold badge14 silver badges17 bronze badges

Comments

user3329837 · Accepted Answer · 2014-02-19 20:06:21Z

0

The longest match as one poster above mentioned combined with regex's using source.subSequence(0, source.length) means even StreamReader doesn't help.

The best kludgy answer I have is use getLines as others have mentioned, and chunk as the accepted answer mentions. My particular input required me to chunk 2 lines at a time. You could build an iterator out of the chunks you build to make it slightly less ugly.

answered Feb 19, 2014 at 20:06

user3329837

Collectives™ on Stack Overflow

Scala Parser Combinators: Parsing in a stream

4 Answers 4

2 Comments

Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

2 Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related