Разработка компиляторов
Язык, определяемый грамматикой
Пусть есть грамматика G=(A,N,S,R) . Языком, определяемым G (обозначение L(G) ) назовем подмножество множества всех деревьев в алфавите A , для которых непусто множество выводов из тривиального дерева, единственная вершина которого помечена стартовым нетерминалом грамматики. Заметим, что такое дерево, так же, как и произвольное дерево в алфавите A , являются образцами.
Неформально говоря, грамматика определяет язык, состоящий из тех деревьев, которые можно получить подстановкой образцов из правых частей правил грамматики вместо листьев, помеченных нетерминалом из левой части этих правил до тех пор, пока в дереве существуют листья, помеченные нетерминалами.
На иллюстрации приведен пример грамматики, которая порождает деревья выражений из констант, переменных, унарных и бинарных операций. Видно, таким образом, что деревянные грамматики предоставляют удобный механизм описания различных деревьев, включая деревья внутреннего представления программы.
Можно показать, что существуют деревянные языки, для которых невозможно их задание с помощью грамматики приведенного вида.
