Левые порождения как способ выражения неоднозначности

Исключение неоднозначности из грамматики

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

В примере с арифметическими выражениями есть две следующие причины неоднозначности грамматики:

1. Не учитывается приоритеты операторов;

2. Не указана ассоциативность операторов.

Решение проблемы приоритета – вводится несколько разных переменных, каждая из которых отражает разные уровни приоритета:

1. Сомножитель (фактор, factor) – это выражение, которое не может быть разделено на части никаким примыкающим оператором (ни «*», ни «+»).

В нашем примере сомножитель:

a) Идентификатор. Буквы идентификатора невозможно разделить путем присоединения оператора.

b) Выражение в скобках.

2. Слагаемое(терм, term) - это выражение, которое не может быть разделено на части оператором «+».

В нашем примере терм – произведение одного или нескольких сомножителей.

3. Выражение (expression)– любое выражение, в том числе те, которые могут быть разделены «*» или «+».

В нашем примере выражение – сумма одного или нескольких термов.

Теорема. В однозначной грамматике левые и правые порождения уникальны.

Теорема. В любой КС-грамматике терминальная цепочка имеет два разных дерева разбора тогда и толь тогда, когда эта цепочка имеет два разных левых (правых) порождения.