Parse tree annotations

Reviewer: David Thomas Barnard

The authors present a technique for associating translation rules with the productions of a grammar and give some applications of the kinds of translations that can be produced. Their technique is not as powerful as methods based on attribute grammars, but its virtue is its simplicity. The paper has two explicit goals: to illustrate the notation in a variety of applications and to show how the approach can be used in conjunction with tools in a programming environment. The system described is a modification of yacc —it allows the parse tree to be retained and rules for transducing the source program to be associated with the parse tree. The rules are actually associated with each production of the grammar, and several different rules, distinguished by identifiers, can be associated with a production. Although the authors do not give the details of the language used in the translation rules, examples show reordering, selecting only parts of the subtree to be examined, and conditional application of rules. It is possible to introduce variables, essentially attached to nodes of the parse tree, that can be assigned values and referenced as the subtree rooted at the node is processed. The authors show applications for reordering an expression (infix to postfix), generating execution profiles of programs, generating output for a tool that can display the execution of a program on a statement-by-statement basis, and generating other source notations for parts of a program (a module “outline”). Readers should be prepared to struggle with a presentation that could have been improved by more careful editing and proofreading. Better editing would have eliminated a few pronouns with ambiguous antecedents and a small number of missing referents. The authors should have added a sentence or two to describe details that are used in some examples without explanation (for example, the NULL translation used in Figure 3, the “$$” notation in yacc rules). The paper contains a few typographical errors: “$” appears instead of “$1” in the rule for addition on page 1469 and in Figure 4; a bad line break occurs in the literal for a single break on page 1469; a grammar example on page 1469 uses two single quotes where other examples use double quotes; Figure 2 uses two different types of mark for the same kind of string; references to Figures 12 and 13 are interchanged; and reference 4 contains a misspelling. The authors have also made some choices that obscure the presentation. The symbol “$” is used in yacc rules, but their new translation rules use “#” for the same purpose; they give no reason for this change. Figure 11 introduces a new program in a new language rather than using the example already under discussion; and Figure 13 introduces a notation that at best obscures the point being made, because the notation is not explained and the example introduces details that are not present in the program from which it is derived. The paper achieves its goals, and I recommend it to readers interested in developing suites of tools based on program transformations. The techniques could probably be applied to sources other than programs, such as documents with formal descriptions, but the authors do not address this topic.