Древовидная грамматика
Материал из WEGA
Древовидная грамматика (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.