Grammar analysis and parsing by abstract interpretation. (English) Zbl 1149.68389

Cousot, Patrick; Cousot, Radhia

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].

MSC:

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