Name for this type of parser, OR why it doesn't exist

Question

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.

Answer 1

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.

Answer 2

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).

Answer 3

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.

Answer 4

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.

Answer 5

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.