3
$\begingroup$

Since Earley parser finds all possible application variants for a token, can it parse text in parallel, unlike the usual parser like stack-based, etc. You just need to modify the start of each parallel chunk of tokens, then while going backwards while constructing a table you combine and validate the found rules like in standart Earley approach. But since vector operations are done there, it is possible to parallel this too. And splitting on tokens also. So its (theoretically, i haven't see project like that) GPGPU support for Earley parsing.

$\endgroup$
1
$\begingroup$

Yes, Earley's algorithm can be parallelized, but not in the way that you are thinking.

Earley's Algorithm In Particular

You ask about Earley's algorithm specifically. Parallelizing the algorithm in the way you suggest is unlikely to be faster. Researchers Peter Ahrens, John Feser, and Robin Hui report:

We first tried to naively parallelize the Earley algorithm by processing the Earley items in each Earley set in parallel. We found that this approach does not produce any speedup, because the dependencies between Earley items force much of the work to be performed sequentially.

The reason Earley's algorithm in particular is difficult to parallelize is because of interdependencies within the computation. To answer how successfully Earley's algorithm parallelizes, we need to solve this demarcation problem: What should be call Earley's algorithm? Seth Fowler and Joshua Paul explain:

There are several published algorithms (see, for example, Hill and Wayne[6]) for parallelizing a variant of the the Earley algorithm, the CYK algorithm. Unfortunately, in practice CYK has a much longer running time than Earley (even though it has the same worst-case complexity of $O(n^3)$), and so it is not typically used.

Most researcher's agree that there are few successful parallelizations of the algorithm, however. Fowler and Paul continue:

For the Earley algorithm itself, there are very few parallelization methods published (though there are many optimizations—see, for example, Aycock and Horspool [1]). One such method by Chiang and Fu [3] uses a decomposition similar to the one we develop,but goes on develop the algorithm for use on a specialized VLSI. Similarly, Sandstrom[7] develops an algorithm based on a similar decomposition....

Nonetheless, there are parallel versions. Peter Ahrens, John Feser, and Robin Hui who we cited earlier present "the LATE algorithm, which uses additional data structures to maintain information about the state of the parse so that work items may be processed in any order. This property allows the LATE algorithm to be sped up using task parallelism." The researchers claim a "120x speedup over the Earley algorithm on a natural language task."

Parallel parsing in general - usually impractical

Parallel parsing techniques have been studied for decades. Other parsing algorithms are more amenable to parallelization, such as the CYK algorithm mentioned above. But parallelizing parsing is only rarely a practical strategy. Most parsing tasks you are likely to encounter are much more efficiently performed serially, that is, in the old fashioned single-threaded way.

The reason parallel parsing algorithms are generally impractical is because parallelism has a lot of overhead that needs to be recouped by the gain in speed, while most parsing tasks can be performed incredibly quickly. (See parallel slowdown.) Quoting from Parsing Techniques: A Practical Guide, by Dick Grune and Ceriel J. H. Jacobs:

From a practical point of view, parallel parsing is interesting only for problems big enough to require considerably more time than a fraction of a second on a single processor. There are three ways in which a parsing problem can be this big: the input is very long (millions of tokens); the grammar is very large (millions of rules); or there are millions of inputs to be parsed. The last problem can be solved trivially by distributing the inputs over multiple processors, where each processor processes a different input and runs an ordinary, sequential, parser. Examples of very long inputs requiring parsing are hard to find. All very long parsable sequences occurring in practice are likely to be regular: generating very long CF sequences would require a place to store the nesting information during sentence generation. ...

The situation is different for parsing with very large grammars. These are found most often in linguistics. They are especially bothersome there since most linguistic applications require general CF parsing techniques, the speed of which depends on the grammar size.

References

Seth Fowler and Joshua Paul. "Parallel Parsing: The Earley and Packrat Algorithms." (2009). Note that this is a student project report for an undergraduate course.

Peter Ahrens and John Feser and Robin Hui. "LATE Ain’T Earley: A Faster Parallel Earley Parser." (2018) The arXiv, 1807.05642.

Grune D., Jacobs C.J.H. (2008) Parallel Parsing. Parsing Techniques. Monographs in Computer Science. Springer, New York, NY.

$\endgroup$
  • $\begingroup$ wow, thats an answer, dude! I m gonna to check info about that LATE. The reason Earley's algorithm in particular is difficult to parallelize is because of interdependencies within the computation. Hm, it depends from the grammar, if there are not much places where one token must occure it must not be that bad. Further, for task like compiling (first step - interpreting in AST) or natural language processing (just per sentence) you can do just parallel inputs. $\endgroup$ – user8426627 Jun 21 at 19:17

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.