Grammar semantics, analysis and parsing by abstract interpretation
type: Item
instance of: scholarly article
title: Grammar semantics, analysis and parsing by abstract interpretation
zbMATH Open document ID: 1248.68316
author: Patrick Cousot
author: Radhia Cousot
published in: Theoretical Computer Science
publication date: 2012-01-04T00:00:00Z
review text: Grammar flow problems consist in computing a function of the proto language generated by the grammar for each nonterminal. In the paper under review, abstract interpretations of a fixpoint protoderivation semantics are studied, 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 problems, classical grammar flow analysis algorithms and parsing algorithms. The paper is absolutely self-contained, providing also the mathematical background and the necessary elements of abstract interpretation.
reviewed by: Anna Labella
Mathematics Subject Classification ID: 68Q55
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 68Q42
zbMATH DE Number: 5994293
zbMATH Keywords: abstract interpretation
zbMATH Keywords: context-free grammar
zbMATH Keywords: bottom-up semantics
zbMATH Keywords: top-down semantics
zbMATH Keywords: abstract semantics
zbMATH Keywords: grammar flow analysis
zbMATH Keywords: grammar problem
describes a project that uses: ALGOL 60
MaRDI profile type: Publication
full work available at URL: j.tcs.2011.06.005
OpenAlex ID: W2073050028
cites work: A generalization of Dijkstra's algorithm
cites work: An Incremental Algorithm for a Generalization of the Shortest-Path Problem
cites work: Q3292904
cites work: Q3315030
cites work: Compiler construction. Theory, design, generation
cites work: Three models for the description of language
cites work: Automatische Rechenplanfertigung bei programmgesteuerten Rechenmaschinen
cites work: Q3270836
cites work: Q2778917
cites work: Q5593685
cites work: On context-free languages and push-down automata
cites work: Q4662826
cites work: Q4385528
cites work: Q5576254
cites work: Constructive design of a hierarchy of semantics of a transition system by abstract interpretation
cites work: Q3922128
cites work: ``A la Burstall'' intermittent assertions induction principles for proving inevitability properties of programs
cites work: Constructive versions of Tarski's fixed point theorems
cites work: Two Families of Languages Related to ALGOL
cites work: On a Theorem of R. Jungen
cites work: Q5526125
cites work: A note on two problems in connexion with graphs
cites work: Q5552540
cites work: Recognition and parsing of context-free languages in time n3
cites work: Q5574395
cites work: Formal certification of a compiler back-end or
cites work: Programming Languages and Systems
cites work: Q4934630
cites work: Abstract interpretation of resolution-based semantics
cites work: Marcus contextual grammars
cites work: Q4714446
cites work: From Contextual Grammars to Range Concatenation Grammars
cites work: Q4530231
DOI: 10.1016/J.TCS.2011.06.005
description: scientific article; zbMATH DE number 5994293