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.

REFERENCES

• 1: CHOMSKY, N. Syntactic Structures. Mouton and Company, The Hague, 1957.
• 2: --. On certain formal properties of grammars. Inform. Contr. 2 (1959), 137-167.
• 3: BAR-HILLEL, Y., AND SHAMm, E. Finite-state languages: Formal representations and adequacy problems. Bull. Res. Council of Israel 8F, 3 (Feb. 1960).
• 4: --, PbES, M., AND SHAMm, E. On formal properties of simple phase struetm'e grammars. Z. Phonetik, Sprachwiss. Kommunilcationsforsch. 14, 2 (1961).
• 5: SmM, E. On sequential languages. Tech. Rep. No. 7, Appl. Logic Branch, ttebrew U. of Jerusalem, 1961.
• 6: Seymour Ginsburg , H. Gordon Rice, Two Families of Languages Related to ALGOL, Journal of the ACM (JACM), v.9 n.3, p.350-371, July 1962 [doi>10.1145/321127.321132]
• 7: Peter Naur , J. W. Backus , F. L. Bauer , J. Green , C. Katz , J. McCarthy , A. J. Perlis , H. Rutishauser , K. Samelson , B. Vauquois , J. H. Wegstein , A. van Wijngaarden , M. Woodger, Report on the algorithmic language ALGOL 60, Communications of the ACM, v.3 n.5, p.299-314, May 1960 [doi>10.1145/367236.367262]
• 8: Edgar T. Irons, A syntax directed compiler for ALGOL 60, Communications of the ACM, v.4 n.1, p.51-55, Jan. 1961 [doi>10.1145/366062.366083]
• 9: David G. Cantor, On The Ambiguity Problem of Backus Systems, Journal of the ACM (JACM), v.9 n.4, p.477-479, Oct. 1962 [doi>10.1145/321138.321145]
• 10: Alfonso Caracciolo Di Forino, Some remarks on the syntax of symbolic programming languages, Communications of the ACM, v.6 n.8, p.456-460, Aug. 1963 [doi>10.1145/366707.367584]
• 11: DAWS. M, Computability and UnoIvabilit. MeGraw-Hill, New York 1958.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.1 Formal Definitions and Theory
          Subjects: Syntax

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES

General Terms:
Algorithms, Languages, Performance, Theory, Verification