A New Language - Independent Prettyprinting Algorithm

An algorithm for prettyprinting using word wrapping is described that is independent of the language being formatted and is substantially simpler than other published algorithms. The algorithm makes use of a simple model with a small set of primitives to direct the prettyprinting of text. For an input string of length $n$, and an output device $m$ characters wide the algorithm runs in $O(n)$ time and requires $O(m)$ space. The algorithm can be restarted from an intermediate point and is therefore well suited for incremental prettyprinting of text. This algorithm is now being used in the Cornell Synthesizer Generator [2]. The algorithm is compared with and contrasted to the previously published algorithm by Oppen [1]