Древовидная грамматика

Древовидная грамматика (Tree grammar) — обобщение понятия грамматики применительно к деревьям (в этом контексте часто называемым термами), отличным от цепочек (см. Древовидный язык). Соответствующим обобщением понятия регулярной грамматики является регулярная древовидная грамматика. Продукции имеют вид

[math]\displaystyle{ A \longrightarrow t, }[/math],

где [math]\displaystyle{ A }[/math] — нетерминальный символ, [math]\displaystyle{ t }[/math] — терм, например,

[math]\displaystyle{ S \longrightarrow h(a,g(S),b) | c. }[/math].

Такие продукции генерируют регулярный древовидный язык. Аналогично можно обобщить и понятие бесконтекстной грамматики. На этот раз нетерминальные символы сами могут быть символами функций, имеющих произвольное число аргументов.

Литература

• Толковый словарь по вычислительным системам. — М.: Машиностроение, 1991.