Barenghi, Alessandro; Crespi Reghizzi, Stefan; Mandrioli, Dino; Pradella, Matteo Parallel parsing of operator precedence grammars. (English) Zbl 1259.68101 Inf. Process. Lett. 113, No. 7, 245-249 (2013). 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. Cited in 3 Documents MSC: 68Q42 Grammars and rewriting systems 68Q45 Formal languages and automata Keywords:formal languages; parallel algorithms; operator precedence languages; local parsability; parallel parsing; incremental parsing PDFBibTeX XMLCite \textit{A. Barenghi} et al., Inf. Process. Lett. 113, No. 7, 245--249 (2013; Zbl 1259.68101) Full Text: DOI