O(log(n)) parallel parsing of a subclass of LL(1) languages
Priti Shankar · NOT FOUND REPOSITORY (Indian Institute of Science Bangalore) · 1990
A parallel algorithm that requires O(log(n)) time on O(n) processors on a CREW PRAM, is presented for the parsing of a subclass of the strong LL(1) languages. The technique involves mapping an input string into an output string representing the sequence of changes to the parsing stack during a parse sequence. If the input string is in the language, the output string is a member of the semi-Dyck set with r parenthesis pairs where r is the number of stack symbols. There exists an optimal algorithm for testing membership in this set.