Разработка компиляторов

       

Деревянные языки


Деревянные языки позволяют описать множества деревьев, обладающих определенными свойствами (везде далее будут иметься в виду деревья, содержащие конечное число вершин). Мы будем использовать скобочную запись дерева, которая может быть получена выписыванием пометок вершин при простом обходе дерева слева-направо и сверху-вниз. При этом поддеревья одной вершины отделяются от нее скобками, а между собой - запятыми.

Для определения понятия деревянного языка введем в рассмотрение алфавит A, снабженный взаимно-однозначной функцией арности # , которая приписывает буквам алфавита неотрицательные целые числа.

Тогда можно определить множество всех деревьев в этом алфавите как совокупность всех деревьев, у которых каждая вершина

  • помечена символом a из алфавита A
  • имеет ровно #(a) поддеревьев
  • каждое ее поддерево в свою очередь является непустым деревом в алфавите A

В множество всех деревьев в алфавите A мы искусственно включаем также пустое дерево, которое не содержит вершин.

Наконец, деревянным языком L в алфавите A мы назовем произвольное (возможно, пустое) подмножество множества всех деревьев в алфавите A.

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



Содержание раздела