Formal language, grammar and set-constraint-based program analysis by abstract interpretation

Grammar-based programs analyses are static analysis techniques that have traditionally been seen as quite different from abstract-interpretation-based analyses, due to their apparent non-iterative nature. There are decidable kinds of analysis that cannot be computed using abstract interpretation (even with widening and narrowing). An example of this is the set-based analysis considered in this work. It is shown that grammar and set-constraint-based program analyses are similar abstract interpretations with iterative fixpoint computation using either a widening or a finitary grammar/set-constraints transformer or even a finite domain for each particular program.