Grammar analysis and parsing by abstract interpretation

Patrick Cousot, Radhia Cousot

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publicationProgram Analysis and Compilation, Theory and Practice - Essays Dedicated to Reinhard Wilhelm on the Occasion of His 60th Birthday
PublisherSpringer Verlag
Pages175-200
Number of pages26
ISBN (Print)9783540713159
DOIs
StatePublished - 2007
EventSymposium on Program Analysis and Compilation, Theory and Practice. Dedicated to Reinhard Wilhelm on the Occasion of His 60th Birthday -
Duration: Jun 9 2006Jun 10 2006

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4444 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

OtherSymposium on Program Analysis and Compilation, Theory and Practice. Dedicated to Reinhard Wilhelm on the Occasion of His 60th Birthday
Period6/9/066/10/06

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Grammar analysis and parsing by abstract interpretation'. Together they form a unique fingerprint.

  • Cite this

    Cousot, P., & Cousot, R. (2007). Grammar analysis and parsing by abstract interpretation. In Program Analysis and Compilation, Theory and Practice - Essays Dedicated to Reinhard Wilhelm on the Occasion of His 60th Birthday (pp. 175-200). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4444 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-540-71322-7_9