tree grammar

Show Summary Details

Quick Reference

A generalization of the notion of grammar, applying to trees (often called terms in this context) rather than strings (see tree language). A regular tree grammar is the corresponding generalization of the notion of regular grammar. Productions have the form At, where A is a nonterminal and t a term, e.g. Sh(a,g(S),b) | c These productions generate the regular tree language shown in the diagram. Note that the frontiers of these trees are the strings shown below each tree in the diagram. A set of strings is context-free if and only if it is the set of frontiers of the trees in a regular tree language.


Sh(a,g(S),b) | c

The notion of context-free grammar can be similarly generalized. This time nonterminals can themselves be function symbols having an arbitrary number of arguments, e.g. F(x1,x2) → f(x2,F(x1,g(x2))) | h(x1,x1,x2) This means, for example, that F(a,b) could be rewritten to f(b,F(a,g(b))), and then to f(b,f(g(b),F(a,g(g(b))))), and then to f(b,f(g(b),h(a,a,g(g(b)))))

F(x1,x2) →

f(x2,F(x1,g(x2))) | h(x1,x1,x2)




Tree grammar.Language generated by a tree grammar

Subjects: Computing.

Reference entries

Users without a subscription are not able to see the full content. Please, subscribe or login to access all content.