Invited Talk (Computer Science)

Parsing algorithms for formal grammars

doc. Alexander Okhotin, PhD. Department of Mathematics,
University of Turku, Finland


The talk will describe the main algorithms for parsing a sentence in a language defined by a formal grammar, and compare their applicability and computational complexity. The algorithms to be discussed include (i) tabular parsing algorithms, which inductively process all substrings of the given string: in particular, parsing by matrix multiplication; (ii) recursive descent parsing, in which the program code of a grammar is generated on the basis of a grammar; (iii) LR parsing and Generalized LR; (iv) parallel parsing by a circuit. Most algorithms apply to context-free grammars, as well as the more general conjunctive and Boolean grammars, and their stochastic variants.