Obtaining a grammar from a less formal language description

In this paper, we will try to show how CF-grammars can be constructed to describe sets of strings;* each string being of a type which is commonly found in programming languages. We will require that these grammars not only describe the syntax of such sets of strings, but also more importantly, reflect unambiguously in the derivation of these strings, the ordering or sequencing conventions commonly imposed on such strings. We will show how these grammars can be used to formally describe, at least in part, two aspects of programming language-operations operations. We will also be concerned with the case in which the grammars can be used to determine this ordering. The grammars we develop will be one of a number of possible grammars, each different in non-superficial ways, and each adequate to express the class of languages we will discuss. A large part of the material presented here is tutorial. The material on constructing a grammar to satisfy a set of precedence relations constitutes the main contribution reported here. We start by considering a non-CFG way of describing ordering conventions in an algebraic expression involving a number of appearances of a group of binary infix operations. This technique - precedence - has immediate appeal because of its familiarity as much, perhaps, because of its simplicity. After discussing precedence in some detail, we will show how some of the same effects can be-obtained with CFG's. Precedence is a common device for describing the order in which operations are to be performed in expressions of the form: a + b * c ** b + c * e...Technical report DCS-TR-