Grammar semantics, analysis and parsing by abstract interpretation

Patrick Cousot, Radhia Cousot

Research output: Contribution to journalArticle

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-upor top-down semantics refining the classical equational and derivational language semantics and including Knuth grammar problems, classical grammar flow analysis algorithms and parsing algorithms.

Original languageEnglish (US)
Pages (from-to)6135-6192
Number of pages58
JournalTheoretical Computer Science
Volume412
Issue number44
DOIs
StatePublished - Oct 14 2011

Keywords

  • Abstract interpretation
  • Abstract semantics
  • Bottom-up semantics
  • Context-free grammar
  • Grammar flow analysis
  • Grammar problem
  • Parsing
  • Top-down semantics

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

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

  • Cite this