Неоднозначные грамматики

Крона дерева разбора

Если листья дерева разбора выписать слева направо, то получается строка, которая называется кроной дерева.

Крона всегда является строкой, выводимой из переменной, которой обозначен корень. Особый интерес представляют деревья разбора со следующими свойствами:

1. Крона является терминальной строкой, т.е. все листья отмечены терминалами или .

2. Корень отмечен начальным символом грамматики.

Кроны таких деревьев представляют собой строки языка, определяемого грамматикой.

Пример. КС-грамматика задана своими правилами

Показать, что строка терминалов принадлежит языку переменной , построив дерево разбора этой цепочки.

Крона: .

КС-грамматика называется неоднозначной, если существует выводимая терминальная цепочка, для которой имеется более одного дерева разбора.

КС-грамматика называется однозначной, если каждая выводимая терминальная цепочка имеет не более одного дерева разбора.

Пример. КС-грамматика задана своими правилами

Цепочка .

Эта цепочка имеет два порождения

1.

2.

Этим порождениям соответствуют различные деревья разбора

1. Второе и третье выражение перемножаются и результат складывается с первым выражением.

2. Два первых выражения складываются и результат перемножается с третьим выражением.

Первое порождение соответствует нашему представлению о правильной группировке арифметических выражений, второе - нет. Неоднозначность разбора происходит от существования двух или более деревьев разбора.

Дата добавления: 2013-12-14