4
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ It looks similar to parsing with bounded lookahead. For example LL(1) parsers should fit the bill. $\endgroup$ – adrianN Aug 12 '16 at 14:21
  • $\begingroup$ Yes, that seems right! Indeed, they produce a leftmost derivation in streaming fashion, using only working memory equal to the number of unresolved nonterminals on the stack. $\endgroup$ – Ulrik Rasmussen Aug 15 '16 at 7:16
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I have edited my question in order to clarify my motivation a bit. I guess that LL(k) and LR(k) parsers can be considered streaming in the sense that they produce a leftmost derivation and a reversed rightmost derivation, respectively, in a streaming fashion. I am mostly interested in deterministic or disambiguated parsing where every recognized input string has a unique parse tree. $\endgroup$ – Ulrik Rasmussen Aug 15 '16 at 7:24
  • $\begingroup$ @UlrikRasmussen: LL(k) and LR(k) parsers are very different, and in an essential way. LR(k) parsers actually construct the "prefix" of the parser tree in a streaming fashion. Since LL(k) parsers are predictive rather than constructive, the same cannot be said of them; the parser stack does represent a part of the tree but most of it has not yet been filled in. In any case, since all LL(k) grammars are also LR(k), LL (top-down) parsing does not provide any advantage over LR parsing, and the LR machines are no more complex and equally fast. $\endgroup$ – rici Aug 15 '16 at 20:51
  • $\begingroup$ I am not sure I understand your comment about LL(k) not being constructive. The LL(k) stack is the leaves of a partially expanded parse tree; the sequence of expansions to get there from the start symbol is the leftmost derivation. The LR(k) result is just the "dual" of this: We have derivations for the nonterminals on the stack, but we don't yet know how to get to this point from the start symbol. I am aware that LR(k) has more recognition power, so from that perspective, it is arguably advantageous. $\endgroup$ – Ulrik Rasmussen Aug 16 '16 at 5:36
  • $\begingroup$ On the other hand, there is one point related to streaming where I would argue that LL(k) might be advantageous over LR(k). Since the LR(k) derivation is produced in reverse, this means that productions for leaves are returned first, and the production for the root of the tree is returned only when all of the input has been processed. For LL(k), this is the other way around. If the result is used to schedule semantic parsing actions, a consumer might prefer a derivation that is not in reverse order. $\endgroup$ – Ulrik Rasmussen Aug 16 '16 at 5:41
  • $\begingroup$ @Ulrik: That depends on whether it is meaningful to initiate a semantic action before the semantics of the children is known. People seem to want to do that once in a while but I'd argue that executing semantic actions bottom up (synthesized) is more commonly useful. Consider, for example, the simple case of evaluating an expression. $\endgroup$ – rici Aug 16 '16 at 5:57
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

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.