On parsing context free languages in parallel environments.

Abstract

Non-canonical generalization of several bottom-up parsing methods, including Simple Precedence, LR(k), SLR(k), and LALR(k) are considered. It is seen that these methods can readily be made to generate many concurrent reductions and thus can be used to advantage in parallel environments. it is suggested that such methods could be used to produce practical parsers for such parallel computers as the CDC Star-100. Further, the grammar classes defined by these parallel methods are studied and compared with the grammar classes defined by a number of serial parsing techniques.