# BNF and Simultaneous Parsing

Let's say we have the following grammar

expr1 ::= ... // Actual definition doesn't matter
expr2 ::= ... //
expr3 ;:= ... //
foo ::=  expr1 | expr2 | expr3


When it comes to parsing foo we note that foo could be parsed in parallel.

p1 = task parse( expr1 )
p2 = task parse( expr2 )
p3 = task parse( expr3 )


Question

Would continuing on the first to complete be better.

result = task.WaitAny( p1, p2, p3 ) // wait for any (parsing) task to complete


or would it be better to wait for all the (parsing) tasks to complete?

task.WaitAll( p1, p2, p3 ) // wait for all (parsing) task to complete


What are the potential issues with simultaneous parsing?
or
Does the ordering of clauses matter?

If the grammar is amenable to limited-lookahead bottom-up parsing, then the parallelism is more or less implicit in the parsing algorithm, and there is little to be gained from parallel computing, at least in the sense proposed in the post. A standard LALR(k) parser is deterministic; it only does a single table-lookup for each action, based on the current state, the lookahead token(s) and -- in the case of reductions -- a single state value popped from a known location on the parse stack.

That's not to say that there is no possible benefit from the availability of multiple CPUs, but I suspect that benefit would come from segmenting the input using some kind of simple lexical analysis (text inside balanced braces, for example) and constructing individual parse trees for each segment.

If the grammar itself is highly ambiguous, as is the case for natural-language parsing, then different algorithms will be employed. CYK parsing, for example, used as the basis for many probabilistic parsers, can benefit significantly from parallel processing, and it is easy to find recent (and not-so-recent) papers on the subject on the internet. I found a dozen in a few seconds, and I won't bother pasting all of them particularly since I didn't read them, but I think that this paper by Mark Johnson has some pretty impressive results.

The answer dodges around the actual question, because I think the algorithmic analysis required to efficiently parallelise chart-parsing is more sophisticated than simply exploring alternative productions in parallel. But I hope it has some utility.

I think that rici's answer is a good summary of the situation. As he remarks, there is probably not too much to expect from from parallel computing in the case of grammars that lend themselves reasonnably well to deterministic parsing.

I am not sure whether the answer is the same when deterministic parsing requires heavy changes in the grammar structure, even assuming these changes are reversible, so that whatever parse tree is produced with the transformed grammar can be transformed back into a parse tree for the original grammar.

The Johnson paper, which I skimmed, seems to contain interesting considerations and experimental results. However, you should keep in mind that parsing is not a single problem. It does have many variants, depending on whether your language is deterministic, or just unambiguous, or possibly ambiguous but you want only some parses based on diverse criteria, or whether you want all parses, possibly to select from them on the basis of further processing. Non deterministic or ambiguous parsing is usually based on dynamc programming techniques, the best known of which are CYK and Earley's algorithm. But there are other views of it (see below).

Apparently, the Johnson's paper focusses on one of these categories: very ambiguous probabilistic grammars with Viterbi selection of the best parse, integrated in the algorithm.

If you were interested in getting the whole parse forest, representing all possible parses, there is a possibility that the results might be different.

On the other hand, both problems rely on a vision of the parsing process as computing an answer in a semiring algebra, so that the difference is not so much in the logic of the computation as it is in the data structures computed with. But parse forest are heavier structures to manipulate than are single trees with probabilities. I have no idea how much this would impact a complexity analysis.

Another point is that the semiring structure is an abstraction, but the same parse forest (seen semantically as a set of parse trees) may have many syntactic representations, some more condensed, or better organized, than others. Parallelization on multiple processors is very likely to have an impact on the syntactic representation of the sharing structures of the parse forest, which could impact further processing, unless it is also integrated adequately in the parallelization scheme.

It might be worth analyzing the problem abstractedly as a semiring evaluation procedure. There is some literature on that, and one place to start from might be Joshua Goodman's "Parsing inside out", though he does not address parallelization (afaik).

Another way to look at your question is parsing as intersection, i.e. to see parsing as the construction of the CF grammar $L_A$ for the intersection of the languages of another CF grammar $L$ and a NFA $A$. The main difference is that parsing corresponds to the case where the graph of the DFA is mostly acyclic (some cycles may be considered for special purposes such as handling of errors or ill-formedness). Possibly that view of the problem could lead to some insight.

Coming back to your question of whether alternative rules for a terminal could lead to parallelization. I would try tp look at it from the point of view of intersection with NFA.

• Thank you for the links to the various papers. Especially the Academia.edu one. If you don't see me for a few days you know where to find me buried beneath of research papers. Sep 21 '14 at 0:30