P. Cousot & R. Cousot, Grammar Abstract Interpretation

Patrick Cousot & Radhia Cousot.
Grammar Abstract Interpretation.
Seminar in Honor of Reinhard Wilhelm's 60th Birthday, Dagstuhl Seminar 6232, Dagstuhl, Wadern, Germany, June 9—10, 2006.
Abstract:
We introduce a stack-based small-step operational semantics of context-free/algebraic grammars (inspired by push-down automata) from which we derive, by abstract interpretation, a hierarchy of bottom-up fixpoint abstract semantics for derivations (maximal execution traces of the grammar transition system), derivation trees, syntax trees, protolanguages and terminal languages as well as a hierarchy of top-down fixpoint abstract semantics for protoderivations, protoderivation tree, protosyntax trees and protolanguages, all with rewrite variables. We show that the top-down semantics can be abstracted to the bottom-up semantics by elimination of the variables. The bottom-up and top-down protolanguage semantics are equivalent but different fixpoint characterizations of the protolanguage generated by the grammar.
The calculational design of the classical bottom-up grammar flow analysis iterative algorithms such as nonterminal productivity, nonterminal emptyness and FIRST is by sound and complete abstraction of the bottom-up semantics. Similarly, the calculational design of the classical top-down grammar flow analysis iterative algorithms such as nonterminal accessibility and FOLLOW is by sound and complete abstraction of the top-down semantics.
Non/deterministic top-down and bottom-up parsing algorithms can also be formally derived from the grammar semantics. This is examplified with top-down nonrecursive predictive parsing (including LL(0) and LL(1)) and CYK (Cocke-Younger-Kasami) bottom-up parser.
Keywords:
Abstract Interpretation, Grammar, Context-free grammar, Algebraic grammar, Grammar flow analysis, Parser, Parsing, LL(k), LR(k), CYK, Earley.
Slides of the 45 mn presentation: The color transparencies are available as 1 slide per lanscape page for projection (1/1), 2 slides per portrait page for reading (2/1) and 4 slides per lanscape page for printing (4/1), in:
- PostScript: 1/1 .ps.gz, 2/1 .ps.gz, 4/1 .ps.gz for viewing with GhostScript and GhostView or (color) printing;
- PDF: 1/1 .pdf, 2/1 .pdf, 4/1 .pdf to be used with Acrobat Reader.

Bibliographic reference:

\bibitem{CousotCousot-RWseminar-10-06-06}
P.~Cousot \& R.~Cousot.
\newblock Grammar Abstract Interpretation.
\newblock \emph{Seminar in Honor of Reinhard Wilhelm's 60th Birthday}, 
         Dagstuhl Seminar 6232, Dagstuhl, Wadern, Germany, June 9--10, 2006.

@conference{CousotCousot-RWseminar-10-06-06,
   author =    {P{.} Cousot and R{.} Cousot},
   title =     {Grammar Abstract Interpretation},
   note    =   {\emph{Seminar in Honor of Reinhard Wilhelm's 60th Birthday}, 
                Dagstuhl Seminar 6232, Dagstuhl, Wadern, Germany},
   month =     {June 9--10},
   year =      2006,
}

copyright notice
Last modified: Monday, 04-Jan-2010 14:02:46 CET