P. Cousot and R. Cousot, Grammar semantics, analysis and parsing by abstract interpretation

Patrick Cousot and Radhia Cousot.
Grammar semantics, analysis and parsing by abstract interpretation.
In Theoretical Computer Science 412(44): 6135-6192 (2011).
PDF (1.1 Mb)
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 problems, classical grammar flow analysis algorithms, and parsing algorithms.
Keywords: Abstract interpretation, Context-free grammar, Bottom-up semantics, Top-down semantics, Abstract semantics, Grammar flow analysis, Grammar problem, Parsing.

\bibitem{CousotCousot-TCS-2011}
P.~Cousot and R. Cousot.
\newblockGrammar semantics, analysis and parsing by abstract interpretation.
\newblock Theor. Comput. Sci. 412(44): 6135-6192 (2011).

@article{CousotCousot-TCS-2011,
  author    = {P.~Cousot and R~Cousot},
  title     = {Grammar semantics, analysis and parsing by abstract interpretation},
  journal   = {Theor. Comput. Sci.},
  volume    = {412},
  number    = {44},
  year      = {2011},
  pages     = {6135-6192},
  doi       = {http://dx.doi.org/10.1016/j.tcs.2011.06.005},
}

copyright notice

Last modified : Friday, 04-May-2012 10:01:26 EDT