Разработка компиляторов
Выводимость образцов
Для понимания того, как грамматики определяют язык, нам потребуется определить понятие выводимости образцов.
Как уже упоминалось выше, под образцом мы понимаем произвольное дерево, у которого некоторые листья помечены нетерминалами. В частности, тривиальное дерево, состоящее из одной вершины, является образцом (при этом единственная вершина может быть помечена как терминалом, так и нетерминалом).
Правила грамматики в нормальной форме содержат в правой части образцы специального вида, однако в выводе будут встречаться образцы произвольной формы. Далее через leaves(p) мы будем обозначать множество листьев образца p , помеченных нетерминалами.
Пусть есть два образца p1 и p2, вершина и правило грамматики R=N:p'. Будем говорить, что образец p2 выводится из образца p1 по правилу R , если v помечена нетерминалом N из левой части правила и p2 может быть получен подстановкой образца p' из правой части правила в образец p1 вместо вершины v .
