Mark van den Brand
Eelco Visser
Abstract
Good documentation is important for the production of reusable and maintainable software. For the production of accurate documentation it is necessary that the original program text is not copied manually to obtain a typeset version. Apart from being tedious, this will invariably introduce errors. The production of tools that support the production of legible and accurate documentation is a software engineering challenge in itself. We present an algebraic approach to the generation of tools that produce typographically effective presentations of computer programs. A specification of a formatter is generated from the context-free grammar of a (programming) language. These generated formatters translate abstract syntax trees of programs into box expressions. Box expressions are translated by language-independent interpreters of the box language into ASCII or TEX. The formatting rules that are generated can easily be tuned in order to get the desired formatting of programs. We demonstrate this by means of real-life applications. Furthermore, we give a practical solution for the problem of formatting comments, which occur in the original text. The formatter generation approach proposed in this article can be used to generate formatting programs for arbitrary programming environments. Our formatter generation approach can be used to automatically generate formatters that have to be programmed explicitly in other systems.
- BAHLKE, R. AND SNELTING, G. 1986. Context-sensitive editing with PSG environments. In Proceedings of the International Workshop on Advanced Programming Environments, R. Conradi, T. Didriksen, and D. Wanvik, Eds. Lecture Notes in Computer Science, vol. 244. Springer-Verlag, Berlin, 26-38. Google Scholar
- BERGSTRA, J. A. AND KLINT, P. 1995. The discrete time ToolBus. Tech. Rep. P9502, Programming Research Group, Univ. of Amsterdam, Netherlands. Available as ftp://ftp.fwi.uva.nY pub/programming-research/reports/1995/P9502.ps.Z.Google Scholar
- BERGSTRA, J.A., HEERING, J., AND KLINT, P. 1989. The algebraic specification formalism ASF. In Algebraic Specification, J. A. Bergstra, J. Heering, and P. Klint, Eds. Addison- Wesley, Reading, Mass., 1-66.Google Scholar
- BLASCHEK, G. AND SAMETINGER, J. 1989. User-adaptable prettyprinting. Softw. Pract. Exp. 19, 7,687-702. Google Scholar
- BORRAS, P. 1989. PPML-Reference Manual and Compiler Implementation. INRIA, Sophia- Antipolis, France.Google Scholar
- BORRAS, P., CLEMENT, D., OESPEYROUX, T., INCERPI, J., LANG, B., AND PASCUAL, V. 1989. CENTAUR: The system. In Proceedings of the ACM SIGSOFT/SIGPLAN Software Engineering Symposium on Practical Software Development Environments. SIGPLAN Not. 14, 2, 14-24. Google Scholar
- BaUNEKREEF, J.J. 1995a. On modular algebraic protocol specification. Ph.D. thesis, Univ. of Amsterdam, Netherlands.Google Scholar
- BRUNEKREEF, J.J. 1995b. TransLog, an interactive tool for transformation of logic programs. Tech. Rep. P9512, Programming Research Group, Univ. of Amsterdam, Netherlands. Available as ftp://ftp.fwi.uva.nYpub/programming-research/reports/1995fP9512.ps.Z.Google Scholar
- CORDY, J. R., ELIOT, N. L., AND ROBERTSON, M.G. 1990. Turingtool: A user interface to aid in the software maintenance task. IEEE Trans. Softw. Eng. 16, 3, 294-301. Google Scholar
- GARLAN, D. 1985. Flexible unparsing in a structure editing environment. Tech. Rep. CMU- CS-85-129, Carnegie-Mellon Univ., Pittsburgh, Pa.Google Scholar
- HASCOET, L. 1992. FIGUE An Incremental Graphic Formatter User's Manual for Version 1. INRIA, Sophia-Antipolis, France.Google Scholar
- HECKMANN, R. AND WILHELM, R. 1995. Formula layout. Tech. Rep. A 07/95, FB 14 Informatik, Universitiit des Saarlandes, Saarbrticken, Germany.Google Scholar
- HEERING, J., HENDRIKS, P. R. H., KLINT, P., AND REKERS, J. 1992. The Syntax Definition Formalism SDF-Reference Manual. Version 6. CWI, Amsterdam, Netherlands. Available as ftp://ftp.cwi.nYpub/gipe/reports/SDFManual.ps.Z. Dec. Earlier version appeared in SIG- PLAN Not. 24, 11 (1989), 43-75. Google Scholar
- HILLEBRAND, J.A. 1996. A small language for the specification of grid protocols. Tech. Rep., Programming Research Group, Univ. of Amsterdam, Netherlands. To appear.Google Scholar
- JOHNSSON, T. 1986. Target code generation from G-machine code. In Graph Reduction, J. F. Fasel and R. M. Keller, Eds. Lecture Notes in Computer Science, vol. 279. Springer-Verlag, Berlin, 119-159. Google Scholar
- JOKINEN, M.O. 1989. A Language-independent prettyprinter. Soflw. Pract. Exp. 19, 9, 839-856. Google Scholar
- KAMPERMAN, J. F.T. 1994. GEL, a graph exchange language. Tech. Rep. CS-R9440, CWI, Amsterdam, Netherlands. Available as ftp://ftp.cwi.nl/pub/gipe/reports/Kam94.ps.Z. Google Scholar
- KAMPERMAN, J. F. T. AND WALTERS, H.R. 1993. ARM, abstract rewriting machine. Tech. Rep. CS-9330, CWI, Amsterdam, Netherlands. Available as ftp://ftp.cwi.nl/pub/gipe/reports/ KW93.ps.Z. Google Scholar
- KERNIGHAN, B. W. AND RITCHIE, D.M. 1978. The C Programming Language. Prentice-Hall, Englewood Cliffs, N.J. Google Scholar
- KLtNT, P. 1993. A meta-environment for generating programming environments. ACM Trans. Softw. Eng. Meth. 2, 2, 176-201. Google Scholar
- KLINT, P. 1994. Writing meta-level specifications in ASF,-SDF. CWI, Amsterdam, Netherlands.Google Scholar
- KLINT, P. 1995. The ASF~SDF meta-environment--user's guide. CWl, Amsterdam, Netherlands. Available as ftp://ftp.cwi.nl/pub/gipe/reports/SysManual.ps.Z.Google Scholar
- KNUTH, D.E. 1984. The TEXbook. Vol. A, Computers and Typesetting. Addison-Wesley, Reading, Mass. (Ninth printing, revised, October 1989i. Google Scholar
- KOORN, J. W.C. 1994. Generating uniform user-interfaces for interactive programming environments. Ph.D. thesis, ILLC dissertation series 1994-2, Univ. of Amsterdam, Netherlands.Google Scholar
- LESK, .M. E. AND SCHMIDT, E. 1986. LEX--A lexical analyzer generator. UNIX Programmer's Supplementary Documents, volume 1 (PS1). Bell Laboratories, Murray Hill, N.J.Google Scholar
- MAGNUSSON, B., BENGTSSON, M., DAHLIN, L.-O., FRIES, G., GUSTAVSSON, A., HEDIN, G., MINOR, S., OSCARSSON, D., AND TAUBE, U. 1990. An Overview of the Mjolner/ORM Environment: Incremental language and software development. In Proceedings of TOOLS '90. Prentice- Hall, Englewood Cliffs, N.J., 635-646.Google Scholar
- MAuW, S. AND VELTINK, G.J. 1990. A process specification formalism. Fundamenta lnformaticae 12, 85-139. Google Scholar
- MEYER, B. 1992. Eiffel: The Language. Prentice-Hall, Englewood Cliffs, N.J. Google Scholar
- MINOR, S. 1990. On structure-oriented editing. Ph.D. thesis, Lund Univ., Lund, Sweden.Google Scholar
- MORCOS-CHOUNET, E. AND CONCH()N, A. 1986. PPML: A general formalism to specify prettyprinting. In Information Processing 86, H.-J. Kugler, Ed. Elsevier, Amsterdam, 583-590.Google Scholar
- OPPEN, D.C. 1980. Prettyprinting. ACM Trans. Program. Lang. Syst. 2, 4, 465-483. Google Scholar
- PLASMEIJER, M. J. AND VAN EEKELEN, M. C. J.D. 1993. Functional Programming and Parallel Graph Rewriting. Addison-Wesley, Reading, Mass. Google Scholar
- REPS, T. AND TEITELRAUM, T. 1989. The Synthesizer Generator: A System for Constructing Language-Based Editors. Springer-Verlag, Berlin. Google Scholar
- RES, M. 1994. A generated programming environment for RISLA, a specification language for defining financial products. M.S. thesis, Programming Research Group, Univ. of Amsterdam, Netherlands.Google Scholar
- ROSE, G. A. AND WELSH, J. 1981. Formatted Programming Languages. Softu,. Pratt. Exp. 11, 651-669.Google Scholar
- SICS. 1992. SICStus Prolog User's Manual. Swedish Institute of Computer Science, Kista, Sweden.Google Scholar
- STERN, N. AND STERN, R. 1988. Structured COBOL Programming. Wiley, New York. Google Scholar
- VAN DEN BRAND, M. G.J. 1992. Pregmatic, a generator for incremental programming environments. Ph.D. thesis, Katholieke Universiteit Nijmegen, Netherlands.Google Scholar
- VAN DEN BRANt), M. G. J., EIJKELKAMP, S. M., GELUK, D. K. A., MEIJER, H., OSBORNE, H. R., AN{) POLLING, M. J.F. 1995. Program transformations using ASF+ SDF. in ASF-~SDF '95: A Workshop on Generating Tools from Algebraic Specifications, M. G. J. van den Brand, A. van Deursen, T. B. Dinesh, J. F. T. Kamperman, and E. Visser, Eds. Programming Research Group, Univ. of Amsterdam, Netherlands, 29-52. Also Tech. Rep. P9504, Programming Research Gr~)up. Univ. of Amsterdam. Available as http://www.fwi.uva.nl/research/prog/report~.Google Scholar
- VAN DEN BRAND, M. G. J. AN1) VISSER, E. 1994. From Box to TEX: An algebraic approach to the construction of documentation tools. Tech. Rep. P9420, Programming Research Group, Univ. of Amsterdam, Netherlands. Available as ftp://ftp.fwi.uva.nl/pub/ programming-research/reports/1994/P9420.ps.Z.Google Scholar
- Vos, K.J. 1990. Pretty for an easy touch of beauty. M.S. thesis, Programming Research Group, Univ. of Amsterdam, Netherlands.Google Scholar
- WALTERS, H.R. 1991. On equal terms, implementing algebraic specifications. Ph.D. thesis, Univ. of Amsterdam, Netherlands. Available as ftp://ftp.cwi.nl:/pub/gipe/reportsfWal91.ps.Z.Google Scholar
- WEt,,~H, ,l., BROOM, B., AND KIONG, D. 1991. A design rationale for a language-based editor. Softl~,. Pratt. Exp. 21, 9, 923-948. Google Scholar
- WIJN(;AARDEN, A., MAILLOUX, B., PECK, J., KOSTER, C., SINTZOFF, M., LINDSEY, C., MEERTENS, L., ANI) FI.~K~R, R. 1976. Revised Report on the Algorithmic Language Algol 68. Springer- Verlag, Berlin.Google Scholar
Index Terms
- Generation of formatters for context-free languages
Recommendations
Developing a lisp-based preprocessor for TEX documents
TEX allows users to define a macro that abstracts a sequence of typesetting commands. However, defining macros is not easy for most users, because the mechanism of macro expansion in TEX is complicated. As a remedy for this situation, a new system that ...
LFG generation produces context-free languages
COLING '00: Proceedings of the 18th conference on Computational linguistics - Volume 1This paper examines the generation problem for a certain linguistically relevant subclass of LFG grammars. Our main result is that the set of strings that such a grammar relates to a particular f-structure is a context-free language. This result ...
Reviews
Heather Brown
The authors have developed grammar-based methods to automate the process of creating formatters (pretty printers) for context-free programming languages. This substantial paper describes the methods in detail and explains how they have been used to create formatters for several different languages. The work has been undertaken in the context of programming environments generated by the ASF+SDF meta-environment [1]. The overall system developed for creating and using formatters works in the following three main stages. First, a formatter generator uses the context-free grammar of a particular language to produce a formatter for that language. The resulting formatter requires access to the abstract syntax trees of programs, so it is closely integrated with the overall programming environment. Second, the generated formatter uses the abstract syntax tree of a program to produce a box language description of the required output. This consists of boxes of text together with information on their relative horizontal and vertical alignment, and operators that control the appearance of the text according to the information represented (variable, comment, keyword, and so on). Finally, a back-end is used to translate the box language description into the required output form. Back-ends currently exist for ASCII and \TeX output, and a back-end for HTML is being developed. The paper begins with an overview of the methods developed, then goes on to discuss the first two stages of the process in detail. Sections 2 and 3 explain the problems of unparsing (recreating the source program from the abstract syntax tree), with particular reference to the issues of the priority and associativity of operators. Section 4 describes the box language used. Section 5 discusses the difficulties of retaining and positioning source program comments. Sections 6 and 7 give full details of the process of generating and fine-tuning a formatter, and discuss the implementation within the overall ASF+SDF meta-environment. Finally, s ection 8 compares the methods used with related work. The paper explains many of the issues clearly and gives useful examples (though it is difficult to follow in places if you are not familiar with ASF+SDF).
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments