Parse Tree Notation

Keywords: grammars.

Parse Tree Notation (PTN) facilitates the encoding of language translators which transform programs written in high level languages with extensions (e.g. a logic language with functional programming features) into equivalent programs in the original unextended languages (e.g. Prolog). PTN does this by offering a small set of operations and built-in predicates for manipulating program parse trees. More complicated actions can be readily coded by combining PTN with Prolog predicates.

The main PTN operation augments unification with pattern matching capabilities based on the Definite Clause Grammar (DCG) for the language of the program being manipulated. This allows parse tree searches to be specified, based on the terminal and nonterminal types of the language, without the programmer having to augment the DCG or to write specialised tree manipulation predicates.

The PTN system is available by anonymous FTP from:
ftp://turiel.cs.mu.oz.au/pub/ptn
The directory contains two files: README and ptn.tar.Z

There are numerous example translators in the distribution, including:

• a translator for a simple functional LP language
• a translator for a LP language with modules
• a text analyser for grades
• a translator for an if-then rule-based system
• a text analyser for phone lists
• a translator for a LP language with attribute/name arguments
• a translator that adds proof tree arguments to programs

PTN notation in a translator is itself translated into vanilla Prolog using a PTN translator.

A Postscript version of the paper `Parse Tree Notation', by A. Davison and E. Haywood is included with the distribution. This paper, combined with the numerous README files, supplies extensive information on the capabilities of PTN.

PTN is implemented in NU-Prolog, but mostly uses ISO-standard Prolog built-ins. There is a small file containing NU-Prolog specific predicates, and these should be easily ported to your Prolog dialect.

For more information, contact:

Andrew Davison or Elizabeth Haywood
Dept. of Computer Science
University of Melbourne
Melbourne, Victoria 3052, Australia
Email: ad@cs.mu.oz.au,
       lizh@cs.mu.oz.au
Fax: +61 3 348 1184
Tel: +61 3 287 9172 / 9101
Telex: AA 35185