27

Conventional parsers consume their entire input and produce a single parse tree. I'm looking for one that consumes a continuous stream and produces a parse forest [edit: see discussion in comments regarding why this use of that term may be unconventional]. My gut says that I can't be the first person to need (or think I need) such a parser, but I've searched off and on for months to no avail.

I recognize that I may be ensnared by the XY problem. My ultimate purpose is to parse a stream of text, ignoring most of it, and produce a stream of parse trees from the sections that are recognized.

So my question is conditional: if a class of parsers with these characteristics exists, what is it called? And if not, why not? What is the alternative? Perhaps I'm missing some way I can make conventional parsers do what I want.

  • 1
    Basically your parser parses a single document and yields a parse tree, then immediately starts parsing another document, etc. I suppose this behavior modification is trivial compared to the variety of parsing techniques applied to a single document. Hence the lack of a special term for it. – 9000 Oct 15 '14 at 20:37
  • 3
    I did a Google Search for "Parse Forest," and discovered that the Earley Parser produces them. – Robert Harvey Oct 15 '14 at 20:39
  • 7
    Are you possibly looking for monadic parser combinators -- that is, a larger parser composed of several smaller parsers. They are handy for situations where an "island" of one language is embedded in another. My former colleague on the C# design team Luke Hoban has a good article on them: blogs.msdn.com/b/lukeh/archive/2007/08/19/… – Eric Lippert Oct 16 '14 at 6:46
  • 3
    There is some confusion. Do you mean that you want a parse tree for each document in your stream, and that they form together a parse forest. That is not the usual meaning of parse forest. A parse forest is a set of parse trees for a single ambiguous document (simplifying a bit) that can be parsed in different ways. And that is what all answers are about. Is your stream composed of many complete documents separated by garbage, or is it a single document that has been partly garbled. Are your document supposed to be syntactically correct or not? The proper technical answer depend on that. – babou Oct 16 '14 at 17:51
  • 1
    Then forget all the answers about parse forests, and Earley, GLR, Marpa, derivatives. They are not apparently what you want unless another reason shows up. Are your documents syntactically correct? Some parsing technique can recreate context for partially garbled documents. Do you have a precise syntax for these documents. Is it the same one for all? Do you really want the parse trees, or would you be satisfied by isolating the documents, and possibly parse them later, separately. I think I know what could improve your processing, but I am not sure you can get that off the shelf. – babou Oct 16 '14 at 19:57
48
+150

A parser that returns a (partial) result before the whole input has been consumed is called an incremental parser. Incremental parsing can be difficult if there are local ambiguities in a grammar that are only decided later in the input. Another difficulty is feigning those parts of the parse tree that haven't been reached yet.

A parser that returns a forest of all possible parse trees – that is, returns a parse tree for each possible derivation of an ambiguous grammar – is called … I'm not sure if these things have a name yet. I know that the Marpa parser generator is capable of this, but any Earley or GLR based parser should be able to pull this off.


However, you don't seem to want any of that. You have a stream with multiple embedded documents, with garbage in between:

 garbagegarbage{key:42}garbagegarbage[1,2,3]{id:0}garbage...

You seem to want a parser that skips over the garbage, and (lazily) yields a sequence of ASTs for each document. This could be considered to be an incremental parser in its most general sense. But you'd actually implement a loop like this:

while stream is not empty:
  try:
    yield parse_document(stream at current position)
  except:
    advance position in stream by 1 character or token

The parse_docment function would then be a conventional, non-incremental parser. There is a minor difficulty of ensuring that you have read enough of the input stream for a successful parse. How this can be handled depends on the type of parser you are using. Possibilities include growing a buffer on certain parse errors, or using lazy tokenization.

Lazy tokenization is probably the most elegant solution due to your input stream. Instead of having a lexer phase produce a fixed list of tokens, the parser would lazily request the next token from a lexer callback[1]. The lexer would then consume as much of the stream as needed. This way, the parser can only fail when the real end of the stream is reached, or when a real parse error occurred (i.e. we started parsing while still in garbage).

[1] a callback-driven lexer is a good idea in other contexts as well, because this can avoid some problems with longest-token matching.

If you know what kind of documents you are searching for, you can optimize the skipping to stop only at promising locations. E.g. a JSON document always begins with the character { or [. Therefore, garbage is any string that does not contain these characters.

  • 5
    Your pseudocode is actually what I've been doing, but I thought it was just an ugly hack. The parser throws two kinds of exceptions (NO_MATCH and UNDERFLOW) which allow me to distinguish whether I should advance the stream position or wait for more input. – Kevin Krumwiede Oct 16 '14 at 16:21
  • 5
    @Kevin: I use this too, with some safety features, to handle incoming data from a network in a proprietary format. Nothing hacky about it! – Lightness Races in Orbit Oct 16 '14 at 16:43
5

There isn't one specific name for a parser that does this. But I will highlight one algorithm that does this: parsing with derivatives.

It consumes input, one token at a time. It will produce a parse forest at the end of input. Alternatively, you can also get the whole parse forest while in the middle of parsing (a partial parse).

Parsing with derivatives handles context-free grammars, and will produce a parse forest for ambiguous grammars.

It's an elegant theory, really, but is only in its infancy, and isn't widely deployed. Matt Might has a list of links to various implementations in Scala/Racket/etc.

The theory is easier to learn if you start with recognition with derivatives (that is, start with taking derivatives of languages, with the goal of recognizing some input to determine whether it's valid or not), and then alter the program to parse with derivatives (that is, change it so instead of taking derivatives of languages, it takes derivatives of parsers, and computes a parse forest).

  • 4
    Downvoter: could you please explain what was worthy of a downvote? If there's something I need to fix or improve, it sure would be nice to know. – Cornstalks Oct 16 '14 at 14:39
  • I am not the downvoter, and I would not dream of downvoting without a comment. But your enthousiastic paper has no reference to the many existing parsers that achieve the same result, regarding complexity and parse forest. Functional programming is great, but comparing a result with the existing literature on the subject is nice too. How convenient are your parse forest for further use? – babou Oct 16 '14 at 18:28
  • @babou: for the record, I'm not the author of that blog/paper. But yes, I agree I could add more detail comparing this algorithm with others and explain it in detail. Matt Might has a whole lecture on it, but it would be nice to consolidate it into this answer. If I get time I'll try to expand this answer. – Cornstalks Oct 16 '14 at 19:51
  • 1
    Do not spend too much time on expanding it. As far as I can tell, that is not what the OP is after. His question requires careful reading. His use of parse forest is not yours. - - Regarding derivatives ... it sounds like it must be interesting, but one must relate it to previous work ... and there is a significant body of it. But I do not mean in this answer, but in the papers of M Might, or his blog. – babou Oct 16 '14 at 20:41
2

Far from ideal, but I've seen it done more than once: at each input line try to parse. if fails, keep the line and add the next one. In pseudocode:

buffer = ''
for each line from input:
    buffer = buffer + line
    if can parse buffer:
        emit tree
        buffer = ''

The big problem is that in some languages you can't know if an expression is complete before reading the next line. In that case, you it seems that you could read the next one, and check if it's a valid beginning, or a valid continuation... But for that you need the exact language syntax

Worse, in those languages it's not hard to create a pathological case that can't be parsed until the end of file, even if it wasn't a single long statement.

0

In a nutshell

It seems that the fast solution to your problem is to define a REGEX, or a FSA (finite state automaton), that recognizes all the possible beginnings of documents (false positives are allowed, that would not actually correspond to a document). You can then run it very fast on your input to identify the next place where a document could start with few errors. It may cause a few erroneous position for a document start, but they will be recognized by the parser and abandonned.

So Finite State Automaton may be the parser name you were looking for. :)

The problem

It is always difficult to understand a practical problem, especially when the vocabulary may have many interpretation. The word parse forest was coined (afaik) for Context-Free (CF) parsing of ambiguous sentences that have several parse-trees. It can be generalized somewhat to parsing a lattice of sentences, or to other types of grammar. Hence all the answers about Earley, GLR, Marpa and derivative parsers (there are many others) that were not relevant in this case.

But that is apparently not what you have in mind. You want to parse a unique string that is a sequence of unambiguous documents, and get a parse-tree for each, or some kind of structured representation, since you do not really say how the syntax of your documents is defined, where it stand from a formal language point of view. What you have is an algorithm and tables that will do the parsing job when started at the beginning of a document. So be it.

The actual problem is that your stream of document contains considerable garbage that separates the documents. And it seem that your difficulty is to scan this garbage quickly enough. Your current technique is to start at the beginning, and try to scan from the first character, and skip to the restart at the next character whenever it fails, until you get a whole document scanned. Then you repeat stating from the first character after the document just scanned.

That is also the solution suggested by @amon in the second part of his answer.

It may not be a very fast solution (I have no way to test), because it is unlikely that the code of the parser is optimized to be very efficiently started on the beginning of a document. In normal use it does this only once, so that it is not a hot spot from an optimization point of view. Hence, your moderate happiness with this solution is not too surprising.

So what you really need is an algorithm that can quickly find the beginning of a document that starts with a mass of garbage. And you are lucky: such algorithms do exist. And I am sure you know it: it is called searching for a REGEX.

The simple solution

What you have to do is to analyze the specification of your documents to find how these documents start. I cannot exactly tell you how, as I am not sure how their syntax specification is organized formally. Possibly they all start with some word from a finite list, possibly mixed with some punctuation or numbers. That is for you to check.

What you have to do is to define a finite state automaton (FSA), or equivalently for most programmers a regular expression (REGEX) that can recognize the first few characters of a document: the more, the better, but it need not be very large (as that may take time and space). This should be relatively easy to do from the specification of your documents, and can probably be done automatically with a program that reads the specification of your documents.

Once you have produced your regexp, you can run it on your input stream to get very quickly to the beginning of your first (or next) document as follows:

I assume:
- docstart is a regex that matches the beginning of all documents
- search(regex, stream) is a function that searches the stream for a substring that matches regex. When it returns, the stream is reduced to its suffix substream starting at the beginning of the first matching substring, or to the empty stream is no match is found.
- parse(stream) attempts to parse a document from the beginning of the stream (what is left of it), and returns the parse tree in whatever format, or fails. When it returns, the stream is reduced to its suffix substream starting at the position immediately following the end of the parsed document. It calls an exception if the parse fails.

forest = empty_forest
search(docstart, stream)
while stream is not empty:
  try:
    forest = forest + parse(stream)
  except
    remove first character from stream
  search(docstart, stream)

Note that the removal of first character is necessary so that the next search will not find again the same match.

Of course, shortening of the stream is an image. It may just be an index on the stream.

A final note is that your regex does not need to be too accurate, as long as it recognizes all beginnings. If it recognizes occasionally a string that cannot be the beginning of a document (false positive), then the only penalty is the cost of one useless call to the parser.

So that may possibly help simplifying the regex, if useful.

About the possibility of a faster solution

The above solution should work pretty well in most cases. However, if you have really a lot of garbage and terabytes of file to process, there might be other algorithms that run faster.

The idea is derived from the Boyer-Moore string search algorithm. This algorithm can search a stream for a single string extremely fast because it uses a structural analysis of the string to skip reading most of the stream, jumping over fragments without even looking at them. It is the fastest searching algorithm for a single string.

Thr difficulty is that its adaptation to search regex, rather than a single string, seems very delicate and might not work as well, depending on the features of the regex you are considering. That might in turn depend on the syntax of the documents you are parsing. But do not trust me too much on this since I did not have time to do a careful reading of the documents I found.

I am leaving you with one or two pointers I found on the web, including one that is apparently a refereed research paper, but you should consider this as more speculative, possibly researchy, to be considered only if you had strong performance problems. And there is probably no of the shelf program that will do it.

-2

What you are describing can be described as SAX vs. SOM.

SAX - (Simple API for XML) is an event sequential access parser API developed by the XML-DEV mailing list for XML documents.

SOM - (XML Schema Object Model) random access to in memory representation of an XML file

There are implementations of both types in C#, and Java, and probably many more. Usually an XSD or DTD is optional.

The joy of SAX is that it is low memory overhead, which is great for large XML files. The trade off is that random access using SAX is either non-existent or slow, and worse the development time is usually considerable more than with SOM. The obvious problem with SOM is potentially large RAM requirements.

This answer is not applicable for all platforms and all languages.

  • 1
    Why do you think the OP is parsing XML? – Dan Pichelman Oct 16 '14 at 19:25
  • 1
    This does not answer the question. – user22815 Oct 16 '14 at 19:56
  • @Snowman Almost nothing so far was answering the question, including the first half of the accepted answer. No point in picking on anyone. The question needs careful reading. – babou Oct 16 '14 at 20:33
  • @babou I was not picking on anyone, I was explaining my downvote. – user22815 Oct 16 '14 at 20:37
  • @Snowman explaining my downvote. That is fair, and I do wish more users would do it. I am no native speaker: picking on him mays be too strong an expression. It is just that everyone has been making unwarranted assumptions. So it is not even worth noticing. It is true that this one seems a bit more off than the others. – babou Oct 16 '14 at 20:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.