Inferring Grammatical Summaries of String Values

We present a new kind of static analysis that infers grammatical summaries of string values. We are given a context-free grammar and a program which contains string expressions whose values should be partial sentences of the grammar. A grammatical summary of an expression is a vocabulary string of the grammar that derives all the possible string values of the expression. Our analysis automatically finds out such grammatical summaries. We design the analysis using abstract interpretation framework making it pluggable into conventional data-flow analysis frameworks.