A regular tree grammar defines a regular tree language. Regular tree grammars are widely applied as tools in formal reasoning, but in practice the basic formalism is hidden in languages designed at human users. The *RTG* language is a little language that just contains the constructs of the clean formalism. The language is probably best introduced by a tiny example: regular tree grammar start Exp productions Var -> Var () Exp -> Int () | Times (Exp, Exp) | Plus (Exp, Exp) | Call (Var, ExpList) ExpList -> (Exp, ExpList) | () A regular tree grammar consists of a list of start non-terminals and a list of productions. The list of start non-terminals defines what non-terminals are allowed at the root of tree in the language defined by this RTG. The productions specify the terms that can be produced for a certain non-terminal. The left-hand-side of a production is non-terminal, the right hand side is a term that can contain non-terminals. Formally, a regular tree grammar consists of: * An unranked alphabet of non-terminals: N * A ranked alphabet of terminals: T * A set of start symbols S, which is a subset of N * A set of productions of the form N -> t, where t is an element of the set of ground terms over T union N. For more formal discussion on tree grammars and tree languages see [[Thttp://www.grappa.univ-lille3.fr/tata/][Tree Automata Techniques and Applications]] or [[ConnectingXMLProcessingAndTermRewritingWithTreeGrammars][Connecting XML Processing and Term Rewriting with Tree Grammars]]. Notice that the regular tree grammar shown above contains a few constructs between angle brackets: =<cons>=, =<nil>=, =<string>=, and =<int>=. The first two are built-in _terminals_ for representing lists. The last two are built-in non-terminals for strings and integers. See also: * [[StrategoRegular][stratego-regular]] (the subpackage of StrategoXT that implements RTG)