On the Syntax of Algorithmic Languages

Abstract

The analytic grammar (a model which provides a rigorous description of syntactic analysis) is presented, and some of its fundamental properties are shown. Various submodels are discussed and equivalences among these are noted. An analytic grammar incorporates a set P of syntactic productions, and also a scan @@@@. At each successive “rewriting” in the analysis of a string x , @@@@ computes a subset of productions applicable to x (i.e., which may be used to “rewrite” x ) from the set of productions which are potentially applicable to x . Thus each scan determines a class of grammars. It is shown that all analytic languages are recursive, and conversely, all recursive sets are analytic languages. All phrase structure grammars are analytic grammars. A simple sufficient condition is shown under which an analytic grammar provides unique analyses for all strings. Particularly relevant to syntactic analysis of algorithmic languages (i.e., languages which are used to specify computing algorithms) are the “leftmost” scans, each of which chooses a certain “leftmost” production. Conditions which provide equivalences among these scans are noted.