Разработка компиляторов
Построение выводов (окончание)
Пусть задана грамматика G и дерево t. Индукцией по числу шагов можно доказать, что приведенный алгоритм действительно строит разметку, обладающую заявленными свойствами. В частности, дерево t выводится в грамматике G тогда и только тогда, когда C[root(t)][S] непусто, где S - стартовый нетерминал G.
Данный алгоритм имеет сложность, пропорциональную произведению числа правил на число вершин дерева.
Будем называть грамматику G однозначной тогда и только тогда, когда для произвольного дерева из порождаемого ею языка существует в точности один вывод, и неоднозначной в противном случае.
