tree grammar

views updated

tree grammar 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.

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)))))