Parallel parsing of operator precedence grammars. (English) Zbl 1259.68101

Summary: 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.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.


68Q42 Grammars and rewriting systems
68Q45 Formal languages and automata
Full Text: DOI