Grammar semantics, analysis and parsing by abstract interpretation (Q655410)

Grammar flow problems consist in computing a function of the proto language generated by the grammar for each nonterminal. In the paper under review, abstract interpretations of a fixpoint protoderivation semantics are studied, defining the maximal derivations of a transitional semantics of context-free grammars akin to pushdown automata. The result is a hierarchy of bottom-up or top-down semantics refining the classical equational and derivational language semantics and including Knuth grammar problems, classical grammar flow analysis algorithms and parsing algorithms. The paper is absolutely self-contained, providing also the mathematical background and the necessary elements of abstract interpretation.