Cyclic Operator Precedence Grammars for Improved Parallel Parsing

Abstract

Operator precedence languages (OPL) enjoy the local parsability property, which essentially means that a code fragment enclosed within a pair of markers—playing the role of parentheses—can be compiled with no knowledge of its external context. Such a property has been exploited to build parallel compilers for languages formalized as OPLs. It has been observed, however, that when the syntax trees of the sentences have a linear substructure, its parsing must necessarily proceed sequentially making it impossible to split such a subtree into chunks to be processed in parallel. Such an inconvenience is due to the fact that so far much literature on OPLs has assumed the hypothesis that the equality precedence relation cannot be cyclic. We present an enriched version of operator precedence grammars which allows to remove the above hypothesis, therefore providing a little more expressive generality, and to further optimize parallel compilation.