building a language independent prettyprinter

Felix Gärtner^{1} 27. Februar 1995

1This report covers the very first version of Pretzel. Consult the Pretzelbook for the latest version of Pretzel documentation.

Abstract

This report is the main documentation to a project that the author worked on at the Technical University of Darmstadt in 1994. The goal of the project was to build a prettyprinter generator, i.e. a program that created a prettyprinter from a formal description of the way it should prettyprint given source code. The result was called “the Pretzel system”.

This text first gives an overview over the area of prettyprinting and presents the prettyprinting method used by the generated prettyprinter. It then describes how to use the Pretzel program to build a prettyprinter program or module of your choice. The remaining chapters deal with the literate programming paradigm, from which this program emerged, and an overview over the design of the system.

Contents

Introduction 3

1 On Prettyprinting 5

1.1 Prettyprinting with Format Commands . . . . . . . . . . . . . . . . 5 1.1.1 Controlling the Amount of Indentation . . . . . . . . . . . . . 6 1.1.2 Controlling Line-breaks . . . . . . . . . . . . . . . . . . . . . 7 1.1.3 Additional Commands . . . . . . . . . . . . . . . . . . . . . . 9 1.1.4 Summary of Format Commands . . . . . . . . . . . . . . . . 10 1.1.5 The Prettyprinting Grammar . . . . . . . . . . . . . . . . . . 11

1.2 A Short History of Prettyprinting . . . . . . . . . . . . . . . . . . . . 12 1.2.1 Historical Notes . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.2.2 The Language Dependent Front End . . . . . . . . . . . . . . 13 1.2.3 The Language Independent Back End . . . . . . . . . . . . . 14 1.2.4 The Set of Format Commands . . . . . . . . . . . . . . . . . 15 1.2.5 Open Prettyprinting Problems . . . . . . . . . . . . . . . . . 16

1.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

2 Using Pretzel 19

2.1 The Concept of Pretzel . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.1.1 The Input Files . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.1.2 The Generated Prettyprinting Functions . . . . . . . . . . . . 20

2.2 The Format of the Input Files . . . . . . . . . . . . . . . . . . . . . . 22 2.2.1 The Formatted Token File . . . . . . . . . . . . . . . . . . . . 22 2.2.2 The Formatted Grammar File . . . . . . . . . . . . . . . . . . 23 2.2.3 Comments and Code . . . . . . . . . . . . . . . . . . . . . . . 24

2.3 Making a Prettyprinter with Pretzel . . . . . . . . . . . . . . . . . . 25 2.3.1 Invoking Pretzel . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.3.2 An Example Pretzel Session . . . . . . . . . . . . . . . . . . . 25 2.3.3 Debugging the Prettyprinting Grammar . . . . . . . . . . . . 26 2.3.4 Advanced Topics . . . . . . . . . . . . . . . . . . . . . . . . . 27

2.4 Example (a Grammar for Pascal) . . . . . . . . . . . . . . . . . . . 27 2.4.1 The Formatted Token File . . . . . . . . . . . . . . . . . . . . 28 2.4.2 The Formatted Grammar File . . . . . . . . . . . . . . . . . . 29 2.4.3 Using the Generated Prettyprinter . . . . . . . . . . . . . . . 30

3 Literate Programming and Pretzel 33

3.1 On Literate Programming . . . . . . . . . . . . . . . . . . . . . . . . 33 3.1.1 The WEB system . . . . . . . . . . . . . . . . . . . . . . . . . . 34 3.1.2 The Literate Programming Paradigm and the Software Life

Cycle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

3.2 “Literate Software Management” . . . . . . . . . . . . . . . . . . . . 36 3.3 The Role of Pretzel . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 4 The Design of the System 38

4.1 The Attribute Grammar . . . . . . . . . . . . . . . . . . . . . . . . . 38 4.1.1 Attributes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 4.1.2 Outputting Attributes . . . . . . . . . . . . . . . . . . . . . . 39

4.2 The Structure of Pretzel . . . . . . . . . . . . . . . . . . . . . . . . . 40 4.3 History . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

5 Future Work 43

Acknowledgements 46

Appendix 47

Bibliography 84

Index 87

Introduction

“Any programmer who fails to comply with the standard naming, formatting or commenting conventions should be shot. If it so happens that it is inconvenient to shoot him, then he is to be politely requested to recode his program in adherence to the above standard.” [32]

Recently, when discussing an assignment in a course on software engineering, the lecturer addressed the auditorium and stressed the fact that he would reject any code that wasn’t properly indented. This was very striking for me since I have never considered proper indentation to be a major problem for any programmer. I always had assumed that everybody was already doing so. But I was wrong.

Luckily, insufficient program formatting in this course didn’t result in any executions as the above quote might suggest. But this note pointed to a problem that I have never been really aware of, possibly because I have actually learned to write programs in a to date non-standard way, i.e. using a WEB.

In common words a web is a fine net made by a spider to catch insects. Since 1984, ‘WEB’ is also known as another name for a literate program, a highly documented program designated for the eye of a reader and not solemnly for execution by a computer; WEBs are meant to be works of literature.

This is the basicly new idea of literate programming, a programming style first introduced by Donald E. Knuth in 1984 [28]. This concept is a new attempt to promote understandability and readability of a program’s source code. With this style, the programmer can be “regarded as an essayist, whose main concern is with exposition and excellence of style”. Instead of writing a program sufficing the rigid rules of a compiler, the programmer is free to choose the manner of presenting the ideas and algorithms of his program. This change of attitude lifts normal computer programs up to become WEBs.

To turn these ideas from theory to practice one needs special tools to bypass the restrictions imposed by normal compilers. One of these tools processes the WEB and turns it into a well formatted, high quality document (including proper indentation) that serves as a source code documentation. A system routine performing this task is usually referred to as a WEAVE processor. This processor weaves the web, i.e. it improves the appearance of the WEB. In most cases, WEAVEing is only the first step towards the final document: The second step normally consists of using a professional typesetter program to produce code for output devices such as high resolution graphic displays or laser printers.

Normally WEAVE not only enhances the readability of the informal text (i.e. commentary) in the WEB; it also improves the appearance of the formal text, i.e. the small parts of source code that are scattered all over the WEB. This work is commonly called prettyprinting. The prettyprinting of the source code is normally the most intricate part of every WEAVE program. This is due to the fact that the problem of prettyprinting is highly language dependent and that—being mostly a matter of personal taste—prettyprinting has to follow a lot of small details to make the output look nice. WEAVE systems normally have a built in prettyprinting algorithm designed by the program author that reflects mainly his opinion of how to space instructions of the underlying programming language.

This paper states that together with the literate program the way of prettyprinting should also be an input parameter to a WEAVE system. To enable this idea, the author has written a program called Pretzel that automatically generates a prettyprinter from a general description of the programming language to be prettyprinted. In this paper I will present this program and discuss several issues related with the topic of prettyprinting, as well as giving an overview of how this program may be used in future projects on literate programming.

This text follows a course that can be described as “from theory to practise”. It starts by giving a rather long and theoretical overview over the area of prettyprinting (chapter 1) and then turns to a more user orientated introduction to the Pretzel program (chapter 2, the Pretzel user’s manual). The end of the more abstract part (chapter 3) is devoted to the issue of literate programming and the role that Pretzel may play in it.

The more practical part is centered around a programmer’s point of view. It discusses the design of the Pretzel system (chapter 4) and states future work that may be done to improve the system (chapter 5). The most “practical” part follows in the appendix where you actually will see parts of the program code, i.e. some specifications of Pretzel modules.

Chapter 1

On Prettyprinting

The term prettyprinting means the rearrangement of a program’s source code to illuminate it’s logical structure and thus enhance readability. The term goes back to Henry Ledgard and his “Programming Proverbs” [33]. Prettyprinting has become a field of interest because many of todays popular programming languages are so called “free-format” languages, where there are basically no column-position or lineboundary restrictions on statements, declarations, or comments.

As a matter of fact, formatting and all other aspects of readability depend heavily on personal taste and skill. This has lead to a wide range of suggestions and standards concerning the formatting of programming languages, especially for the Pascal [22] language [1, 2, 3, 6, 11, 15, 17, 19, 32, 35, 42, 38]. The consistency of these proposals has also enabled construction of automatic formatting algorithms and tools that are usually called prettyprinters (or indenting programs). In the literature general examples of prettyprinters have been presented among others for the languages Algol [37, 50], PL/I [9], Lisp [14, 18, 52, 53], Ada [40], and of course for Pascal [20, 21, 3, 55, 1].

However, technological advance in the area of automatic typesetting has led to a set of powerful formatting tools called typesetters, or typesetting systems, of which TEX [27] is maybe the most apparent to computer scientists. These tools allow the preparation of documents in high quality suited for publication. Among the features of these systems are automatic line- and page-breaking, powerful macro-processing facilities and convenient devices for typesetting mathematical formulas. Seen in this light, automatic program formatting is only a simple instance of automatic typesetting [48, p. 652]. So prettyprinting algorithms that rely on professional typesetters can be simpler and produce better results at the same time, because a lot of the formatting problems (e.g. alignment, line-breaking, typesetting mathematical formulas) can be taken on by the typesetter.

In this chapter I will now present the prettyprinting algorithm that is used in the Pretzel system. It is a simple, but sophisticated method that relies on a typesetter. I have chosen a rather straightforward approach to this presentation using a lot of examples and leaving the discussion of this algorithm to the very end of this chapter.

1.1 Prettyprinting with Format Commands

The prettyprinting method presented here can be called prettyprinting with format command primitives and goes back to a similar method used by Knuth in his original WEAVE system for Pascal (see section 1.2 for details). Like most other prettyprinting algorithms this method functions similar to a compiler, i.e. an input file is processed and translated into an output file according to special rules. Here, the input file is the patch of source code that shall be prettyprinted and the output file is the text suited for the typesetter. The translation rules represent the special way in which source code should be formatted.

The main assumption is that we have a text formatter that uses control sequences (or tags) inside the actual text body for specifying all the different ways of formatting (such as fonts, indentation, spacing, etc.). Another term for this way of formatting control is in-text procedural markup and systems using this technique are commonly called document compilers (though this might only refer to the way they work, not to viewing text processing as programming). Common examples of such typesetting systems are TEX and the UNIX tools Nroff/Troff.

So what does the prettyprinting algorithm presented here actually do? During the processing of the input the only thing it does is to enrich the stream of incoming information with special control sequences that I will call format commands (or format command primitives). These commands are tags that are left for the typesetter to interpret. The set of format commands used here is basically the initial set used by Knuth.

To understand this procedure we don’t have to go into the special nitty-gritty details now. This will be done excessively in the following chapter. It probably will be more instructive to introduce the command set by way of example.

Finally a word about the notation: In the following examples of input text the format commands will be set in italics whereas normal strings will be given in typewriter type. The corresponding output text of the examples will reflect the input in a way similar to the output obtained using TEX as typesetter and the “normal” interpretation of the format commands.

1.1.1 Controlling the Amount of Indentation

So let’s now have a look at a few small examples of how prettyprinting works with the so called format commands. The first interesting thing to consider is the contol of indentation. Suppose we want to prettyprint a simple while-do-statement of Pascal and we want to indent the body of this statement a bit from it’s header keyword. The plain Pascal text of our first example looks like this:

  while (i<size) do begin i:=i+1; end;

(Of course the begin… end pair is obsolete, but don’t bother at the moment.) What we have to do now to achieve our goal is to insert the right format commands into this sequence of strings and pass it on to the formatter to do the rest of the work.

We wanted to indent the body of the while-statement a little, so we insert an indent command between the do and the begin. If you imagine this while - statement being part of a larger block of statements you probably don’t want the following statements to be indented as much as the body of the while-loop. So the indentation must be taken back after the while-body. This is done with the outdent command (that rather should have been named “de-indent”, but we‘ll stick with Knuth‘s word creation). So now we have:

  while (i<size) do indent begin i:=i+1; end; outdent

If passed to the formatter this will probably yield:

while (i < size) do begin i := i + 1; end;

So what happened? The format primitives don’t seem to have any effect on the output at all! Well, it only seems so. What the formatter has really done cannot be concluded in detail from the output above: It has increased the indentation after the do sure enough, but this doesn’t show, because the body of the while-statement fits on the same line as it’s header. We would have expected something like this:

while (i < size) do begin i := i + 1; end;

To get this result, one has to explicitly insert a line break before the begin. This is done with the force command, that denotes a forced line break. So the input

  while (i<size) do indent force begin i:=i+1; end; outdent

would yield the expected result.

So the indent and outdent primitives cause only future lines to be in- or “out”dented and have no effect on the present line that is just processed. The indentation shows only if there is a forced line break after the amount of indentation has been changed.

Why has Knuth chosen indent and outdent to behave in this way? To understand this, we should consider the above example without the keywords begin and end surrounding the assignment. The result

while (i < size) do i := i + 1;

really does look a bit stupid. In cases like this we would like the controlled statement to stand on the same line as the header because the program structure doesn’t need to be visualized in this simple case by indentation. The only thing one has to to here is to remove the force command from the input sequence and we will get:

while (i < size) do i := i + 1;

The interesting fact is that this doesn’t change our global rule that the body of a while-statement should be indented from it’s keyword. So the indent and outdent commands can always be inserted before and after the controlled statement. The only thing to worry about is whether or not to insert a force (which is always recommended before a begin, since this nearly always starts a sequence of two or more statements).

1.1.2 Controlling Line-breaks

The indent and outdent commands together with force are sufficient to control the alignment of similar syntactic constructs. But these three commands lack just one feature you will surely miss if you try to format some code with only this “triumvirate” of commands at hand. Consider for example a long block of statements in Pascal that contain extremely long names for identifiers as in the following example:

  begin string_buffer[string_buffer_pointer]:=c;
  string_buffer_pointer:=string_buffer_pointer + 1; end;

Handed over to the formatter, this may lead to the following

begin string buffer[string buffer pointer] := c; string buffer pointer := string buffer pointer + 1; end;

if the line width is unfavourable. This is okay if we had normal text in front of us. But here we are writing text in a programming language and breaking lines within an identifier violates the syntax. But on the other hand, how would you like: begin string buffer[string buffer pointer] := c; string buffer pointer := string buffer pointer + 1; end;

This may look better than the first possibility, but still doesn’t look nice. We would prefer line breaks to occur only between two adjacent statements (and usually also before the end) like in :

begin string buffer[string buffer pointer] := c;

string buffer pointer := string buffer pointer + 1;

end;

So the conclusion is, that we have to tell the formatter, where it is possible to break a line, if the current block of text should exceed the right margin. This is done with the break space primitive.

By inserting a break space amidst two statements (and even after the begin and before the end) the above problem cannot happen any more. A break space tells the typesetter, to break a line at this point, if he is looking for a place to break somewhere near it.

But even now just one feature is missing, that also has to do with line breaking. Consider for example a while-loop or an if-statement with a very long expression that governs it, as in:

  while (str buf[str buf ptr]<>c) and (str buf ptr<=buf size) do

Inserting break spaces before and after the “and” would seem to be a good solution to this line-breaking problem. But breaking the line after the “and”, say, would result in

while (str buf [str buf ptr] <> c) and

(str buf ptr ≤ buf size) do

what of course is intolerable. We want a long continuous line to be indented a little if it is broken, like in:

while (str buf [str buf ptr] <> c) and (str buf ptr ≤ buf size) do

Using the indent, outdent and force primitives is no solution in this case. This becomes clear if you look at the while-loop followed by its body:

while (str buf [str buf ptr] <> c) and (str buf ptr ≤ buf size) do begin … end

In case of a line break within a statement the indentation has to be sufficiently different from the normal break-spaced or forced indentation. So the answer is: More space!

Therefore we need a new primitive, namely the optional line break command opt. There are ten different opts that specify the badness of a line break at the point of it’s occurence. They are called opt0 , opt1 ,…, opt9 . A smaller number encourages line breaking at this point more than a higher number. So opt0 will nearly always lead to a line break whereas opt9 leads to a line break only if there is no opt0 ,…, opt8 primitive somewhere near and the line has to be broken around this point. (In TEX terms the digit n in the name of the opt command specifies the penalty associated with this break point. The penalty in the default interpretation of opt is about 10 · n.)

So the opt command denotes an optional line break with the continuation line indented a little more with respect to the normal indentation.

Returning to our example from above we should therefore say

  while (str buf[str buf ptr]<>c) and opt4 (str buf ptr<=buf size) do

indent force begin ...force end

depending on whether we rather liked a line break before or after the “and”. This would then yield the correct way of formatting, as in:

while (str buf [str buf ptr] <> c) and

(str buf ptr ≤ buf size) do begin… end

Note however that a break space is always a better place to break a line than an optional line break denoted by opt.

1.1.3 Additional Commands

By choosing the examples in the way above, I hope to have made clear that the format commands presented so far are sufficient to format program text of any block structured programming language in a manner according to most of the formatting standards referenced in the introduction of this chapter on page 5. Readers, who are not yet convinced, are put off until section 1.2, where the evolution of this method is reconstructed.

However, the list of format commands is not yet complete. There are still a few more primitives to learn, but they are not as important as the other commands that were presented up to this point. The following primitives were introduced to achieve better formatting results in special situations.

The first one is called backup and denotes a little negative horizontal space. This command must be preceded by a force, because it doesn’t make sense to backup within a line if it’s beginning has already been output. So the two commands “force, backup” appearing in a row can be seen as a short form for the sequence “outdent, force, indent”. The backup command is used in cases where statements are preceded by labels or simply where a line should stick out to the left a bit in order to emphasize it.

The next additional command is called big force. As the name implies this primitive acts like a force, but only on a bigger scale. big force not only forces a line break; it also inserts a little extra vertical space after the break. You can use the big force primitive to separate two adjacent lines that semantically do not belong together, like two function declarations.

If you are trying to typeset C or C++ programs, you will need a feature to typeset so called preprocessor directives. These are commands beginning with a # that can influence the source code before compilation. Normally these lines appear beginning at the left margin so we want a command that can be used to typeset lines like this. This command is called no indent. It causes the current line to be printed flushleft. So if you want to prettyprint a C or C++ preprocessor line, you should say

  force no indent #PREPROCESSOR DIRECTIVE force

and the line following this directive will be indented as much as the line before the directive.

Finally the last command of the present command set is called cancel. To understand this command I have to mention a tricky detail of the presented algorithm that I have omitted in the intoduction of this section: There I said that format commands are simply output by the prettyprinter one by one just like strings, only that they are “marked” as typesetting commands. Actually the prettyprinter also does a little bit of interpretation in advance. But these exceptions from the rule can be caught in two phrases. The first one is of global importance and the second one is related to the cancel command:

1. A sequence of consecutive break space, force, and/or big force commands is replaced by a single command (the maximum of the given ones).

2. The cancel command cancels any break space, opt, force or big force command that immediatly precede or follow it and also cancels any backup command that follows it.

So it seems that the cancel command is a command that mixes everything up again after we have put everything into a neat and tidy form! But this only seems so. The interpretation done by the prettyprinter according to the two rules stated above, was introduced to be more generous and more flexible with the placement of format primitives into the source code. Because, after all, the format commands will not be inserted by hand (as the reader might think after viewing the examples given above), but they will be inserted automatically by the prettyprinter according to a prettyprinting grammar.

1.1.4 Summary of Format Commands

Table 1.1 shows a complete list of all the format command primitives introduced in this chapter. The only command that wasn’t mentioned up to now is the null primitive that serves as a neutral (or empty) command.

null  empty command
indent  indents the next line a little more
outdent  takes back the last indentation (de-indent)
force  forces a line break
break space  denotes a possible space for a line break

opt n, n ∈ {0, …, 9} denotes an optional line break with the continuation line indented a litte with respect to the normal starting position. This line break will score a penalty of 10n.

backup  denotes a small backspace

big force forces a line break and inserts a little extra space

no indent  causes the current line to be output flushleft

cancel obliterates any break space, opt, force or big force command that immediatly precedes or follows it and also cancels any backup command that follows it.

Figure 1.1: List of format command primitives

1.1.5 The Prettyprinting Grammar

The functionality of the format command primitives from the previous subsection is only half of the work of the prettyprinting process. The second point is the way how these commands are automatically inserted into the source code. This is done using a so called prettyprinting grammar. To get an idea of how formatting with such a grammar works, I will give a short and low-level introduction now. The exact way in which this grammar is specified to work with Pretzel is a topic that will be discussed in detail in chapter 3.

The idea of formatting with a prettyprinting grammar is to insert format commands during a bottom up parse of the programming language text. Taking, say, a context free grammar to describe something similar to Pascal, a grammar rule for a while loop might look like this:

  WHILE expr DO stmt ⟶ stmt

This means that a WHILE token followed by an expression, followed by a DO token, followed by a statement can be reduced to a statement again (and can be used for example within a second while-loop that surrounds it). Here the tokens WHILE and DO are non-terminal symbols of the grammar and expr and stmt are terminals.

The simple trick that converts a normal grammar to a prettyprinting grammar goes back to Knuth’s idea of “attribute grammars”. In such a grammar every token has a so called translation that reflects certain semantic properties about it. (For example, the translation of an identifier token could be its name.) The translations of tokens are constructed from the translations of the tokens that it has reduced. The translation of the stmt token in our example would be put together from the translations of the WHILE, expr, DO and the other stmt token on the left side of the rule.

A prettyprinting grammar is an attribute grammar. As seen in the previous section, it is our aim, to insert format commands into certain spaces within syntactic constructs of the programming language. Now think of the translation of a token to be the actual printed output of the token, that can be sent to a typesetter. Inserting format commands into the translation can be achieved by defining the special ways of how to build the translation of certain constructs during rule reduction. So, for instance we could say: “Every time I reduce a WHILE-loop to a stmt-token, I should insert an indent and an outdent format command around the body of the whileloop. Additionally a force command should be inserted behind the outdent.” This can be expressed by the following notation, that uses “pseudo-tokens” (that can be imagined of being non-terminal tokens that match the empty string):

  WHILE expr DO indent stmt outdent force ⟶ stmt

This rule states, that the statement controlled by the while loop should be indented a little from it’s header if this statement happens to begin on a new line. The indentation is taken back (outdent) and there will always be a line break at the end of such a statement (if the force isn’t canceled).

As a matter of fact, this way of expressing the formatting of a programming language within its own grammar is very intuitive and powerful. It would be possible to code a prettyprinting grammar in this way into machine readable form. However, for reasons of simplicity of design the author has chosen to use a slightly different way of expressing such grammars in Pretzel, but this will be discussed in the following chapter (see also chapter 5 on future work).

The fact that such a grammar will solemnly be used to create a “prettyprinted” translation of a bit of source code has a great impact on the resulting grammar. In Pascal for instance, for-, while- and elseless if-statements are normally formatted in a very similar way; so the grammar mustn’t distinguish between the three constructs. This results in prettyprinting grammars that can be quite different from the normal grammars of the programming languages. Mostly they are smaller. But if you want to design a prettyprinting grammar yourself, it is always easier to start with a normal language syntax and simply enhance every rule to suit the occasion.

1.2 A Short History of Prettyprinting

In this section I will give a brief chronological overview over the area of prettyprinting, try to structure the field, and will show, how the present system fits into it.

1.2.1 Historical Notes

The prettyprinting of code has a long tradition that not only originates from the compulsion to typeset programs for publication. The readability or even the sheer beauty of a prettyprinted algorithm have also been a key motivation to this part of computer science.

The first people to call special attention to formatting issues were probably Peter Naur, Myrtle Kellington and William McKeeman. While Myrtle Kellington, as executive editor of ACM publications, helped to develop high quality programminglanguage typography standards, Naur was the first to include such formatting standards into his report on the Algol 60 language [39] and McKeeman was the first to present a prettyprinting algorithm for it [37]. This reaches back to the early 60s. In fact, McKeeman‘s algorithm is the first actual prettyprinter to be found in the literature. Its purpose was

“[…] to edit Algol 60 text that is difficult to read because, for example, the Algol has been transcribed from printed documents, or written by inexperienced programmers […]”

Later, other prettyprinters were presented for PL/I [9], Lisp [14], and finally Pascal [20]. These systems simply looked at the input text searching for special keywords. When encountering a keyword (which could be a begin or an opening brace, for example) a certain action would be triggered which would result in a line break, change of indentation, etc.

In these first approaches to the issue of prettyprinting the basic actions that prettyprinting includes were already visible. These concern (in order of importance):^{1}

• indentation and folding (i.e. determining line breaks) of source code

• the additional spacing of syntactic constructs (like expressions)

• using additional typographic means (e.g. different fonts)

The main disadvantage of the early systems was their language dependence. The style of prettyprinting was hard-wired into the system, which was basicly a big “case” switch over all known constructs that were to be treated specially. The main advantage of them, however, was their simplicity and their error handling capabilities (which is also the reason why such and similar tools are still widely used today). But it was soon clear that this approach wasn’t adequate and that structural changes had to be made to the concept.

In their paper titled “A One-pass Prettyprinter” [18] Hearn and Norman introduce a fundamentally new idea into this area. They simplify the whole concept of prettyprinting by introducing structure.

1In the late 70s there was one additional point on this list, namely the introduction of ‘connector lines’ into the prettyprinted output [8, 43]. But this method hasn’t found too much support since.

“The new method that we propose here will be described in terms of a pair of coroutines. One of these will be responsible for producing a stream of characters that represent the program being printed, the other makes decisions about how these characters should be displayed.” [18, p. 52]

This is a fundamental distinction, namely that between formatting policy and formatting algorithm [2] and is a vital step on the road to language independence.^{2}

A problem that arises from this separation is: how do the two coroutines communicate? Hearn and Norman use a simple FIFO buffer in which the first coroutine inserts text and “special markers” that indicate its decisions on the policy. These markers were mainly special blanks that indicate possible line breaks.

“The markers will contain enough information for the formatting process to discover what level of indentation would be appropriate to use were a line break to be inserted at that point.”

This resembles a special kind of ‘communication protocol’ and is the first hint to a thing that I have called ‘format command primitive’ throughout this chapter. Other authors [21, 41, 52, 5, 49, 48, 23] have taken up this idea and have introduced different sets of format commands that change and increase the communication facilities between these two processes. The two most elaborate to date are those of Rubin [49] and that of Knuth and Levy [30], that is used here.

The separation introduced by Hearn and Norman is an example of ‘separation of concerns’: the language dependent parts of prettyprinting are separated from the actual typesetting issues that arise, when putting text to paper. Blaschek and Sametinger [5] call this a distinction between “language dependent front end and language independent back end”.

1.2.2 The Language Dependent Front End

The earliest suggestions how to build the language dependent front end go back to Oppens fundamental paper on prettyprinting [41]. Though his main concern is the language independent back end, he makes suggestions about the “preprocessor” that should drive it. The main idea is to make a full syntactic parse of the prettyprinted code and to use the resulting parse tree to drive the prettyprinter. The format commands are either assumed to be implicit in the tree (i.e. every single branch is treated as a structural block) or they are explicitly inserted into the tree during the parse. Oppen writes:

“First, notice that the information needed by the prettyprinter can often conveniently be represented directly in the grammar […]. We modify the grammar of the language to contain prettyprinting information as above, where […] [the formatting commands] are nonterminals mapping only the empty string.” [41, p. 475]

This aspect has at last enabled people to use formal methods to describe layout rules. Mateti’s paper [36] is another approach in the same direction and is the first to adapt this method to Pascal.^{3} The fact that rules for layout and grammar are often closely related [34] also is a strong indication that this method is in fact adequate. The trend towards formal specification in this area has indeed been “very fortunate”

2This idea however has also introduced a slight blur in the terminology, as some authors refer to prettyprinting as consisting only of the actual “printing” on paper (i.e. the formatting algorithm)

[41, 23] and others still mean the entire process.

3It is interesting that Mateti’s solution was the result of formalization (due to verification needs)

and that Oppen’s proposals emerged from the language independent nature of his approach.

[56] and has also proved to be useful in other areas, such as syntax-directed editors [49].

To this end Rose and Welsh [48] have advocated the integration of format rules within the language syntax on the language design level. They state that “program format decisions [should be put] in the domain of the language’s designer, rather than its several implementators or numerous users, which implies uniformly formatted programs of improved readability and therefore usability.” [48, p. 651] Their idea does not try to impose rigid formatting rules on users of existing or future languages. Instead they propose a metasyntax and a set of guidelines that constrain and direct the language designer in the placing of format commands. These format commands include commands for indentation, as well as for line breaks and optional line breaks (so called “fold options”). The metasyntax and the guidelines only effect rather global issues of formatting but ensure consistency across language borders. They also present a folding algorithm that implements the format commands from their list.

This last approach by Rose and Welsh is currently the ‘state of the art’ in program layout issues. Woodman has published a thorough discussion of this scheme and has proposed refinements [56] that however do not alter the main points. It is an approach that in some way surpasses the area of prettyprinting in that it forces the formatting grammar to be equal to the language reference grammar. However, Knuth shows that a prettprinting grammar can be much simpler than a full-size language grammar, because it is able to treat semantically different contructs equally as they are formatted in the same way (e.g. if, for and while statements).

1.2.3 The Language Independent Back End

The language independent back end implements the formatting algorithm. It actually makes the formatting decisions that the formatting policy has outlined and communicated to it via the format commands. The main concern of most algorithms is line breaking (or folding). The proposals by Rose and Welsh [48] and Oppen [41] have been the most influential ones on other systems [52, 23, 5] in the literature. However, in both articles the authors refer to the future of their proposals for the formatting algorithm:

“The changes advocated must be seen in the light of current technological advances. Automatic program formatting is a very simple instance of automatic typesetting, as that provided by Knuth’s TEX system for technical or mathematical text.” [48, p. 652]

“It [the algorithm] is not, however, as sophisticated as it might be, and certainly cannot compete with typesetting systems (such as TEX) for preparing text for publication.” [41, p. 466]

As the WEB system shows, TEX has been used as a back end for a prettyprinter, but it has remained the only one that I am aware of. This leads to the question, why so little prettyprinters faciliate typesetters as back ends for their output? This question is very striking, as typesetters offer powerful capabilities, and for example, TEX’s line breaking algorithm has been advocated to be very suitable for exactly this task [25].

Oppen gives an answer to this in his paper:

“However, it [the algorithm] seems to strike a reasonable balance between sophistication and simplicity, and to be appropriate as a subcomponent of editors and the like.” [41, p. 466] It is surely the question whether you are prettyprinting on screen or preparing a publication. But the other part of the answer is maybe not so obvious and has to do with the traditional fears in the programming community.

A lot of prettyprinters have been built as parts of larger programming environments and were constituent parts of this larger system. A lack of modularity in the design (as for example the fundamental distinction presented in these sections and visialized in figure 1.2) often makes the resuing of subcomponents impossible. The prettyprinters hide somewhere in the larger system and are difficult to extract.

Another point is that an old habit of programmers is their strive for independence. They do not want their systems to rely on other systems. But this habit is hopefully getting less frequent today.

[figure: and format commands; stream of strings; formatting algorithm; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; typeset document; unformatted source code; prettyprinter; language dependent front end; language independent back end; parser using; prettyprinting grammar]

Figure 1.2: The module structure of modern prettyprinters

1.2.4 The Set of Format Commands

The format commands passed between the front end and the back end of the prettyprinter are the only means to convey the formatting policy to the actual formatter (see figure 1.2 that visualizes the modularity of a prettyprinter). This means that every typesetting feature must be expressible in them. In conjunction with this work it is important to ask, if the command set provided in the current Pretzel system is sufficient to format every desired feature that we can possibly think of. The answer is clearly ‘No!’, as there still are open prettyprinting problems. We will have a look at them later. But just how sufficient is the command set?

First we’ll look at whether it allows full control over line breaks and indentation. A detailed comparison shows that the command set used by Rose and Welsh is a subset of Knuth’s command set (indent, outdent, force, breakspace, opt).^{4} Rose

4The commands used by Rose and Welsh are denoted by the special symbols m, o, r, i and s. A stack is used to keep track of the indentation of the preceding lines. The symbol m pushes the current horizontal print position onto the stack and the symbol o pops the stack again. The metasyntax insists that every string produced from a non-terminal is bracketed by an m… o pair.

As no m and o are allowed elsewhere in a rule body, the amount of indentation is always restored to the prevoius value during formatting.

The symbol r denotes a line feed and a carriage return to the margin that is stored in top of the stack, whereas i increments the top-of-stack margin value and then performes an r. The s symbol is used to emphasize strings produced from a rule of the grammar. It is only allowed at the beginning of a rule body and directs the folding algorithm to force line breaks before and after the string produced from this rule. Optional line breaks (so called folding options, denoted ‘[i]’ or ‘[r]’) can be inserted between the non-terminals in the rule body.

necessary command set N = { indent, outdent, force, break space, opt }
convenient command set C = N ∪ { backup, big force }
sufficient command set S = C ∪ { cancel, no indent }

Figure 1.3: Naming of subsets of the command set.

and Welsh in fact show by example, that any language syntax can be transformed into a formatted syntax that in itself is capable of specifying all desirable folds and changes of indentation. The main precondition for this transformation is, that the starting grammar is context free. None of the five basic commands is superfluous (as we have seen in the first part of this chapter) so we can call these basic commands the necessary command set.

The necessary command set enables the first point of the basic actions of a prettyprinter mentioned on page 12. The other two points (additional local spacing of syntactic constructs; using different fonts) are things that depend on the capabilities of the typesetter and are not so much a question of the format command set. Thanks to procedural markup, as long as the prettyprinter allows us to insert strings between any two tokens at lexical level we are able to handle these two points too. However, in Rubin’s rather assembler like command set [49, p. 122] we see that the necessary command set still lacks full control over vertical and horizontal spacing. One can argue over what parts of this issue belong into the domain of the typesetter and what should be left to the user’s control, but there surely is an obvious need to express additional vertical separation in terms of a simple format command. In our case this is the big force command.

The other command that gives better control over horizontal space is backup. Both backup and big force can be simulated by sequences of commands from the necessary command set.^{5} So they are not necessary but convenient short-hands. We will call them, together with the basic commands the convenient command set.

Typesetting lines of code flushleft is not a feature commonly needed in modern structured programming languages, except in C/C++ when using preprocessor directives (and still they do not belong to the actual language itself). The no indent command caters for them but it is hardly necessary in other languages, where alone the idea of excluding single lines from the overall indentation frame violates all rules of good program layout.

Finally the cancel command does not add any striking new features to the command set. It just allows more flexibility in the placement of format commands in the output. A well placed cancel command can obliterate a dozen rules of your prettyprinting grammar and thus can deflate prettyprinting grammars very much. So if you define sufficiency as incorporating convenience and flexibility we could call this whole set of presented commands a sufficient command set. This, however, naturally excludes the open problems mentioned in the next subsection. The two subsets of this sufficient command set are summarized in table 1.3.

1.2.5 Open Prettyprinting Problems

If you have ever tried to use a prettyprinter for your own code you will surely have come across problems concerning user control. Yehudai states, that “[…] it is not clear that any automated indentation scheme will be adequate, as I may choose different ways to lay out the same construct in different parts of my program.” [57, p. 85]

The most obvious analogy is the i symbol. It corresponds to the sequence indent, force and since every indent is followed by a force or made superfluous by a matching outdent you may transform every occurence of indent into an optional i. The r symbol, performed inside the i, denotes a force command. By popping the margin stack, the o symbol plays the role of the outdent command.

The two fold options ‘[r]’ and ‘[i]’ correspond to break space and opt.

5The sequence ‘force, backup’ is equal to ‘outdent, force, indent’ and ‘big force’ is something like ‘force, null, force’, depending on the exact interpretation of the typesetter.

Woodman gives an example for this point that he calls “adaptive combs” [56, p. 616], where a long if/elsif statement in Modula-2 is cited as:

if longexpression1 then

longstatement1

elsif expr2 then stmt2
elsif longexpression3 then

longstatement3 else

longstatement4 end

Here the statement stmt2 appears on the “tooth” of the comb, whereas the context rather suggests that it should appear between the teeth like all other statements. This is a question of context sensitive formatting and it is an open question, how to deal with this problem in terms of format commands.^{6}

Another open problem falls into the same domain, but deals with horizontal spacing instead of line breaking. Blaschek [5, p. 701] points out that his system is not able to align constructs horizontally, as for example in:

with stmt ˆ do
position := pos
decLabel := label
next  := nil

end

This is a problem that no prettyprinter to date has mastered in an automatic fashion.

It is an open question whether these problems could be solved using intelligent algorithms that learn a layout style by example, like for instance the ‘intelligent’ prettyprinter by Winter and Cook [55]. But maybe the worst (and oldest) prettyprinting problem is how to typeset comments! Papers as early as those of Mohilner [38] and Jackel [21] address this topic and the core of the problem surely lies in the nature of comments. The paper “Programming languages should NOT have comment statements” by Kaelbling [24] and that by Grogono [16] strongly argue that at last comments should be treated equally as parts of the language, not as an add-on that is forgotten at first point during compilation. Grogono brings this to the point by stating that “Comments are second class citizens.” [16, p. 80] They are mostly allowed anywhere in the source code and prettyprinters who want to preserve them in the output have severe problems doing that without destroying the program’s format, because they have to be incorporated into the prettyprinting grammar.

There have been attempts to do this in a structured way, i.e. to divide comments into classes and to treat each class differently [46, 49, 13, 47]. Rose and Welsh distinguish between pre- and postcomments and state that comments must move with the syntactic elements that they refer to [48, p. 660]. Kaelbling even goes as far as to demand “scoped comments”, i.e. comments that explicitly show to which part of the program they belong.

6Woodman proposes the idea of “linked folds”, i.e. a special set of format commands that force a number of consecutive folds to be treated equally, but doesn’t elaborate on it.

All these attempts have the same goal, but the problem of prettyprinting comments will only be solved, if they are treated as an equal part of a programming language and thus are included in the reference grammar.

1.3 Summary

As this has been quite a long chapter I will try to recall the main points of it now:

In this chapter I have introduced the way of formatting that Pretzel uses in the generated prettyprinter. This method uses format commands that are intermixed with the text strings of the source code according to a prettyprinting grammar and interpreted by the typesetter. A few examples were given.

In the second part I have tried to reconstruct the evolution of this formatting algorithm by giving a brief overview over the history of prettyprinting. This has shown the main points that structure the field (distinction between formatting policy and formatting algorithm, formalization of formatting policy through a prettyprinting grammar, different sets of format commands). From this overview I have shown how the algorithm used be the Pretzel system fits into the field and how sufficient its command set is.

Using Pretzel

Pretzel is a program that generates a prettyprinter module from a formal description of the way a certain language should be prettyprinted. (NB: Pretzel produces modules, not programs!) This chapter is the user’s manual for Pretzel. It first gives an overview of how Pretzel works and how the generated prettyprinter can be used. Secondly it takes a close look at the formats of the two input files to Pretzel, the formatted token and the formatted grammar files. Thirdly, this chapter states how the program is invoked and how the input is turned into the prettyprinter. Finally there is a complete example for a prettyprinter for Pascal that was generated by Pretzel.

2.1 The Concept of Pretzel

The concept of Pretzel is visualized in figure 2.1. From a formal formatting description of a programming language P, Pretzel generates a prettyprinting function that can be used to prettyprint source code in P. To get the actual prettyprinting program, you only have to supply a main program (or use the one that comes with Pretzel). If the way of prettyprinting needs to be changed, the user only needs to change formal parts in the input and use Pretzel again to get an enhanced prettyprinter.

Figure 2.2 on page 21 shows the generating process in slightly more detail. The figure shows that the program Pretzel doesn’t generate a prettyprinter immediately; what it does is to produce code that can be turned into a C++ prettyprinting function with the help of two tools:

flex A POSIX.2 compliant lexical analyser generator.

Bison A POSIX.2 compliant parser generator. The version used with Pretzel has

[figure: pretzel; formal description; prettyprinter; Text; prettyprinted; text]

Figure 2.1: The concept of Pretzel.

to produce C++ compliant source.

Users that are already familiar with the basics of both tools will find it easier to read the following text because the way of specifying input to Pretzel is quite close to the ways used by them. However, this text aims at people who don’t have such knowledge and will explain everything that is necessary.

Also visible from this figure is that Pretzel creates two things:

• A prettyprinting scanner and

• a prettyprinting parser (the actual prettyprinter).

The prettyprinting parser is the actual prettyprinter function that you normally want to get when using Pretzel. The prettyprinting scanner is used by the parser and takes care of the token formatting. Both parts are separate modules with a well defined interface and can be used individually. Hence, you can write your own scanner or parser if you really need features that the ones produced by Pretzel don’t have. (For a description of the interface to both, see section 2.1.2 or the specifications of the two generator functions for a complete reference.)

2.1.1 The Input Files

The word “pretty” is very subjective and so programming language source code can be printed in a “pretty” kind of fashion in almost infinitely many ways, according to the taste and preferences of the user. If the task of prettyprinting is handed over to the computer, the user must specify in detail all of his wishes towards the appearance of the output of the prettyprinter.

To generate a prettyprinter, Pretzel needs two descriptions that it expects to find in two different files:

A formatted token file. This file should contain all information concerning the individual formatting of tokens (i.e. identifiers, reserved words, etc.).

A formatted grammar file. This file should contain a prettyprinting grammar, i.e. a context free grammar enhanced with formatting commands. This information is necessary to handle the more global aspects of prettyprinting that need information about the language context (i.e. indentation, line breaks, etc.).

The name of the first file might be a little misleading, since it doesn’t contain formatted tokens. Instead it tells you what you will get from the definitions therein. A name like “token formatting file” might have been a little better, but the similarity in names between the two input files sounded good and seemed to outplay this small inconsistency.

The special formats of these two files are described later in section 2.2. Let’s first look at what the generated scanner and parser functions look like.

2.1.2 The Generated Prettyprinting Functions

So there are two inputs to Pretzel. And if these inputs are okay and the program runs without error, you will obtain an output from which a C++ prettyprinting function can be made. The output of Pretzel are two files. The first file is a valid Bison file from which the actual prettyprinting parser can be obtained. The second file (generated from the formatted token file) can be processed with the scanner generator to form the prettyprinting scanner used by the parser.

The generated Bison file contains all definitions for the actual prettyprinting function. It’s default interface is:

[figure: grammar file; Bison source; C++ code; prettyprinting; prettyprinter; pretzel; Bison; CC; formatted; parser; common; token header; scanner; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; token file; flex source; C++ code; prettyprinting; pretzel; flex; CC; is called by; formatted]

Figure 2.2: The current process of generating a prettyprinter with Pretzel.

void pparse (istream∗, ostream∗);

This is in the flesh the desired prettyprinter. The input (source code text) enters the prettyprinter through an input stream (i.e. a C++ istream object) and leaves the prettyprinter through an output stream (i.e. a C++ ostream object). This output isn’t actually prettyprinted yet. By default the output is delivered in a format suitable for TEX to typeset it. It can be changed however to suit any other typesetter. (The output format is very much part of the implementation of the Output class. See into the appendix for details.)

The prettyprinting function depends on a separate function that cuts the input file into small bits (tokens) and does the local formatting. This function is provided in the scanner generator source produced from the formatted token file. It’s default interface consists of two functions:

void pscan init (istream∗);

int pscan (Attribute∗∗);

The first function serves as an initializer and tells the scanner where it should take its input from. The second function is the actual scanner. It scans the input and returns token codes as integer numbers. These codes have to be the same as the ones used by the parser (look at section 2.2.2 for details). The formatted look of this token is handed back as a call-by-reference argument of type Attribute.

Please note that the interface of the prettyprinting scanner is exactly how the parser above expects it to be. If you are planning to create a normal prettyprinter you won’t have to bother about the interface of the scanner, because it works together fine with the parser. If you really need to know more details or want to change the default interface in any way, look into section 2.3.4 for a description of some of the more specialized topics.

To use the prettyprinting functions in a C++ program, header files are needed that declare the interface. From the information above it is possible for you to write your own header files for the generated scanner or parser. But Pretzel spares you from this job, however, as it offers two template header files that you can copy and edit to suit your own purposes. They provide the default interface of both functions. Look into the README file for an exact description of their location in the Pretzel distribution.

2.2 The Format of the Input Files

Now we turn to a vital thing for the user of Pretzel: The format of the Pretzel input files. Here the user has to put a formal description of the underlying programming language and (with the help of format commands) state how its text should be formatted.

We have seen that Pretzel takes two input files: The formatted token file and the formatted grammar file. We suggest to use the suffix ‘.ft’ for a formatted token file and ‘.fg’ for a formatted grammar file.

2.2.1 The Formatted Token File

The formatted token file contains a list of token definitions with their corresponding “prettyprinted” form. The prettyprinted form of a token will be called an attribute or a translation.

The general outline of the formatted token file is

declarations

  %%

token definitions

Normally, the declarations part is empty. You can put a general description of the file here (as a C comment) and redefinitions of the default interface go here as well (see section 2.3.4 for more).

The token definitions section of the formatted token file contains a series of token definitions of the form:

pattern  token  {attribute}

The pattern must be a valid regular expression (in terms of flex) and must be unindented. The token specifies the symbolic name of the token for the pattern and begins at the first non-whitespace character after the pattern. The token name must be a legal name for an identifier in Pascal notation and must be all in upper case. (Underlines are allowed but not at the beginning of a word.)

The attribute for this token, that is it’s prettyprinted form, consists of all text between the two curling brackets ‘{’ and ‘}’. Attributes can be either simple strings (surrounded by double quotes) or format commands (like force, indent) or a combination of both joined together by the ‘+’ sign. Attribute definitions can cover several lines and the starting ‘{’ needn’t stand on the same line as the token definition; however subsequent lines must be indented with at least one blank or one tab.

If you define strings as part of an attribute definition, you have to specify them in a C kind of fashion, i.e. you can insert newlines and tabs with ‘\n’ and ‘\t’. But if you want to insert a backslash into a string, you mustn’t forget to put two backslashes (‘\\’) into the input file. This is especially noteworthy if you are using TEX as typesetter, because TEX uses a backslash as a prefix for typesetting commands.

If the definition of the attribute is omitted Pretzel creates an attribute for this pattern by default. The default attribute consists of the string containing the text matched by the corresponding pattern.

The user himself may also refer to the matched text by using the sequence ‘**’. Thus

  "foo"       BAR
  "foo"       BAR     { ** }
  "foo"       BAR     { "foo" }

all have the same meaning.

You can use a ‘|’ sign as a token name; this signals that the current regular expression has the same token name (and also the same attribute) as the token specified in the following line (empty lines are ignored). An attribute definition behind a ‘|’ is illegal. However you may specify regular expressions with neither a token name nor an attribute to give a default rule or to eat up whitespace.

The following examples are all legal token definitions (and please note the dot in the very last line):

  [0-9]           DIGIT
  "{"             OPEN           { "\\{" + indent + force }
  [a-z][a-z0-9]*  ID             { "{\\it " + ** + "}" }
  "function"      |
  "procedure"     PROC_INTRO     { big_force + ** }
  [\t\ \n]        |
  .

The declarations and the token definitions must be separated by a line containing only the two characters %%. So the shortest possible formatted token file is

   %%

but this doesn’t seem of any use, does it?

2.2.2 The Formatted Grammar File

In the formatted grammar file the user encodes the general prettyprinting grammar for the programming language. This is done by specifying a context free grammar of the language and by adding information about the creation of new attributes in every rule.

The formatted grammar file is the second and last input to the Pretzel program. Its general outline looks like this:

token declarations

  %%

grammar rules

The token declarations section may be empty and the separator between the two parts of the file (%%) must appear unindented on a single line by itself. Before we look at these declarations, let’s have a look at the grammar rules.

The grammar rules section contains the collection of rules of the context free grammar that can be accompanied by an attribute definition. A rule is specified by stating the resulting token, a colon and then the series of tokens which will be reduced by this rule. The rule is ended by a semicolon. A block definition in Pascal for example might look like this:

  block : BEGIN stmt_list END
  ;

Following the token list on the right side of the colon can be an attribute definition; this definition states, how the translation of the produced symbol is obtained from the tokens on the right side of the rule.

An attribute definition is bracketed amidst curling brackets ‘{’ and ‘}’ and can again consist of strings (in double quotes) and format commands or both joined together with ‘+’. But here you can also refer to the attributes of the tokens on the right side of the rule. This is done in a slightly awkward notation with a number that is preceded with a ‘$’ dollar sign. The numbers refer to the order of appearance of the symbols on the right side of the rule. So ‘$1’ refers to the first token of the rule, ‘$2’ to the second, …

Again attribute definitions are allowed to span several lines and strings must be specified in C manner.

For example, here again is the possible definition of a block in Pascal, now with an example attribute definition:

  block : BEGIN stmt_list END   { $1 + $2 + force + $3 }
  ;

The attribute of a block will therefore consist of the attributes of the BEGIN and stmt list tokens, joined together with a force command and the translation of the END token.

The attribute definition may be omitted. If this is so, Pretzelwill by default form the attribute of the produced symbol from the simple concatenation of the attributes on the right side of the rule. For instance

  stmt : block SEMI
  ;

means the same as:

  stmt : block SEMI       { $1 + $2 }
  ;

Of course you may also have empty right sides of a rule (to produce things out of nothing) or simply concatenate two or more rules resulting in the same symbol with a ‘|’. So the following are legal rules:

  stmt_list   :                      { force }
              | stmt_list stmt SEMI  { $1 + $2 + $3 + force }
  ;

To end this subsection, we have to return to the token declarations section of the formatted grammar file. Here we have to insert a special line for every terminal token that appears in the grammar rules. These definitions are of the form ‘%token tokenname’. This part of the formatted grammar file is owed to Bison and should be removed in subsequent versions.

2.2.3 Comments and Code

There is a very simple way of putting comments into the formatted token and formatted grammar files. This is done in a C++ kind of manner by preceding the comment with a double slash (‘//’). All characters between this sign and the end of the line are ignored by pretzel.

In both files you can put additional C++ code before and after the definitions/grammar sections. If you want to insert code at the end of your file, you have to put a second ‘%%’ on a line by itself and put the code behind it. C/C++ Code before the definitions/rules section has to be tied in with a ‘%{’, ‘%}’ pair.

Inserting extra code will however only become interesting if these functions could be accessed from inside the attribute definitions of the grammar. This might be possible in a later version of Pretzel.

2.3 Making a Prettyprinter with Pretzel

So if you have specified the two necessary files that describe a prettyprinter for your favourite programming language called, say P now, you will have a formatted token file called p.ft and a formatted grammar file called p.fg. To get your prettyprinter from these two files you have to successively invoke Pretzel, flex, Bison and your C++ compiler. It is very convenient to use the make tool to support you with this task. There is a typical Makefile for such cases included in the Pretzel distribution. You can use it as a starting point for your own files.

2.3.1 Invoking Pretzel

The first step would be to produce the flex and Bison files using Pretzel. Pretzel is invoked by typing

  pretzel

at the command line. The full usage of Pretzel can be obtained using the -h option. It is:

  pretzel [-qtgdh] [-o outfile] (prefix | file1 file2)

Here’s an explanation of the options:

-q Run quietly (no screen output).

-t Process formatted token file only.

-g Process formatted grammar file only.

-d Run in debug mode (i.e. print out debugging information on the screen while running).

-h Show full usage.

-o outfile Names of the produced output files begin with “outfile”.

The options -t and -g are mutually exclusive, i.e. you can’t choose both at the same time.

The command line parameters have different meanings depending on whether one ore two names are given. If there is only one parameter, it specifies the prefix of both formatted token and formatted grammar files. The suffixes ‘.ft’ and ‘.fg’ are assumed. But if there are two parameters at the command line, Pretzel will take the first as full name of the formatted token file and the second as full name of the formatted grammar file. In this case, the output files will get a default name. The output files will have endings ‘.l’ (token file) and ‘.y’ (grammar file).

2.3.2 An Example Pretzel Session

So let’s return to our initial example with our programming language P for which we want to build a prettyprinter. To get both valid flex and Bison files we invoke Pretzel with:

  pretzel -o printp p

This will result in two new files, namely printp.l and printp.y. (The -o option defines the prefix of the output files.) The .l-file is the flex file and the .y-file is the Bison input. So now try

  flex printp.l
  bison -d printp.y

to create C++ code for your prettyprinter. After renaming the output files of flex and Bison to, say, myscan.c (flex) and myparse.c (Bison) you have to compile both. After compilation you will get object files that, together with the default headers, form the prettyprinter module. Other programs, that want to use the prettyprinter, only have to include the header file and be linked with the resulting object files. Figure 2.3 shows a minimal main program that reads from the standard input and outputs the prettyprinted code to the standard output.

/*
 * a minimal main program to test a pretzel prettyprinter
 */
#include <iostream.h>
#include "pparse.h"       // include the header of the prettyprinter
int main () {
    pparse(&cin,&cout);   // call the prettyprinter function
    return(0);
}

Figure 2.3: A minimal main program that uses a Pretzel prettyprinting function.

The -d option of Bison produces a so called ‘token header’ file needed by the scanner (see figure 2.2 on page 21). It contains information about all of the nonterminal tokens that the parser knows of. The scanner expects to find it under the name ptokdefs.h, so you should rename this file to meet the scanner’s expectations.

2.3.3 Debugging the Prettyprinting Grammar

According to the prettyprinting grammar you specify, the generated prettyprinting function will parse the input text and try to prettyprint it. However, it sometimes may be impossible for the parser to parse the input according to the supplied rules. In such a case, the prettyprinted output may look a bit strange (a lot of stuff will be missing), but the prettyprinter will never stop or even issue an error.

To fine-tune your grammar and look for the place it couldn’t cope with, you can switch on a debugging feature that offers you are large amount of tracing information. You can switch it on by setting the external integer yydebug to a nonzero value. As soon as this is done and the parsing starts, you will see the standard Bison tracing reports. In addition to this, the attribute of every token read is displayed directly after the token name inside brackets when a new token is read. However, depending on the complexity of your grammar and the length of the input, parsing can take very long if you have the tracing feature switched on. So you should debug your prettyprinting grammar with small examples.

2.3.4 Advanced Topics

This section finally tells you some ways to fine tune your prettyprinter.

Pretzel allows you to rename the prettprinting functions. This is done via C preprocessor makros. Here’s a list of makros with which you can influence the interfaces of prettyprinting scanner and parser. We’ll see how to redefine them in a moment.

PPARSE NAME This makro is the name of the prettyprinting parser (‘pparse’ by default).

PSCAN NAME This makro holds the name of the prettyprinting scanner (‘pscan’ by default).

PSCAN NAME INIT This is the name of the initialiser function of the scanner (‘pscan init’ by default).

PTOKDEFS NAME This is the name of the common token header file that defines the token codes of the terminal tokens returned by the prettyprinting scanner (‘ptokdefs.h” by default).

The names of these functions will be defined if the user doesn’t have his own definition. For example, if you want to change the name of the prettyprinting scanner to ‘foo’, you have to put lines like this into the declarations section of your formatted token file:

%{
#define PSCAN_NAME foo
%}

Note that you can only change the names of the functions, not other parts of their interface. (The ‘%{’ and ‘%}’ are necessary because the line in between is C code.)

The prettyprinting parser implicitly expects to have a scanner available for parsing under the default name. So if you are using a prettyprinting scanner with a different name you have to redefine the same makro again in the formatted grammar file.

2.4 Example (a Grammar for Pascal)

To end this chapter I will try to give a small impression about the looks of a formatted token and a formatted grammar file by giving a small example. The following inputs are excerpts of a prettyprinting grammar for something like Pascal. It was basically derived from Knuth’s context sensitive grammar in his original WEAVE program, but suits my own formatting preferences. The typesetter used in this example is TEX using the macro definitions from Knuth’s cwebmac macro package for CWEB. Basicly, you could use any typesetter that has in-text procedural markup. The only thing you have to do is to write a macro package with a special tag for every format command and have the Pretzel prettyprinter output these special tag names instead of the current control sequences (\1 … \7). Using the cwebmac package spared me from having to write my own set of commands and works fine for demonstration purposes. (See chapter 5 on the problems of changing output formats.)

Note that if you want to use the following code for playing around, you have to tell flex to create a case-insensitive scanner since reserved words are only noticed in lowercase.

The sequence ‘[...]’ denotes that parts are left out from the original file.

2.4.1 The Formatted Token File

/* pretzel formatted tokens for simple PASCAL */
%%
"<>"       MATH     { "$\\neqI$" }         // not equal sign
"<="       MATH     { "$\\leq$" }          // less or equal
">="       MATH     { "$\\geq$" }          // greater or equal
":="       MATH                            // assignment
'([^']|'')*'    SIMP                       // strings
"("        OPEN
")"        CLOSE
"["        OPEN
"]"        CLOSE
"*"        MATH     { "$\\ast$" }
","        MATH     { ** + opt9 }
".."       MATH
"."        SIMP
":"        COLON
";"        SEMI
"="        MATH
"+"        MATH
"-"        MATH
"<"        MATH     { "$<$" }
">"        MATH     { "$>$" }
"/"        MATH
                 // this to allow underscores in identifiers:
"_"[a-zA-Z0-9]*    ID_TYPE    {"\\" + ** }
[0-9]+             SIMP
[0-9]*"."[0-9]+    SIMP
and        MATH     {"\\AND "}
array      ALPHA    {"\\&{array}"}
begin      BEG      {force + "\n" + "\\&{begin}" }
boolean    SIMP     {"\\&{boolean}"}
case       CASE     {force + "\\&{case}" + cancel }
const      INTRO    {force + backup + "\\&{const}"}
div        MATH     {" \\&{div} "}
do         OMEGA    {"\\&{do}"}
downto     MATH     {"\\&{downto}"}
else       ELSE     {"\\&{else}" }
end        END      {"\\&{end}" }
for        ALPHA    {"\\&{for}" }
function   PROC     {big_force + backup + "\\&{function} " }
if         ALPHA    {"\\&{if}" }
integer    SIMP     {"\\&{integer}"}
mod        MATH     {"\\&{mod}"}
not        MATH     {"\\neg "}
of         OMEGA    {"\\&{of} " + cancel }
or         MATH     {"\\V "}
procedure  PROC     {big_force + backup + "\\&{procedure} " }

program    PROC     {big_force + backup + "\\&{program} "}
readln     SIMP     {"\\&{readln}"}
real       SIMP     {"\\&{real}"}
record     RECORD   {"\\&{record}"}
repeat     BEG      {force + "\\&{repeat}" }
then       OMEGA    {"\\&{then}" }
to         MATH     {" \\&{to} "}
type       INTRO    {force + backup + "\\&{type}" }
until      UNTIL    {force + "\\&{until}" }
var        INTRO    {force + backup + "\\&{var} "  }
while      ALPHA    {force + "\\&{while}" }
with       ALPHA    {force + "\\&{with}"}
write      SIMP     {"\\&{write}"}
writeln    SIMP     {"\\&{writeln}"}

"{"[^}]*"}"    COMMENT    { "\\C{" + ** + "}" }
[a-zA-Z][a-zA-Z0-9]*    ID_TYPE    // identifiers
[\t\ \n]          // eat up whitespace
.                 // eat up other non matching characters

2.4.2 The Formatted Grammar File

/* pretzel formatted grammar for simple PASCAL. */
%token SEMI
%token BEG
%token END
%token MATH           // token should only be used in math mode
%token SIMP           // other simple tokens
%token OPEN
%token CLOSE
%token ALPHA
%token OMEGA
%token UNTIL
%token INTRO
%token PROC
%token COLON
%token ELSE
%token COMMENT
%token ID_TYPE
%token RECORD
%token CASE
%%
stmt_list    : stmt                // collect everything on a
             | stmt_list  stmt     // list of `statements'
;
    // what can statements be?

stmt         : COMMENT             {cancel + $1}
             | proc                // procedure heading
             | SEMI                // empty statement
                                   {cancel + $1 + force }
             | BEG stmt_list END   // a block
                            { $1 + indent + force + $2 +
                              cancel + outdent + force + $3 }
             | math                // an expression
;
math         : MATH                // build something like an
             | math math           // `expression'
             | simp
             | COLON
             | OPEN decl_list CLOSE
             | RECORD stmt_list END
;
simp         : SIMP
             | identifier     { "\\\\{" + $1 + "}" }
;
identifier   : ID_TYPE             // put together identifiers
             | identifier ID_TYPE
;
decl_list    : math                // parameter lists
             | INTRO math                   // for var-parameters
             | decl_list SEMI math    {$1 + $2 + " " + $3 }
             | decl_list SEMI INTRO math    // for var-parameters
;
stmt         : ALPHA math OMEGA stmt  // if then/while do etc.
                                 { $1 + " " + $2 + " " + $3 +
                                   indent + force + $4 + outdent }
             | ALPHA math OMEGA stmt ELSE stmt   // if then else
                           {$1 + " " + $2 + " " + $3 +
                            indent + force + $4 + outdent +
                            force + $5 + indent + force + $6 +
                            outdent }
             | CASE math OMEGA stmt_list END     // case of end
             | BEG stmt_list UNTIL math          // repeat until
                                { $1 + indent + force +
                                  $2 + cancel + outdent + force +
                                  $3 + " " + $4 }
;
proc         : proc INTRO math SEMI   {$1 + $2 + $3 + $4 + force}
             | PROC            // procedure heading
;
stmt         : INTRO math SEMI  // variable and type declarations
                           {$1 + $2 + $3 + force}
;

2.4.3 Using the Generated Prettyprinter

The definitions in the previous section are sufficient to produce a prettyprinter for Pascal, that can handle most of the language features and formats them to suit my own preferences. As an example text I have chosen a simple Pascal routine to compute the square root of a given real number. It was written solemly for pleasure in my first year of study in Darmstadt to test one of the algorithms that were presented in a maths lecture. This is to demonstrate, that the example is by no means constructed to suit the demonstration purpose in this paper. I have tested the prettyprinter on various other Pascal texts.

The Pascal Input

This is what the plain Pascal source code looks like.

function Wurzel ( x : REAL ) : REAL;
{Berechnet die positive Quadratwurzel von x}
var x0, x1 : real;
begin
if x>=0 then begin
             x1:=x;
             repeat
               x0:=x1;
               x1:=(x0+x/x0)/2;
             until (x0 + abs(x0-x1) = x0);
             Wurzel:=x1;
             end
        else begin
             writeln('Fehler: Wurzel ist komplex!');
             end;
end; {Wurzel}

The Translation in TEX

This is what the prettyprinter generated out of the Pascal text. Note again that the format commands are translated to suit the cwebmac macro package of the CWEAVE system. The commands outside of the indicated area necessary to put TEX into the right mood to format source code. The control sequences \1… \7 refer to indent (1), outdent (2), opt (3, with the digit n following directly), backup (4), break space (5), force (6) and big force (7). The commands \\ and \& tag identifiers and reserved words, respectively.

\input cwebmac
\B
\Y
% generated text begins here
\7\4\&{function} \\{Wurzel}(\\{x}:\&{real}):\&{real};
\C{{Berechnet die positive Quadratwurzel von x}}\6\4\&{var}
\\{x0},\39\\{x1}:\&{real};\6
\&{begin}\1\6\&{if} \\{x}$\geq$0 \&{then}\1\6
\&{begin}\1\6\\{x1}:=\\{x};\6\&{repeat}\1\6\\{x0}:=\\{x1};
\6\\{x1}:=(\\{x0}+\\{x}/\\{x0})/2;\2\6\&{until}
(\\{x0}+\\{abs}(\\{x0}-\\{x1})=\\{x0});\6\\{Wurzel}:=\\{x1};
\2\6\&{end}\2\6\&{else}\1\6
\&{begin}\1\6\&{writeln}('Fehler: Wurzel ist komplex!');
\2\6\&{end}\2;\2\6\&{end};\C{{Wurzel}}
% generated text ends here
\end

The Formatted Output

This is what the actual formatted output looks like, if the above text is processed by TEX.

function Wurzel(x:real):real; {Berechnet die positive Quadratwurzel von x} var x0 , x1 :real;

begin

if x≥0 then begin

x1 := x; repeat

x0 := x1 ;

x1 := (x0 +x/x0 )/2; until (x0 +abs(x0 -x1 )=x0 ); Wurzel := x1 ;

end else

begin

writeln(’Fehler: Wurzel ist komplex!’); end;

end;{Wurzel}

Literate Programming and Pretzel

The Pretzel program is the result of a project that the author worked on in 1994 at the Technical University of Darmstadt. It is a small contribution to a larger project of research that has to do with the literate programming paradigm that I have already mentioned in the introduction to this report.

This chapter now introduces the literate programming paradigm in slightly more detail and outlines the research project of which Pretzel is only a small part. Taking this larger frame into account, I will finally describe the role that Pretzel could play in this research.

3.1 On Literate Programming

“When was the last time you spent a pleasant evening in a comfortable chair, reading a good program?” asks Jon Bentley in the introduction to his regular column in the Communications of the ACM [4]. As might be suspected, Jon Bentley is far from being sarcastical; his question is meant seriously and our not taking him seriously reveals only the poor attitude we have towards the readability of a program’s source code.

But how can it be pleasant and amusing to read a program, if this program is simply another sequence of programming language commands destined for a compiler, that—if we are lucky—may be decorated with a few lines of commentary? This surely isn’t very pleasant; but the reading and understanding of a program is far too important to be unpleasant. The only way to get out of this dilemma is to write programs with a different attitude: Programs are not merely lines of code that primarily instruct a computer to act in a special way; programs must be destined to meet the eye of a human being and explain him or her what the author wants a computer to do [28, p. 97].

Though this necessity has long been recognized, it is due to Donald Knuth and his idea of “literate programming” that today programs can be written in a style that makes comprehension of source code indeed a pleasant and rewarding job. The name of his new concept is derived from the idea, that programs should be considered works of literature; in the course of this idea, the programmer’s main concerns switch from efficiency and brevity to exposition and excellence of style (without forgetting the first two goals of course). Considering this turning of approach, Knuth’s idea can legitimately be called a new programming paradigm [10].

There has been (and still is) a lot of discussion concerning the question of what makes a program literate or what languages really support a literate programming style. However, there seems to be a consensus that literate programming languages must enable the programmer to be absolutely free in choosing the order and way of presenting his ideas. It must be possible to use a top-down approach of presentation as well as a bottom-up approach or even a mixture of both. The key notion here is that it must support arbitrary refinements together with an easy way to insert comments into the program (imagine the notion of delimiting parts of the source code instead of bracketing comments, as you would normally do in traditional languages). The only restriction the programmer should have to worry about is the limitation of his own programming skills.

In 1984 Knuth presented a first literate programming language that was based on Pascal, which he called WEB. In fact, he didn’t introduce a whole new language: WEB programs and Pascal programs are essentialy the same thing, only that the Pascal source code is split into small pieces and shuffeled around in a WEB program. Knuth proved that his WEB system was practicable by writing (among other smaller examples) a full scale software system in it, namely TEX [29, 27]. These two things, together with his naming of the area, are Knuth’s main contributions to the idea of literate programming.

3.1.1 The WEB system

A conventional WEB system—like that first presented by Knuth [28]—is chiefly a combination of two other languages:

• a document formatting language and

• a programming language.

Knuth’s initial WEB used TEX as document formatting language and Pascal as programming language, but the idea is chiefly independent of the underlying languages.

A literate program is a combination of these two languages: commentary is written in the document formatting language, source code is written in the programming language. The WEB system itself only provides a small set of commands that allow the user to switch between these two languages and that identify the actual order of the source code making it possible for a normal compiler to handle it.

As implied by the last sentence, one main part of the WEB system is a routine that converts a literate program into a form, that a conventional compiler may understand; the converted code then may be compiled into a machine-executable program. This way of processing is called tangling the web and the corresponding system routine is called TANGLE. The second main line of processing converts the WEB into a high quality document that serves as a source code documentation. This line is called weaving the web, the system routine perfoming this task consequently WEAVE. These two lines of processing are visualized in figure 3.1.

As stated above, the idea of WEB is basically language independent. The past few years have seen many new WEB systems for a lot of different combinations of languages. Many of them have been inspired copies of Knuth’s initial Pascal-WEB, like for example CWEB [30] for C, C++ and TEX. As mentioned earlier there has also been a lot of disagreement on what exactly a WEB system must be able to do. This is mostly due to the language dependency of the weaving process.

Today one can see three main categories of WEB systems:

1. In this category you would find Knuth’s initial WEB system. The structure of the underlying languages are hard-wired into the implementation and the

[figure: .WEB; .PAS; .EXE; .TEX; .DVI; TANGLE; PASCAL- Compiler; WEAVE; TEX; Program; Document]

Figure 3.1: The two lines of processing in Knuth’s initial WEB system.

output (mostly in TEX) is of high quality and sees the program code beautifully prettyprinted. Moreover an index of identifiers is generated as well as a complex cross-reference of sections.

2. Here, the language dependencies are excluded from the actual TANGLE and WEAVE processors and put into modules. When writing a literate program the user can switch between programming languages and formatting languages by choosing the appropriate modules. An example for such a WEB system is FWEB by John Krommes [31].

3. This category collects all the WEB systems that are more or less programming language independent (L^{A}TEX is mostly used as document formatting language). Due to this independency, these WEB systems have no prettyprinting feature and are not able to generate indexes or cross references. Examples for these kinds of WEBs are funnelweb [54], noweb [45] and nuweb [7].

There is also a generator for WEB systems called SpiderWEB written by Norman Ramsey [44] that produces a category one-WEB. The Pretzel program was inspired very much by this approach (and this report also owes its title to Ramsey’s paper). However, Pretzel does not produce a whole functional WEAVE program, but generates only a prettyprinter. But because the prettyprinting is the most intricate part of the systems of categories one and two, it would not be a major problem to construct a WEB system around it. But as Pretzel produces a “prettyprinting block” for a specific programming language, the resulting WEB system would rather belong to category two.

The name “WEB” has different origins. Knuth writes: “I chose the name WEB partly because it was one of the few three-letter words of English that hadn’t already been applied to computers.” [28] Another source Knuth refers to is the name of the mother of Knuth’s wife, Wilda Ernestine Bates [26, p. 2]. Seriously, the name of the system and its subcomponents TANGLE and WEAVE is a reminiscence to the popular english proverb:

Oh, what tangled web we weave

? ? ? Specification  Maintenance Testing Implementation Design

Figure 3.2: Life-cycle coverage offered by the literate paradigm.

When first we practice to decieve.

3.1.2 The Literate Programming Paradigm and the Software Life Cycle

The WEB system was originally designed “for system programmers, not for high school students or for hobbyists” [28, p. 111]. This implies that the literate programming paradigm concentrates on the development and the documentation of actual system code [10, p. 55]. So when reviewing the software life cycle is becomes apparent, that literate programming covers only parts of it, namely the implementation and additionaly the final stage of maintenance (see figure 3.2).

Current examples of literate programs however feign that writing a literate program from scratch is a valid programming method; they do not properly emphasize the importance of formalized system specification and design. However the descriptive features that are inherent to the paradigm provide a strong bridge between specification, design and implementation. Thus it seems possible to integrate the literate paradigm much further into the software life cycle. This issue is a field of further research at the TH Darmstadt.

3.2 “Literate Software Management”

Software systems today run during their evolution through what is called a software life cycle. One iteration of this life cycle begins with the global aspects of the specification, goes through the system design and the implementation, runs through the testing phase and ends with the maintenace of the software system. As todays software continuously has to react to market or other changes, it is usual that such systems run through the software life cycle more than once.

Every phase of the life cycle has it’s own tools; most apparent are programming languages if you think of the implementation phase. However there also exist tools that help pipeline software systems through their life cycle, help to keep track of revisions, describe the overall structure of the system and so on. The comination of such tools is normally called a software management system.

As mentioned in the end of the previous section, the literate programming paradigm applies only to small parts of the software life cycle, namely those that are covered by the term programming in the small. However the literate paradigm also offers a lot of features that also seem usefull to the other parts of the software life cycle. The main features are as follows:

• Formal and informal description methods are combined leading to more readable text (the method of “saying everything twice”).

• Through the recording of subsequent changes during a phase and the description of alternatives in the informal text, design decisions become more

transparent and understandable.

• Additionally, information retrieval methods like index and cross reference may be a model for similar things on a larger scale.

Research is taking place at the TH Darmstadt to apply the benefits of literate programming to the whole software life cycle. This research runs under the title “Software als Buch. Methoden und Werkzeuge für das literarische Softwaremanagement” [12] (what may be translated as “Software as a Book. Methods and tools for literate software management”). A software management system is under development that incorporates “literate” features and shifts the whole management process to become literature itself; the software system becomes a software book, or better: a SoftBook.

The underlying model is based upon division of a so called depot and a workspace. The workspace supplies an environment of working on the software system no matter in what stage of the life cycle it should be. The depot provides a general (nonstandard) database that stores documents and system parts from all phases of the life cycle. These parts can therefore vary a lot: whilst system parts from the design phase may be written in a formal and abstract design language, other parts can be simple essays and others may consist of hard-core assembly code. All these parts are connected with each other as a hypertext.

3.3 The Role of Pretzel

In the so called workspace, the user may work on the software system in various ways: he might change the design, implement modules or just examine documents that belong to previous versions of the system. In all these cases the information that is stored in the depot has to be visualized on the screen. Thinking of the software system as a book, the output for the user hast to be of high quality and formal code should be formatted to local standards. Considering the large amount of possible languages that you may encounter in software development, you may not use a universal module for formatting. This is where the Pretzel program plays its role.

As shown above, it is possible to generate prettyprinting functions with Pretzel for a large variety of languages in fairly short time. These prettyprinting functions then may be turned into modules of the software management system that take over some of the “weaving” that is required to visualize the contents of the depot.

Anyway, with Pretzel it could be possible to build one’s personal WEAVE system rather easily, because the prettyprinting is the most intricate part of the weaving process. The only major thing left is to generate an index and the cross reference and to build the major frame. A simple approach would be to change the one existing WEB generator, namely the SpiderWEB system, and change it to use a Pretzel generated prettyprinter. Another possible way would be to build a prettyprinting back end for noweb that is language independent and uses the UNIX toolbox paradigm.

Prettyprinting will surely remain a major aspect of literate programming even though a lot of people do not believe in its worth. But, as Marc van Leeuwen puts it, it is a question of personal taste:

“Nevertheless I strongly disagree with people saying that pretty-printing is not worth the effort for anyone in general; this depends very much on ones particular situation and purpose. In some cases pretty-printing may even be the main reason to opt for literate programming.” [51]

The Design of the System

The idea behind the Pretzel program is not new. The way of using a prettyprinting grammar for formatting and the idea of generating a WEB system from a formal specifiacation of the underlying programming language have been presented by Knuth and Ramsey years ago. The new thing behind the Pretzel program is that it combines these two ideas to produce output that is useable in a lot of different fashions.

This chapter presents the evolution of the Pretzel program from its early design to the history of its implementation.

4.1 The Attribute Grammar

As said earlier, the main working mechanism of the generated prettyprinter is the use of an attribute grammar to build up prettyprinted code during a bottom-up parse of the programming language text. So one of the first steps was to look at a system that had implemented this already: Knuth’s initial WEAVE program and the CWEAVE program that is derived from it. The first bigger aim in this project was then to build a prototype prettyprinter that implemented this notion, using Bison and the semantic actions provided in it to put together the code using a set of specially designed functions from a run time library. In fact, it was the mere design of this run time library that took up the biggest part of the time in the design stage.

4.1.1 Attributes

The basic idea that was the starting point of the design was to provide a recursive data type that implemented attributes or translations of grammar tokens and could be used during parsing. This data type was to be called attribute and should be implemented using C++. An attribute could be recursively defined as follows:

• A simple string is an attribute.

• A format command is an attribute.

• Any combination of two or more attributes is again an attribute.

This definition resulted from hand-simulating the process done by Knuth’s WEAVE program on the blackboard and on notepaper. It seemed at first that it would be a good idea to implement attributes as a long linked list, because the result of the prettyprinting always appeared to be a long list of strings and format commands. Whenever a grammar rule was chosen, the attributes of the tokens were simply inserted into a new list that represented the attribute of the resulting token.

For efficiency reasons this idea was soon abandoned and the insertion of attributes was done by inserting references (visualized as long arrows on paper) into newly created attributes. The resulting structures looked very much like trees and the resulting output could be obtained with a simple tree traversion.

An abstract way of defining attributes using the C++ classes was to have one abstract base class, of which all of the three attribute types could be derived from, namely: strings, format commands and sequences of attributes. This was realized in the Attribute class. It provided three kinds of attributes, i.e. subtypes of Attribute:

1. Text attribute to store simple strings.

2. Format attribute to store format commands (implemented as an enumeration type).

3. Attributelist to store a sequence of objects of type Attribute (implemented as a linked list holding attribute pointers).

The recursive implementation is hidden elegantly in the definition of Attributelist, because such a list can contain any attribute, a string, a format command or simply again a list of such attributes.

The final thing concerning this class was to provide a set of useful functions to handle objects of this type. This set simply consisted of two functions, namely:

1. create() to create a Text attribute or a Format attribute from a simple string or the name of a format command.

2. join() to create an Attributelist from a sequence of attributes.

Note that both functions return valid attributes and thus can be used as arguments to each other. Using attributes in this fashion therefore creates the trees that appeared earlier on paper or on the blackboard automatically in the computer’s memory.

4.1.2 Outputting Attributes

Creating huge trees of attributes in memory would be useless unless there would be a possibility to get them out again and output them into a file or onto screen. As stated earlier this could be done by a simple tree traversion in pre-order. However, the object oriented approach that was built into the attributes now seemed to inhibit an easy way of doing this, since all of the nodes of the tree were simply of type Attribute and their initial subtype could not be retieved by simply looking at them. How do you know how to output an attribute, when you don’t know if it is a string, a format command or even a list of attributes?

The solution to this problem is really one of the most interesting parts of the whole program and gets to the actual core of “real” object oriented programming. The idea was to provide a public member function called print in each subclass of Attribute that would automatically output an object of its class in the right way, provided it was told where to put the output. This was the birth of the Output class. Objects of this class (“outputs”) can be used to output attributes.

An output is attached to a C++ ostream class object during creation. Any calls of the print member functions of attributes must say into which output they want to send their information. But the problem of calling the right kind of print function for every attribute is obsolete because of the built-in dynamic dispatch: every object knows its type and can therefore invoke its own specific member function. (Sending information to an output is done by taking the string or the format command out of the attribute and calling a special function do output of the output with this information.) The traversion is achieved by simply implementing the print function of the Attributelist as a subsequent invocation of the print functions of its members.

The output to which this stream of attributes is sent then has full control over the information flow before it sends it out to the ostream object to which it is connected. In fact, an output can do much more than merely directing information flow to a specific destination: it may also be used to do any kind of processing of the attribute information, such as interpreting the format commands and translating them into typesetter understandable format; or it can do the preprocessing that is caught by the two phrases on page 10, i.e. reducing a sequence of force commands to just one or handling the behaviour of the cancel command. The internal structure of each output just has to wait for subsequent calls of the do output function and handles the incoming information as it wishes.^{1}

Both the Attribute class and the Output class are the central and decisive part of the run time library. Attributes are used to build up the translations of tokens during parsing; Outputs are used to interpret and output these attributes to a given output stream.

4.2 The Structure of Pretzel

After designing and implementing the run time library for the generated prettyprinter all of the functions were tested thoroughly with a small prototype prettyprinter that could handle simple C code. The main result from this time of testing was that using attributes and outputs within semantic actions of a Bison grammar to generate prettyprinted output actually worked.

The next step was to think of a way of specifying a prettyprinting grammar in machine readable form that would be intuitive and similar enough to the way used by Knuth in his documentation to WEAVE. After sketching out some rough ideas I turned to actually defining Bison grammars to parse this notation and to translate this into valid flex and Bison files. This was the birth of the formatted token and the formatted grammar files and the functions that transform them into valid flex and Bison code.

The general idea of these functions is to transform a sequence like

    "begin"    BEG    {"\\&{begin}"}

into a line of flex like

    "begin"   {*rvalue=create("\\&{begin}"); return(BEG);}

where *rvalue stores the semantic value of the token and is of type Attribute∗. A declaration in the formatted grammar file like

    block  : BEG stmt_list END    {$1 + $2 + force + $3}
    ;

should be transformed into lines of Bison input as in:

    block  : BEG stmt_list END    {$$=join($1,$2,create(force),$3);}
    ;

It is again an astonishing point to see the universality of the Attribute class. Designed for building up attributes during parsing within the prettyprinter, they suddenly were used to generate the code put into the flex and Bison files.

The result of all this coding were two generators (see also figure 4.1):

1Unfortunately this causes the Output class to neglect the fundamental modularity of modern prettyprinters as described in chapter 1. See chapter 5 (future work) for more on this topic.

• A build pscan function that reads a formatted token file from an istream class object, parses and translates the contents of the file and writes to an ostream class object the generated code of a prettyprinting scanner. This scanner acts in the way that was specified in the input.

• A build pparse function that reads a formatted grammar file from an istream and writes a Bison source for a prettyprinting parser to an ostream. This parser acts in the way specified in the input.

[figure: file; prettyprinting scanner; flex source for; prettyprinting parser; Bison source for; .fg; file; .ft; build pparse(); pretzel; build pscan()]

Figure 4.1: The two generator functions within Pretzel.

The translated code not only consists of the pure flex and Bison definitions for the prettyprinting grammar, but also contains the code for the actual prettyprinting functions, that were the major goal of this project. These two functions do the main work of Pretzel.

The last step of this project was then to write the actual Pretzel program. It simply does nothing else but to form a nice user interface to the two parser functions. See figure 4.2 for an overview over the dependency structure of the modules involved in Pretzel.

4.3 History

The design phase began very much in the beginning of 1993 with an analysis of the sourcecode of Knuth’s Pascal WEAVE program. In May 1993 I had designed a prototype prettyprinter for simple C code that simulated very much the kind of prettyprinter that Pretzel should generate. After testing and playing around with it, the second and last step could begin.

In June 1993 I thought of a way to specify a prettyprinting grammar that would be easy to read and easy to parse. At this point the prettyprinting scanners and parsers emerged. As mentioned earlier they themselves were written in flex and Bison and use the Attribute class during code generation.

Finally I had only to write a main program that would invoke these two parsers and write the generated code into files. I began coding this program in July 1993 and called it Pretzel. The final revisions are documented in the diary file that is part of the Pretzel distribution.

[figure: .ft; files; ftscan.h; ftparse.h; generator for the; prettyprinting scanner; prettyprinting parser; generator for the; fgparse.h; .fg; files; fgscan.h; scanner for; scanner for; run time library:; pretzel.w; attr.h; Attribute class; output.h; Output class; format command definitions; functions create() and join(); .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .]

Figure 4.2: The dependency structure of the modules of Pretzel.

Future Work

After having finally implemented and tested the Pretzel program I have noticed, that the program doesn’t do very much at all, although it suits the specifications that belonged to this project. To enjoy beautifully formatted source code you still have to construct your prettyprinting grammar. As is seems, the work of fine tuning such a grammar that the prettyprinter is able to handle the last formatting detail you desire is quite tedious and time-consuming, especially if you start to build your grammar from scratch. But after constructing such a grammar for Pascal and applying it to a few everyday-example Pascal source codes, I was astonished how easy it was to change the looks of the prettyprinted text. I think that starting with a formal grammar of your favourite language and trying to enhance it and transform it into a prettyprinting grammar is surely a better way to reach your goal. I suppose that the Pretzel program could be the right tool to help you with this task.

However, since only few people have used Pretzel until today there will surely be a lot of things people miss when using the program. Now I will list a number of omissions that I have thought of during the last phase of the implementation. I have listed them in order of increasing severity.

Allow /*… */ comments. In places where the user has an empty production in the formatted grammar file or an empty token definition in the formatted token file file, it would be nice to have a C like commenting feature with opening and closing delimiters. The ‘//’ comment delimiter isn’t nice if you want to add an attribute definition to an empty production.

Copy comments. It surely would make the generated flex and Bison files more readable, if Pretzel would copy the comments from the formatted token and the formatted grammar files into them.

Generate %token definitions. If one would impose the restriction to use only uppercase identifiers as terminal token names Pretzel could automalically generate the list of %token definitions needed to identify terminals in the formatted grammar file.

Using more than one prettyprinter at the same time. This problem is closely related to the question whether you can use two seperate Bison parsers in your program. As this is the case in newer versions of Bison using more than one prettyprinter at the same time should be possible. However, you have to use the relevant Bison options to enable this and it would be nice to circumvent these problems in a nicer way.

Include code in attribute definitions. If you want to generate an index of identifiers during the prettyprinting and you don’t want to do this through text markup, one would have to have a way of smuggling additional C code into the actions of the flex and/or Bison files. A clean way of doing this would be to include the code in the formatted token and formatted grammar files using special delimiters like ‘[[’ and ‘]]’ that normally don’t appear in todays programming languages.

Change prettyprinting grammar format. It would be nice to be able to insert format commands directly into the grammar rules, like for example in:

  WHILE expr DO indent stmt outdent force ⟶ stmt

This is a point that effects fundamentals of the build pparse function. Other parts of Pretzel are not involved. This is a change that would be good for new users, since this way of specifying the grammar is much more intuitive.

Allow changing output formats. To present, the Output class that does all the interpretation of the format commands exists only in a version that produces TEX text. Though it is easy to change the implementation and thus the interpretation of the output class, it would be nice to be able to have a library of different output versions that can be chosen from at run-time. So if you want to prettyprint code with a prettyprinter, you not only mention in- and output streams, but also how the format commands could be interpreted.

Joachim Schrod suggested to design a new C++ class for this purpose called “Interpretation” or something similar. There should be a default interpretation as abstract base class (what would it look like?) and subsequent interpretation versions would be derived from this standard. The prettyprinting function would then turn to

void myparse (istream∗,Interpretation, ostream&);

Include files for grammars. As parts of prettyprinting grammars occur frequently in many different programming languages (such as the formatting of expressions) it would be nice to be able to include files that contain these definitions with a simple command in the formatted token and formatted grammar files. On a more abstract level one could think of a notion of modules of grammars, i.e. parts of a grammar that can be called with arguments to suit local demands (“grammar templates”?). But it is still an unanswered question whether this is practical, because of the lack of method to specify the interface of such a module.

Looking back at the project it is quite striking why the prettyprinter generated by pretzel is not built in a modular kind of fashion that is described in chapter 1 and visualized in figure 1.2 on page 15. This lack of modularity possibly has something to do with the fact, that chapter 1 was written after the project was in the design phase. But this lack of modularity has the advantage of not having to define the interface between the language dependent front end and the language independent back end, as this part is hidden within the Output class (see figure 5.1 on page 45 for how the Pretzel prettyprinter fits into this scheme). This makes the implementation more efficient but less understandable. The extension proposed in the above list to introduce “interpretations” would possibly only blur the concept further. A new design, based on the fundamental distinction of modules, seems a little more promising to me. It is clear that still a lot of work has to be done.

[figure: .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; unformatted source code; typeset document; complex attribute; prettyprinter; text with markup; prettyprinting scanner; prettyprinting parser; flex/Bison generated functions:; preprocessing of format commands; attribute traversal; transformation into strings; output object:; formatting algorithm; document formatter (TeX):; language independent back end; language dependent front end]

Figure 5.1: How the prettyprinter generated by Pretzel fits into the module structure of modern prettyprinters.

Acknowledgements

I have to thank Joachim Schrod for his time and lasting inspiration on this subject. Also thanks to U. Freiling for her continuous support during the time it took me to finish this project. And of course thanks to Donald Knuth for the idea of literate programming.

Appendix

Specifications

Included in this report are the specifications of the following modules:

• The Attribute class and the Output class from the run-time library.

• The scanners for the formatted token and formatted grammar files.

• The generator functions build pscan and build pparse for the prettyprinting scanner and parser.

• The generated prettyprinting scanner (default header file).

• The generated prettyprinting parser (default header file). Unfortunately I was unable to provide correct page numbers to these parts of the report. However, the bibliography and the index at the end are numbered correctly again.

Bibliography

[1] M. Arab. Enhancing program comprehension: formatting and documenting. ACM SIGPLAN Notices, 27(2):37–46, February 1992.

[2] P. A. Bailes and A. Salvadori. A semantically-based formatting discipline for Pascal. Software — Practice & Experience, 14(3):235–251, March 1984.

[3] R. M. Bates. A Pascal prettyprinter with a different purpose. ACM SIGPLAN Notices, 16(3):10–17, March 1981.

[4] Jon Bentley. Programming pearls—literate programming. Communications of the Association for Computing Machinery, 29(5):364–369, May 1986.

[5] G. Blaschek and J. Sametinger. User-adaptable prettyprinting. Software — Practice & Experience, 19(7):687–702, July 1989.

[6] R. Bond. Another note on Pascal indentation. ACM SIGPLAN Notices, 14(12):47–49, December 1979.

[7] Preston  Briggs.  Nuweb,

A simple literate programming tool. cs.rice.edu:/public/preston, Rice University, Houston, TX, 1993.

[8] H. M. Clifton. A technique for making structured programs more readable. ACM SIGPLAN Notices, 13(4):58–63, April 1978.

[9] K. Conrow and R. G. Smith. NEATER2: A PL/I source program reformatter. Communications of the ACM, 13(11):669–675, November 1970.

[10] David Cordes and Marcus Brown. The literate-programming paradigm. Computer, 24(6):52–61, June 1991.

[11] J. Crider. Structured formatting of Pascal programs. ACM SIGPLAN Notices, 13(11):15–22, November 1978.

[12] Christine Detig. SoftBook. Methoden für das literarische Softwaremanagement. TH Darmstadt, November 1992.

[13] P. Fritzson. Adaptive prettyprinting of abstract syntax applied to Ada and Pascal. Research report, University of Linköping, Sweden, 1983.

[14] I. Goldstein. Prettyprinting, converting list to linear structure. Technical Report 279, M.I.T. Artificial Intelligence Laboratory, Cambridge, Mass., 1973.

[15] P. Grogono. On layout, identifiers and semicolons in Pascal programs. ACM SIGPLAN Notices, 14(4):35–40, April 1979.

[16] P. Grogono. Comments, assertions, and pragmas. ACM SIGPLAN Notices, 24(3):79–84, March 1989.

[17] G. G. Gustafson. Some practical experiences formatting PASCAL programs. ACM SIGPLAN Notices, 14(9):42–49, September 1979.

[18] A. C. Hearn and A. C. Norman. A one-pass prettyprinter. ACM SIGPLAN Notices, 14(12):50–58, December 1979.

[19] R. Heckert. A Pascal indentation philosophy. Computer Language, pages 37–39, September 1985.

[20] Jon Hueras and Henry Ledgard. An automatic formatting program for PAS-CAL. ACM SIGPLAN Notices, 12(7):82–84, July 1977.

[21] M. Jackel. A formatting parser for Pascal programs. ACM SIGPLAN Notices, 15(7–8):58–63, July–August 1980.

[22] K. Jensen and N. Wirth. PASCAL — User Manual and Report. Springer, third edition, 1985.

[23] M. O. Jokinen. A language-independent pretty printer. Software — Practice & Experience, 19(9):839–856, September 1989.

[24] M. J. Kaelbling. Programming languages should NOT have comment statements. ACM SIGPLAN Notices, 23(10):59–60, October 1988.

[25] D. E. Knuth and M. F. Plass. Breaking paragraphs into lines. Software — Practice & Experience, 11:1119–1184, 1981.

[26] Donald E. Knuth. The WEB system of structured documentation. Stanford Computer Science Report CS980, Stanford University, Stanford, CA, September 1983.

[27] Donald E. Knuth. The TEXbook, volume A of Computers and Typesetting. Addison-Wesley, Reading, Massachusetts, 1983.

[28] Donald E. Knuth. Literate programming. The Computer Journal, 27(2):97– 111, May 1984.

[29] Donald E. Knuth. TEX: The Program, volume B of Computers & Typesetting. Addison-Wesley, Reading, MA, USA, 1986.

[30] Donald E. Knuth and Silvio Levy. The CWEB System of Structured Documentation, Version 3.0. Addison-Wesley, Reading, MA, USA, 1993.

[31] John Krommes. FWEB (Krommes) vs. FWEB (Avenarius and Oppermann). TEXhax, 90(19), February 1990.

[32] H. Ledgard, A. Singer, and J. Hueras. A basis for executing PASCAL programmers. ACM SIGPLAN Notices, 12(7):101–105, July 1977.

[33] Henry F. Ledgard. Programming Proverbs. Hayden, Rochelle Park, New Jersey, 1975.

[34] D. W. Leinbaught. Indenting for the compiler. ACM SIGPLAN Notices, 15(5):41–48, May 1980.

[35] D. Marca. Some Pascal style guidelines. ACM SIGPLAN Notices, 16(4):70–80, April 1981.

[36] P. Mateti. A specification scheme for indenting programs. Software — Practice & Experience, 13:163–179, 1983.

[37] William M. McKeeman. Algorithm 268. Communications of the ACM, 8:667– 668, 1965.

[38] Patricia R Mohilner. Prettyprinting PASCAL programs. ACM SIGPLAN Notices, 13(7):34–40, July 1978.

[39] Peter Naur et al. Report on the algorithmic language Algol 60. Communications of the ACM, 3(5):299–314, May 1960.

[40] D. Norris. An Ada prettyprinter. Journal of Pascal and Ada, 3(4):29–48, April 1984.

[41] Derek C. Oppen. Prettyprinting. ACM Transactions on Programming Languages and System, 2(4):465–483, October 1980.

[42] James L. Peterson. On the formatting of Pascal programs. ACM SIGPLAN Notices, 12(12):83–86, December 1977.

[43] J. Ramsdell. Prettyprinting structured programs with connector lines. ACM SIGPLAN Notices, 14(9):74–75, September 1979.

[44] Norman Ramsey. Weaving a language-independent WEB. Communications of the Association for Computing Machinery, 32(9):1051–1055, September 1989.

[45] Norman Ramsey. Literate-programming tools need not be complex. Re-

port at ftp.cs.princeton.edu in /reports/1991/351.ps.Z. Software at
ftp.cs.princeton.edu in /pub/noweb.shar.Z and at bellcore.com in

/pub/norman/noweb.shar.Z. CS-TR-351-91, Department of Computer Science, Princeton University, August 1992. Submitted to IEEE Software.

[46] Frederic Richard and Henry F. Ledgard. A reminder for language designers. ACM SIGPLAN Notices, 12(12):73–83, December 1977.

[47] P. N. Rorbillard. Automating comments. ACM SIGPLAN Notices, 24(5):66– 70, April 1989.

[48] G. A. Rose and J Welsh. Formatted programming languages. Software — Practice & Experience, 11:651–669, 1981.

[49] Lisa F. Rubin. Syntax-directed pretty printing — a first step towards a syntaxdirected editor. IEEE Transactions on Software Engineering, SE-9(2):119–127, March 1983.

[50] R. Scowen, D. Allin, A. L. Hillman, and M. Shimell. SOAP – A program which documents and edits Algol60 programs. The Computer Journal, 14(2):133–135, 1971.

[51] Marc van Leeuwen. Differences between CWEB and WEB prettyprinting grammars. Posting in comp.programming.literate, February 1995. Correct subject header might be different.

[52] R. Waters. User format control in a LISP prettyprinter. ACM Transactions on Programming Languages and Systems, 5(4):513–531, October 1983.

[53] R.C. Waters. Using the new common LISP pretty printer. Lisp and Symbolic Computation, V(2):27–34, April–June 1992.

[54] Ross Williams. FunnelWeb user’s manual. ftp.adelaide.edu.au in /pub/compression and /pub/funnelweb, University of Adelaide, Adelaide, South Australia, Australia, 1992.

[55] K. Winter and C. Cook. A prototype intelligent prettyprinter for Pascal. ACM SIGPLAN Notices, 24(9):116–125, September 1989.

[56] M. Woodman. Formatted syntaxes and Modula-2. Software — Practice & Experience, 16(7):605–626, July 1986.

[57] A. Yehudai. Automatic indentation versus program formatting. ACM SIG-PLAN Notices, 15(10):85–87, 1980.

Index

/*… */ comments, 43 // comments, 43 [[…]] delimiters, 44

ACM, 12, 33 Ada, 5 “adaptive combs”, 17 Additional spacing, 12 Algol, 5, 12 Algorithm-policy distinction, 13 Assembler like command set, 16 Attribute class, 21 Attribute grammar, 11 Automatic typesetting, 5

Back end, 13 backup, 9, 16 Basic actions of prettyprinters, 12 Bates, Wilda Ernestine, 35 Beauty, 12 Bentley, Jon, 33 big force, 9, 16 Bison, 20, 25

-d option, 26 using more than one parser, 43

Bison input, 26 Blaschek, G., 13, 17 break space, 8 build pparse, 44

C, 9, 16, 24, 44 C preprocessor, 9 C++, 9, 16, 19, 20, 24, 25 cancel, 10, 16 “case” construct, 12 Changing output formats, 44 Classes of comments, 17 Command set

assembler like, 16 convenient, 16 sufficiency, 9, 15 sufficient, 16

Comments, 17

in Pretzel input files, 24 Common token header file, 26 Communication protocol, 13 Compilers

and prettyprinters, 6 for documents, 6

Connector lines, 12 Context free grammar, 11, 16, 23 Context sensitive formatting, 17 Context sensitive grammar, 27 Control sequences, 6 Controlling line breaks, 7 Convenient command set, 16 Conventions, 22

of typesetting, 6 Cook, C., 17 Copy comments, 43 Coroutines, 13

CWEAVE, 38
CWEB, 27
cwebmac, 27

-d option of Bison, 26 Darmstadt, 31, 36 Debugging the prettyprinting gram-

mar, 26 Deflating prettyprinting grammars, 16 Design phase, 44 Details

nitty gritty, 6 Document compilers, 6

Early prettyprinters, 12 Editors

syntax directed, 14 Empty tokens, 43 Equality, 17 Example grammar, 27 Exceptions, 10 Explicit format commands, 13 Exposition and excellence of style, 33

.fg suffix, 22, 25 FIFO buffer, 13 File formats, 22 Filename conventions, 22 flex, 20, 25 flex input, 26 Flexibility, 10 Folding, 12, 14 Folding algorithm (Rose and Welsh),

14 force, 7 Forced line break, 7 Formal methods, 14 Format commands, 13

backup, 9, 16 big force, 9, 16 break space, 8 cancel, 10, 16 explained, 5–10 explicit, 13 force, 7 implicit, 13 indent, 7 no indent, 9, 16 null, 10 opt, 9 outdent, 7 summary, 10

Formatted grammar file, 20, 23 Formatted token file, 20, 22 Formatting algorithm, 13 Formatting algorithms, 5 Formatting policy, 13, 14 Formatting standards, 5 “free format” languages, 5 Front end, 13 .ft suffix, 22, 25 Funnelweb, 35 Future work, 43

FWEB, 35

Grogono, P., 17 Guidelines (Rose and Welsh), 14

Header file

of Pretzel prettyprinter, 26 Hearn, A. C., 12, 13 History of prettyprinting, 12 Horizontal spacing, 17

Implicit format commands, 13 In-text procedural markup, 6 Include files for grammars, 44 Including C code into rules, 44 indent, 7 Indentation, 12

controlling amount of, 7 Indenting programs, see Prettyprint-

ers Inituitive grammar format, 44 Intelligent prettyprinter, 17 Interface of the scanner, 21 Interpretation, 44 Interpretation of format commands, 6

Jackel, M., 17

Kaelbling, M. J., 17 Kellington, Myrtle, 12 Knuth, Donald E., 3, 6, 7, 11, 13, 14,

16, 27, 33, 35, 38 command set by, 6

Krommes, John, 35

.l suffix, 25 .l file, 26 Lack of modularity, 44 Language (in)dependence, 13 Language dependent front end, 13 Language independent back end, 13,

14, 44 L^{A}TEX, 35 Ledgard, Henry F., 5 Leeuwen, Marc van, 37 Levy, Silvio, 13 Lexical level, 16 Life cycle, 36 Line breaks

controlled, 7 Linked folds, 17 Lisp, 5, 12 Literate programming, 3, 33 Long chapter, 18 Long names

extremenly, 7

Makefile, 25

Markup, 6, 16 Mateti, P., 14 McKeeman, William, 12 Metasyntax (Rose and Welsh), 14 Modula-2, 17 Modularity, 15 Mohilner, Patricia R., 17

myparse.c, 26
myscan.c, 26

Naur, Peter, 12 Necessary command set, 16 New design, 44 Nitty-gritty details, 6 “No”, 15 no indent, 9, 16 “normal” interpretation, 6 Norman, A. C., 12, 13 Noweb, 35 Nroff, 6 null, 10 Nuweb, 35

Omissions, 43 Oppen, Derek C., 13, 14 opt, 9 opt and break space, 9 Optional line-break, 9 Options of Pretzel, 26 outdent, 7

P, 19 Parse tree, 13 Pascal, 5–7, 11, 12, 14, 19, 22, 24,

27, 31, 34, 43 Personal taste, 4, 5 PL/I, 5, 12 Policy-algorithm distinction, 13 POSIX, 20 “postcomments” (Rose and Welsh), 17

PPARSE NAME, 27

“precomments” (Rose and Welsh), 17 Preprocessing of format commands, 10 Preprocessor, 9 “preprocessor” for prettyprinting, 13 Prettprinting scanner, 20 Prettyprinter

example, 27 first, 12 header file, 26 intelligent, 17 token header file, 26

Prettyprinters basic actions, 12 early systems, 12 for other languages, 5 running on keywords, 12

Prettyprinting, 4, 5, 34 history, 12 language (in)dependence, 13 problems, 16

Prettyprinting grammar

include files, 44 Prettyprinting grammar, 10, 11, 43,

44 and comments, 17 deflating, 16

Prettyprinting parser, 20 Prettyprinting problems

worst and oldest, 17 Pretzel, 4, 43 concept, 19 options, 25, 26

Procedural markup, 6, 16 Program formatting, 5 Programming paradigm, 33

PSCAN NAME, 27
PSCAN NAME INIT, 27

Pseudo tokens, 11

ptokdefs.h, 26
PTOKDEFS NAME, 27

Ramsey, Norman, 35 Refinements, 34 Reuseability, 15 Rigid formatting rules, 14 Rose, G. A., 14, 16, 17 Rubin, Lisa F., 13, 16

Sametinger, J., 13 Sarcasm, 33 “scoped comments” (Kaelbling), 17 Second class citizens, 17 Separation of concerns, 13 Software life cycle, 36 Software management systems, 36 Spacing

additional, 12 horizontal, 17 horzontal, 16 vertical, 16

“special markers”, 13 Spiderweb, 35 State of the art, 14 Sufficiency of command set, 15 Sufficient command set, 16 Summary of format commands, 10 Syntax-directed editors, 14

Tags, 6 Taste

personal, 5 TEX, 5, 6, 14, 27, 34, 44 %token definitions, 43 Token header file, 26 Tooth, 17 Tradition, 12 Translation, 11, 12 Tricky details, 10 Triumvirate, 7 Troff, 6 Typesetters, 3, 5 Typesetting systems, 5 Typesetting comments, 17 Typesetting conventions, 6 UNIX, 6 User control, 16 User’s manual, 19

Violation of syntax, 7

WEAVE, 3, 6, 27, 38 WEB, 14, 34

name of, 35 Welsh, J., 14, 16, 17 Winter, K., 17 Woodman, M., 14, 17 Work

a lot of, 44 “works of literature”, 33

.y suffix, 25 .y file, 26 Yehudai, A., 16

yydebug, 26