Разработка компиляторов
Деревянные языки
Деревянные языки позволяют описать множества деревьев, обладающих определенными свойствами (везде далее будут иметься в виду деревья, содержащие конечное число вершин). Мы будем использовать скобочную запись дерева, которая может быть получена выписыванием пометок вершин при простом обходе дерева слева-направо и сверху-вниз. При этом поддеревья одной вершины отделяются от нее скобками, а между собой - запятыми.
Для определения понятия деревянного языка введем в рассмотрение алфавит A, снабженный взаимно-однозначной функцией арности # , которая приписывает буквам алфавита неотрицательные целые числа.
Тогда можно определить множество всех деревьев в этом алфавите как совокупность всех деревьев, у которых каждая вершина
- помечена символом a из алфавита A
- имеет ровно #(a) поддеревьев
- каждое ее поддерево в свою очередь является непустым деревом в алфавите A
В множество всех деревьев в алфавите A мы искусственно включаем также пустое дерево, которое не содержит вершин.
Наконец, деревянным языком L в алфавите A мы назовем произвольное (возможно, пустое) подмножество множества всех деревьев в алфавите A.
Поскольку при функции арности, не превосходящей единицы, все деревья в данных определениях превращаются в линейные списки, деревянные языки можно рассматривать как обобщение обычных "линейных" языков.
