zbMATH — the first resource for mathematics

Grammar analysis and parsing by abstract interpretation. (English) Zbl 1149.68389
Reps, Thomas (ed.) et al., Program analysis and compilation, theory and practice. Essays dedicated to Reinhard Wilhelm on the occasion of his 60th birthday. Berlin: Springer (ISBN 978-3-540-71315-9/pbk). Lecture Notes in Computer Science 4444, 175-200 (2007).
Summary: We study abstract interpretations of a fixpoint protoderivation semantics 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 problem, classical grammar flow analysis algorithms, and parsing algorithms.
For the entire collection see [Zbl 1116.68008].

68Q42 Grammars and rewriting systems
68Q45 Formal languages and automata
68Q55 Semantics in the theory of computing
Full Text: DOI