An all(1) compiler generator

ABSTRACT

Aparse is a flexible and modular system for generating efficient one-pass compilers from attributed grammar specifications. The system is of particular interest in that it combines recent research in attributed parsing and error-correction into a powerful and practical tool. It has been amply demonstrated that attributed grammars are a convenient mechanism for organizing translations ([Fan 72], [LRS 74], [Bra 76]). This is partially due to the fact that an attributed grammar is not a completely formal specification tool—it merely provides a framework for structuring a semantic and syntactic specification. A number of compiler-compilers have been written to process attributed grammars ([LB 74], [BW 78], [GRW 77]), but Aparse is unique in incorporating attribute values in the parsing function. We have found that this facility permits smaller grammars to be used, and smaller parsers to be generated. In addition, a significant degree of context-sensitivity can be reflected in what is essentially a context-free framework. Section 2 will contain a brief introduction to attributed grammars, and section 3 will sketch the theory of attributed parsing.

REFERENCES

• 1: A. V. Aho , S. C. Johnson , J. D. Ullman, Deterministic parsing of ambiguous grammars, Communications of the ACM, v.18 n.8, p.441-452, Aug. 1975 [doi>10.1145/360933.360969]
• 2: Paul Branquart, Optimized Translation Process and Its Application to ALGOL 68, Springer-Verlag New York, Inc., Secaucus, NJ, 1976
• 3: G. V. Bochmann and P. Ward. "Compiler Writing System for Attribute Grammars," The Computer Journal, Vol. 21, No. 2, pp. 144-148 (1978).
• 4: C.C.I.T.T. Study Group XI. High Level Language Team of Specialists. "Proposal for a Recommendation for a C.C.I.T.T. High Level Programming Language," Blue document (May 1977).
• 5: I. Fang. "FOLDS, a Declarative Formal Language Definition System," Technical Report STAN-72-329, Stanford University (1972).
• 6: C. N. Fischer , D. R. Milton , S. B. Quiring, An efficient insertion-only error-corrector for LL(1) parsers, Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.97-103, January 17-19, 1977, Los Angeles, California [doi>10.1145/512950.512960]
• 7: H. Ganzinger, K. Ripken, and R. Wilhelm. "Automatic Generation of Optimizing Multipass Compilers," IFIP 77, pp. 535-540 (1977).
• 8: Susan L. Graham , Steven P. Rhodes, Practical syntactic error recovery, Communications of the ACM, v.18 n.11, p.639-650, Nov. 1975 [doi>10.1145/361219.361223]
• 9: S. C. Johnson. "Yacc—Yet Another Compiler-Compiler," Comp. Sci. Tech. Rep. No. 32, Bell Laboratories (July 1975).
• 10: S. C. Johnson and M. E. Lesk. "UNIXTM Time-Sharing System: Language Development Tools," Bell System Technical Journal, Vol. 57, No. 6, Part 2, pp. 155-2176 (1978).
• 11: D. E. Knuth. "Semantics of Context-Free Languages," Mathematical Systems Theory, Vol. 2, pp. 127-145 (1968). Correction appears in Mathematical Systems Theory, Vol. 5, p. 95 (1971).
• 12: B. W. Kernighan , D. M. Ritchie, The C programming language, Prentice-Hall, Inc., Upper Saddle River, NJ, 1978
• 13: O. LeCarme and G. V. Bochmann. "A (Truly) Usable and Portable Compiler Writing System," Information Processing 74, North-Holland Publishing Company (1974).
• 14: P. M. Lewis, D. J. Rosenkrantz, and R. E. Stearns. "Attributed Translations," Journal of Computer and Systems Sciences Vol. 9, pp. 279-304 (1974).
• 15: Donn Robert Milton, Syntactic specification and analysis with attributed grammars., 1977
• 16: Thomas J. Pennello , Frank DeRemer, A forward move algorithm for LR error recovery, Proceedings of the 5th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.241-254, January 23-25, 1978, Tucson, Arizona [doi>10.1145/512760.512786]
• 17: Bruce Ramon Rowland, Combining parsing and evaluation for attributed grammars., 1977

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Translator writing systems and compiler generators

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging
          Subjects: Error handling and recovery

  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.2 Grammars and Other Rewriting Systems
          Subjects: Parsing

General Terms:
Theory, Verification