Tree Description Language (TreeDL) is a
computer language
A computer language is a formal language used to communicate with a computer. Types of computer languages include:
* Software construction#Construction languages, Construction language – all forms of communication by which a human can Comput ...
for description of strictly-typed
tree data structures and operations on them. The main use of TreeDL is in the development of language-oriented tools (
compiler
In computing, a compiler is a computer program that Translator (computing), translates computer code written in one programming language (the ''source'' language) into another language (the ''target'' language). The name "compiler" is primaril ...
s, translators, etc.) for the description of a structure of
abstract syntax tree
An abstract syntax tree (AST) is a data structure used in computer science to represent the structure of a program or code snippet. It is a tree representation of the abstract syntactic structure of text (often source code) written in a formal ...
s.
Tree description can be used as
* a documentation of interface between
parser
Parsing, syntax analysis, or syntactic analysis is a process of analyzing a string of symbols, either in natural language, computer languages or data structures, conforming to the rules of a formal grammar by breaking it into parts. The term '' ...
and other subsystems;
* a source for generation of data types representing a tree in target programming languages;
* a source for generation of various support code:
visitor
A visitor, in English and Welsh law and history, is an overseer of an autonomous ecclesiastical or eleemosynary institution, often a charitable institution set up for the perpetual distribution of the founder's alms and bounty, who can interve ...
s, walkers,
factories
A factory, manufacturing plant or production plant is an industrial facility, often a complex consisting of several buildings filled with machinery, where workers manufacture items or operate machines which process each item into another. Th ...
, etc.
TreeDL can be used with any
parser generator
In computer science, a compiler-compiler or compiler generator is a programming tool that creates a parser, interpreter, or compiler from some form of formal description of a programming language and machine.
The most common type of compiler- ...
that allows custom actions during parsing (for example,
ANTLR
In computer-based language recognition, ANTLR (pronounced ''antler''), or ANother Tool for Language Recognition, is a parser generator that uses a LL(*) algorithm for parsing. ANTLR is the successor to the Purdue Compiler Construction Tool Set ...
,
JavaCC).
Language overview
Tree description lists the node types allowed in a tree. Node types support
single inheritance
Multiple inheritance is a feature of some object-oriented computer programming languages in which an object or class can inherit features from more than one parent object or parent class. It is distinct from single inheritance, where an object o ...
. Node types have children and attributes. Children must be of defined node type. Attributes may be of primitive type (numeric, string, boolean), enum type or node type. Attributes are used to store literals during tree construction and additional information gathered during tree analysis (for example, links between reference and definition, to represent
higher-order abstract syntax
In computer science, higher-order abstract syntax (abbreviated HOAS) is a technique for the representation of abstract syntax trees for languages with variable name binding, binders.
Relation to first-order abstract syntax
An abstract syntax is ' ...
).
Operations over a tree are defined as
multimethods. Advantages of this approach are described in the articl
Treecc: An Aspect-Oriented Approach to Writing Compilers
Tree descriptions support inheritance to allow modularity and reuse of base language tree descriptions for language extensions.
See also
*
ANTLR
In computer-based language recognition, ANTLR (pronounced ''antler''), or ANother Tool for Language Recognition, is a parser generator that uses a LL(*) algorithm for parsing. ANTLR is the successor to the Purdue Compiler Construction Tool Set ...
- parser generator that offers a different approach to tree processing: tree grammars.
*
SableCC
SableCC is an open-source compiler generator (or interpreter generator) in Java. Stable version is licensed under the GNU Lesser General Public License (LGPL). Rewritten version 4 is licensed under Apache License 2.0.
SableCC includes the followin ...
- parser generator that generates strictly-typed
abstract syntax tree
An abstract syntax tree (AST) is a data structure used in computer science to represent the structure of a program or code snippet. It is a tree representation of the abstract syntactic structure of text (often source code) written in a formal ...
s.
References
External links
*
old TreeDL home* {{webarchive , url=https://web.archive.org/web/20070703044959/http://www.southern-storm.com.au/treecc.html , date=July 3, 2007 , title=treecc
Programming languages
Domain-specific knowledge representation languages