Unparsing Expressions with Prefix and Postfix Operators

Norman Ramsey


Automatic generation of computer programs from high-level specifications is a well-known technique, which has been used to create scanners, parsers, code generators, tree rewriters, packet filters, dialogue handlers, machine-code recognizers, and other tools. To make it easier to debug an application generator, and to help convince prospective users that the generated code can be trusted, the generated code should be as idiomatic and readable as possible. It is therefore desirable, and sometimes essential, that the generated code use infix, prefix, and postfix operators, and that they be presented without unnecessary parentheses. Another helpful technique is to use a prettyprinter to automate indentation and line breaking. This paper presents a method of automatically parenthesizing expressions that use prefix, postfix, and implicit operators; the method is compatible with automatic prettyprinting. The paper also shows how to parse expressions that use such operators. The parsing algorithm can be used even if operator precedences are not known at compile time, which means that it can be used with an arbitrary number of user-defined precedences.

The full paper is available in technical-report form as PostScript (370K), or you can see a scanned reprint in DjVu (2.2M).

You can download the ML code.