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



         

Построение выводов (окончание)


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

Данный алгоритм имеет сложность, пропорциональную произведению числа правил на число вершин дерева.

Будем называть грамматику G однозначной тогда и только тогда, когда для произвольного дерева из порождаемого ею языка существует в точности один вывод, и неоднозначной в противном случае.




Содержание  Назад  Вперед