Parallel parsing of LRP(q, k) grammars.

This thesis presents new methods for deterministic parallel parsing of strong LR grammars and of LRP(q, k) grammars - a new subset of grammars suitable for bottom up parsing. The text of this thesis contains examples, definitions, algorithms and proofs of new approaches. During the parallel parsing process the input string is divided into substrings which are delivered to the processors. The processors form a binary tree architecture. The root of the tree contains the result of the parsing. The algorithm for merging of partial parsing results is the parallel reduction. That is the reason of logarithmic time complexity. Applicable context free grammars for bottom up parallel parsing are strong LR grammars. In the case of the context free grammars it is possible to parse the input string in log time. The strong LR(1) grammars allow the deterministic parallel parsing with using one of approaches presented in this thesis. LRP(q, k) grammars allow deterministic parallel parsing for more general languages than those generated by strong LR grammars. They use both the lookahead and the lookback strings. This idea is new and is presented in this thesis.Available from STL Prague, CZ / NTK - National Technical LibrarySIGLECZCzech Republi