Grammar semantics, analysis and parsing by abstract interpretation

作者：Cousot Patrick^*; Cousot Radhia

来源：Theoretical Computer Science, 2011, 412(44): 6135-6192.

DOI：10.1016/j.tcs.2011.06.005

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

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.

• 出版日期2011-10-14
• 单位INRIA