Automated Construction of Input and Output Grammars

We describe a technique for constructing the input and output grammar of a module. The grammar can be expressed in many ways, we choose BNF, because the notation is widely known from the theory of programming languages. The program's basic types and names of functions called serve as the alphabet of the grammar, and the production rules represent the possible forms that the input and output may take, when the program is executed. We construct a separate grammar to describe the input and the output of the program, but also discuss briefly the potential for combining the two in a single grammar which captures the interleaving of the input and output. We construct the grammar using a function which takes a set of program statements and returns a set of BNF production rules. We use a subset of C, including basic constructs (selection, sequencing and iteration) functions and procedures, to illustrate our approach. 1 Introduction A type is a classification of some group of objects. In many ..