Canonical Precedence Schemes

ABSTRACT

A general theory of canonical precedence analysis is defined and studied. The familiar types of precedence analysis such as operator precedence or simple precedence occur as special cases of this theory. Among the theoretical results obtained are a characterization of the structure of precedence relations and the relation of canonical precedence schemes to operator sets.

REFERENCES

• 1: COLMERAUER, A. Precedence, analyse syntaxique et languages de prograrnmation. Th., U. of Grenoble, 1967.
• 2: Jerome Feldman , David Gries, Translator writing systems, Communications of the ACM, v.11 n.2, p.77-113, Feb. 1968 [doi>10.1145/362896.362902]
• 3: Michael J. Fischer, Some properties of precedence languages, Proceedings of the first annual ACM symposium on Theory of computing, p.181-190, May 05-07, 1969, Marina del Rey, California, United States [doi>10.1145/800169.805432]
• 4: Robert W. Floyd, Syntactic Analysis and Operator Precedence, Journal of the ACM (JACM), v.10 n.3, p.316-333, July 1963 [doi>10.1145/321172.321179]
• 5: Robert W. Floyd, Bounded context syntactic analysis, Communications of the ACM, v.7 n.2, p.62-67, Feb. 1964 [doi>10.1145/363921.363927]
• 6: Seymour Ginsburg, The Mathematical Theory of Context-Free Languages, McGraw-Hill, Inc., New York, NY, 1966
• 7: Seymour Ginsburg , Michael A. Harrison, One-way nondeterministic real-time list-storage languages, Journal of the ACM (JACM), v.15 n.3, p.428-446, July 1968 [doi>10.1145/321466.321475]
• 8: GRAI~AM, S.L. Extended precedence languages, bounded right context languages and deterministic languages. Proc. IEEE llth Annum Symp. on Switching and Automata Theory, Oct. 1970, pp. 175-180.
• 9: GRAY, J.N. Precedence parsers for programming languages. Ph.D. Th., Dep. of Computer Sci., U. of California, Berkeley, Calif., Sept. 1969.
• 10: James N. Gray , Michael A. Harrison, On the Covering and Reduction Problems for Context-Free Grammars, Journal of the ACM (JACM), v.19 n.4, p.675-698, Oct. 1972 [doi>10.1145/321724.321732]
• 11: Sheila A. Greibach, A New Normal-Form Theorem for Context-Free Phrase Structure Grammars, Journal of the ACM (JACM), v.12 n.1, p.42-52, Jan. 1965 [doi>10.1145/321250.321254]
• 12: John E. Hopcroft , Jeffrey D. Ullman, Formal languages and their relation to automata, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1969
• 13: KNUTH, D. E. On the translation of languages from left to right. Inform. and Contr. 8, (1965), 607-639.
• 14: MCKEEMAN, W.M. An approach to computer language design. Tech. Rep. CS48, Cornput. Sci. Dep., Stanford U., Stanford, Calif., 1966.
• 15: PAIR, C. Arbres, piles et compilation. Revue Franfalse de Tra~tement de l'Informatio~ 7, 3 0964), 199-216.
• 16: Niklaus Wirth , Helmut Weber, EULER: a generalization of ALGOL, and its formal definition: Part II, Communications of the ACM, v.9 n.2, p.89-99, Feb. 1966 [doi>10.1145/365170.365202]

INDEX TERMS

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

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

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