Prettyprinting

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.