Parallel parsing of operator precedence grammars

Operator precedence grammars, introduced by Floyd several decades ago, enjoy properties that make them very attractive to face problems and to exploit technologies highly relevant in these days. In this paper we focus on their local parsability property, i.e., the fact that any substring s   of a longer one x.s.yx.s.y can be parsed independently of its context without the risk of invalidating the partial parsing when analyzing another portion of the whole string. We exploit this distinguishing property by developing parallel algorithms and suggest its further application to error recovery and incremental analysis. Great savings in terms of computational complexity are theoretically proved and have been reached in practice by first prototype tools.

► Floyd languages (FLs) are a deterministic sub-class of context-free languages. ► FLs enjoy many theoretical properties that make them very attractive. ► An important one is local parsability (LP). ► Thanks to LP, any substring can be parsed independently of its context. ► We exploit LP for natural parallel and incremental parsing algorithms.