Syn: A Single Language for Specifying

Abstract Syntax Trees, Lexical Analysis,

Parsing and Pretty-Printing?

Richard J. Boulton

University of Cambridge Computer Laboratory

New Museums Site, Pembroke Street

Cambridge CB2 3QG, United Kingdom

March 1996

Abstract

A language called Syn is described in which all aspects of context-free syntax can be specified without redundancy. The language is essentially an extended BNF grammar. Unusual features include high-level constructs for specifying lexical aspects of a language and specification of precedence by textual order. A system has been implemented for generating lexers, parsers, pretty-printers and abstract syntax tree representations from a Syn specification.

1 Introduction

Syn is a language for specifying the syntax of computer languages. Lexical analysis, parsing, pretty-printing, and abstract syntax trees can all be specified in a single compact notation similar to Backus-Naur Form (BNF) grammars. However, the language is not as flexible as individual languages for specifying parsers, etc. The intention is to have a concise specification of syntax with sufficient flexibility and expressive power to be useful for a significant range of realistic languages. The main reason for having a single language is to eliminate redundancy and the consequential difficulty in maintaining consistency. The most notable features of Syn are:

?Research supported by the Engineering and Physical Sciences Research Council of Great Britain under grant GR/J42236.