Parallel Parsing (Parallel Ontleden)

摘要

The thesis begins by forming one coherent theory on parsing context-free grammarsin which three algorithms are described, first in the slow parallel case and then in the fast parallel case. Everything is tied up to essentially three similar partial parse relations. The presentation of each variant is kept as closely in line with the others as possible. It then goes on to describe a sharpest upper bound for the derivation length of acyclic context-free grammars and, almost as a corollary, its implication on acyclic noncircular attribute grammars. The next chapter covers the slow parallel decorating of all parses simultaneously. The bulk of the final chapter is on a parallel dag contraction algorithm. Working on such an algorithm is quite difficult because of the requirement of low time complexity. There is very little room to maneuver; even trivial steps must be analyzed on their contribution to the overall time complexity.