Prettyprinting

ABSTRACT

An algorithm for prettyprinting is given. For an input stream of length n and an output device with linewidth m, the algorithm requires time O(n) and space O(m). The algorithm is described in terms of two parallel processes: the first scans the input stream to determine the space required to print logical blocks of tokens; the second uses this information to decide where to break lines of text; the two processes communicate by means of a buffer of size O(m). The algorithm does not wait for the entire stream to be input, but begins printing as soon as it has received a full line of input. The algorithm is easily implemented.

REFERENCES

• 1: Charles M. Geschke , James H. Morris, Jr. , Edwin H. Satterthwaite, Early experience with Mesa, Communications of the ACM, v.20 n.8, p.540-553, Aug. 1977 [doi>10.1145/359763.359771]
• 2: GOLDSTEIN, I. Pretty-printing, converting list to linear structure. Artificial Intelligence Laboratory Memo. No. 279, M.I.T., Cambridge, Mass., 1973.
• 3: HEARN, A.C., ANO NORMAN, A.C. A one-pass prettyprinter. Rep. UUCS-79-112, University of Utah, Salt Lake City, Utah, 1979.
• 4: KNUTH, D.E. Tan el~silon chi--A system for technical text. Rep. STAN-CS-78-675, Computer Science Dep., Stanford Univ., Stanford, Calif., 1978.
• 5: Kenneth Conrow , Ronald G. Smith, NEATER2: a PL/I source statement reformatter, Communications of the ACM, v.13 n.11, p.669-675, Nov 1970 [doi>10.1145/362790.362796]
• 6: DONZEAU-GOUGE, V., HUET, G., KAHN, G., LANG, R., AND LEVY, J.J. A structure-oriented program editor; A first step towards computer assisted programming. Proc. Inter. Computing Syrup., Antibes, 1975.
• 7: GORDON, H. Paragraphing computer programs. M.Sc. Thesis, Univ. of Toronto, Toronto, Ontario, Canada, 1975.
• 8: Jon Hueras , Henry Ledgard, An automatic formatting program for PASCAL, ACM SIGPLAN Notices, v.12 n.7, p.82-84, July 1977 [doi>10.1145/954639.954645]
• 9: HUET, G., KAHN, G., AND LANe, B. The MENTOR Program Manipulation System. Unpublished manuscript, 1978.
• 10: JoY, W. Berkeley Pascal PXP implementation notes. Manuscript, Dep. of Electrical Engineering and Computer Science, Univ. of California, Berkeley, Calif., 1979.
• 11: KNVTH, D.E. BLAISE--A TEX preprocessor for Pascal. To appear.
• 12: W. M. McKeeman, Algorithm 268: ALGOL 60 reference language editor [R2], Communications of the ACM, v.8 n.11, p.667-668, Nov. 1965 [doi>10.1145/365660.365673]
• 13: Patricia R. Mohilner, Prettyprinting PASCAL programs, ACM SIGPLAN Notices, v.13 n.7, p.34-40, July 1978 [doi>10.1145/953863.953869]
• 14: James L. Peterson, On the formatting of Pascal programs, ACM SIGPLAN Notices, v.12 n.12, p.83-86, December 1977 [doi>10.1145/954618.954624]
• 15: SCOWEN, R., ALLIN, D., HILLMAN, A., AND SHINELL, M. SOAP--A program which documents and edits Algol60 programs. Comput. J. 14, 2 (1971), 133-135.
• 16: Tim Teitelbaum, The Cornell Program Synthesizer: A Microcomputer Implementation of PL/CS, Cornell University, Ithaca, NY, 1979

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.3 Coding Tools and Techniques
          Subjects: Pretty printers

General Terms:
Design, Languages, Performance, Theory