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
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
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
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:
docstart is a regex that matches the beginning of all documents
search(regex, stream) is a function that searches the
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
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
forest = empty_forest
while stream is not empty:
forest = forest + parse(stream)
remove first character from 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,
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.