[madPL] Synthesis / SemGuS Reading Group: Grammar Flow Analysis

[Keith Jens Carl Johnson <keith.johnson@xxxxxxxx>]

Hello everyone,

 

The Synthesis / SemGuS Reading Group returns this week, Thursday (7/29) at 1pm on Zoom:

https://uwmadison.zoom.us/j/96450343227?pwd=emtGcHROSVZoOWsyWEFhN2wyazA2Zz09

 

This week, I’ll be presenting on Grammar Flow Analysis (Möncke, Wilhelm 1991), followed by a discussion about its applicability to solving synthesis problems.

 

Abstract:

“

This paper specifies the theoretical basis for the implementation of different generators of the OPTRAN system. Grammar Flow Analysis uses the techniques of data flow analysis at the meta level of compiler construction. The analogue of the states in data flow analysis are the syntax trees together with some information that is associated with trees by propagation functions. One example is the association of characteristic graphs, another example is the association of sets of matching tree patterns.

“

 

“Homework” question:

Generally speaking, grammar flow analysis allows proving properties about non-terminals in a grammar. Traditional examples of this include the first and follow sets in parsing. What properties about non-terminals might be useful to know during program synthesis?

 

 

-Keith