Streaming parsing algorithms

Question

A parser is a procedure which decides if an input belongs to a certain language and produces a witness in the form of a parse tree.

Let a streaming parser be a parser which for any prefix $u$ can produce a partial parse tree corresponding to the productions that must be expanded to eventually accept any completion $uv$ of the prefix, for some completion $v$.

For example, if parsing the CFG $$ \begin{array}{lcl} S &\to& (a S+ b) \end{array} $$

then upon reading the prefix $aaa$, the streaming parser should report that any parse tree must consist of three top-level expansions of $S$.

Edit: I have two motivations for streaming parsing. The first is to provide a best-case constant bound on memory usage in the case where productions can always be resolved by a constant amount of lookahead. The second is to allow the consumer to lazily tear down the parse tree as the result is produced, e.g. by scheduling the execution of semantic actions associated with productions.

I am also interested in streaming parsing based on other foundations than context-free grammars, such as top-down parsing (parsing expression grammars, parser combinators, etc.).

Is there any existing work on such parsing algorithms?

Answer 1

I believe that the LR(k) property corresponds to your notion of a grammar which can be parsed in a streaming fashion. It's probably useful to (re)read Donald Knuth's 1965 paper On the Translation of Languages from Left to Right. In that paper, Knuth defines the LR(k) property in terms of the construction of the parse tree; a grammar is LR(k) iff "any handle is always uniquely determined by the string to its left and the $k$ terminal characters to its right." (p. 610) He then proves that every language recognizable by a deterministic push-down automaton is LR(1).

In effect, the stack in an LR(k) parser is essentially the lower-left corner of the final parse tree, which is one way to understand the phrase "the tree starts with". An LR(k) parser's stack will reflect the parser of all but the last $k$ symbols read, so unless $k$ is 0, which would considerably limit the possible languages, the prefix read will be slightly longer than the corresponding parse stack. But that doesn't seem to be excluded by the form of your question.

Unfortunately, it is not decidable whether a particular language is LR(k). It is easy enough to figure out if a particular CFG is LR(k) for some given $k$, but I don't believe there is any way to find such a $k$ for a given CFG other than trying all possible values in sequence.

At the end of the paper, Knuth proposes a possible generalization ($LR(k,t)$) in which the $t$th last handle of every parse tree fragment is uniquely-determined (so that $LR(k)$ is $LR(k,1)$). This might still fall into your idea of possible streaming parsers, although it no longer is able to stream in a strictly bounded context. He gives an example of a language which is not $LR(k,1)$ for any $k$ but is $LR(0,2)$; however, he does not propose any algorithm for constructing an $LR(k,t)$ parser for $t\ne 1$.

Given an arbitrary CFG, you can use Tomita's Generalized LR (GLR) parsing algorithm, which, if implemented correctly, will produce all possible parses for a given string in $O(n^3)$ time and space. The GLR parser maintains a data structure from which all viable parse stacks can be derived; in particular, it is easy to find the longest prefix which corresponds to an unambiguous parse stack. However, there is no guarantee that all the parse stacks at a particular point in the parse (before the end) are actually viable; only that all viable stacks are included. So it is possible that there is a longer unambiguous prefix. A Tomita parser would correctly find the longest prefix for Knuth's $LR(0,2)$ example, but I don't know if that result could be generalized.

Answer 2

The first solution coming to mind is an extension of Brzozowski's derivatives as context-free grammars are closed under derivative operation with respect to a letter.

Here that question answered: https://cstheory.stackexchange.com/questions/3280/generalizations-of-brzozowskis-method-of-derivatives-of-regular-expressions-to

Answer 3

As mentioned above LL would allow streaming out of box, since it would have to report the top of the parse tree with all non-terminals before reporting any terminal symbol that is coming from the text being parsed. Like in your example:

S→ aS + b

Upon reading first 'a' from input string 'aaa' it would have to say first that it is start of rule (non-terminal) S, something like:

• S begins
• a

Now, what if terminal 'a' can appear as beginning of more than one rule reachable from the top? That would require parser to postpone output and read more before the only one possible match found. That requires some lookahead that can be fixed like LL(1) or LL(2) or adaptive like LL(*) that ANTLR parser generator is using.

LR parser, on the other hand, doesn't tell top of the parse tree first, but kind of does it in reverse order. It first reports terminals and then says what rule (non-terminal) was that. Advantage is that parser can see more tokens before it has to decide what rule that was.

As it turns out, it is also possible to do streaming with LR parser and turn output to that of LL parser, but with advantage of stronger LR parser for the same lookahead than LL. That would mean that parser has to postpone output until place of current subtree is fixed in the parse tree. I was able to make such parser for parsing EDI text documents, like EDIFACT, HL7 and so on. Basically, I precalculated during parse table construction which rule is referenced where and when it is safe to report the beginning of such rule. And extended stack data to hold additional flag if terminal or non-terminal was already reported and also to keep subtrees of folded rules if they were not yet reported.

I didn't find any paper or book that would discuss that anywhere. There could be some neat way to do that with minimum overhead. Overhead that would best happen during parsing table construction once, and keep the parser driver fast. I was able to find two ways of doing it, and then kept the one that does more work at parser table generation. And it is streaming very nicely! From this point of view LR and LL are not so different. I would say that for a nice grammar modified LR(k) with this addition is similar to LL(*). Both would cache and postpone output if not enough input has been seen to decide what it is. Implementation-wise, one of them is easier than another. Where LL(*) would use backtracking, in modified LR(k) partial parse trees are just cached before output.