Grammar semantics, analysis and parsing by abstract interpretation

Patrick Cousot; Radhia Cousot

doi:10.1016/j.tcs.2011.06.005

Grammar semantics, analysis and parsing by abstract interpretation

Patrick Cousot, Radhia Cousot

Computer Science

Research output: Contribution to journal › Article › peer-review

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 language	English (US)
Pages (from-to)	6135-6192
Number of pages	58
Journal	Theoretical Computer Science
Volume	412
Issue number	44
DOIs	https://doi.org/10.1016/j.tcs.2011.06.005
State	Published - 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
General Computer Science

Access to Document

10.1016/j.tcs.2011.06.005

Cite this

@article{a84e55c74c264e24aac0e80530569aed,

title = "Grammar semantics, analysis and parsing by abstract interpretation",

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.",

keywords = "Abstract interpretation, Abstract semantics, Bottom-up semantics, Context-free grammar, Grammar flow analysis, Grammar problem, Parsing, Top-down semantics",

author = "Patrick Cousot and Radhia Cousot",

year = "2011",

month = oct,

day = "14",

doi = "10.1016/j.tcs.2011.06.005",

language = "English (US)",

volume = "412",

pages = "6135--6192",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier B.V.",

number = "44",

}

TY - JOUR

T1 - Grammar semantics, analysis and parsing by abstract interpretation

AU - Cousot, Patrick

AU - Cousot, Radhia

PY - 2011/10/14

Y1 - 2011/10/14

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

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

KW - Abstract interpretation

KW - Abstract semantics

KW - Bottom-up semantics

KW - Context-free grammar

KW - Grammar flow analysis

KW - Grammar problem

KW - Parsing

KW - Top-down semantics

UR - http://www.scopus.com/inward/record.url?scp=84859465330&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84859465330&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2011.06.005

DO - 10.1016/j.tcs.2011.06.005

M3 - Article

AN - SCOPUS:84859465330

SN - 0304-3975

VL - 412

SP - 6135

EP - 6192

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 44

ER -

Grammar semantics, analysis and parsing by abstract interpretation

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this