Регулярные выражения и языки (стр. 29 )

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

Пример 5.26. Используя ту же грамматику выражений, мы находим, что цепочка а+Ь имеет много разных порождений. Вот два из них.

E=>E+E=*I+E=>a + E=>a + I=$a + b E=>E+E=>E + I=>I+I=>I+b=*a + b

Заметим, что настоящей разницы между структурами, заданными этими двумя порожде­ниями, нет. Каждая из них говорит, что а и b— идентификаторы, и что их значения нужно сложить. В действительности, оба эти порождения приводят к одному и тому же дереву разбора, если применяются конструкции теорем 5.18 и 5.12. □

Два примера, приведенные выше, показывают, что неоднозначность происходит не от множественности порождений, а от существования двух и более деревьев разбора. Итак, мы говорим, что КС-грамматика G = (V, T, P, S) является неоднозначной, если найдется хотя бы одна цепочка w в Т', для которой существуют два разных дерева разбора, каждое

с корнем, отмеченным 5, и кроной и>. Если же каждая цепочка имеет не более одного де­рева разбора в грамматике, то грамматика однозначна.

Е + Е

I Е

а        I

Пример 5.25 почти показал неоднозначность грамматики, изображенной на рис. 5.2. Нам нужно лишь доказать, что деревья разбора на рис. 5.17 можно пополнить так, чтобы они имели терминальные кроны. На рис. 5.18 приведен пример такого пополнения.

Е * Е

Е + Е 1

I        а

а        а        а        а

а)        б)

Рис. 5.18. Деревья с кроной а + а * а, показывающие неоднозначность грамматики выражений

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

В идеальном мире мы смогли бы дать алгоритм исключения неоднозначности из КС-грамматик, почти как в разделе 4.4, где был приведен алгоритм удаления несущест­венных состояний конечного автомата. Однако, как будет показано в разделе 9.5.2, не существует даже алгоритма, способного различить, является ли КС-грамматика неодно­значной. Более того, в разделе 5.4.4 мы увидим, что существуют КС-языки, имеющие только неоднозначные КС-грамматики; исключение неоднозначности для них вообще невозможно.

К счастью, положение на практике не настолько мрачное. Для многих конструкций, возникающих в обычных языках программирования, существует техника устранения не­однозначности. Проблема с грамматикой выражений типична, и мы исследуем устране­ние ее неоднозначности в качестве важной иллюстрации.

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

1. Не учитываются приоритеты операторов. В то время как на рис. 5.17, а оператор * правильно группируется перед оператором +, на рис. 5.17, б показано также допусти­мое дерево разбора, группирующее + перед *. Необходимо обеспечить, чтобьг в одно­значной грамматике была допустимой только структура, показанная на рис. 5.17, а.

2. Последовательность одинаковых операторов может группироваться как слева, так и справа. Например, если бы операторы * (см. рис. 5.17) были заменены операторами +, то мы увидели бы два разных дерева разбора для цепочки Е + Е + Е. Поскольку оба оператора ассоциативны, не имеет значения, группируем ли мы слева или спра­ва, но для исключения неоднозначности нам нужно выбрать что-то одно. Обычный подход состоит в группировании слева, поэтому только структура, изображенная на рис. 5.17, б, представляет правильное группирование двух операторов +.

Разрешение неоднозначности в YACC

Если используемая грамматика выражений неоднозначна, нас может удивить реали­стичность YACC-программы, приведенной на рис. 5.11. Действительно, данная грам­матика неоднозначна, однако генератор синтаксических анализаторов YACC обеспе­чивает пользователя простыми механизмами разрешения большинства общих причин неоднозначности. Для грамматики выражений достаточно потребовать следующее.

Приоритет у оператора * выше, чем у +, т. е. операторы * должны группироваться раньше, чем соседние с обеих сторон операторы +. Это правило говорит нам ис­пользовать порождение 1 из примера 5.25, а не порождение 2. И *, и + левоассоциативны, т. е. последовательности выражений, связанных только знаком *, группируются слева, и это же относится к последовательно­стям, связанным +.

YACC позволяет нам устанавливать приоритеты операторов путем перечисления их в порядке возрастания приоритета. Технически приоритет оператора применяется к использованию любой продукции, в теле которой этот оператор является крайним справа терминалом. Мы можем также объявить операторы как лево - или правоас - социативные с помощью ключевых слов %left и % right. Например, для того, чтобы объявить оба оператора * и + левоассоциативными и с более высоким при­оритетом у *, в начале грамматики (см. рис. 5.11) можно поместить следующие ин­струкции.

%left '+' %left '*'

Решение проблемы установления приоритетов состоит в том, что вводится несколько разных переменных, каждая из которых представляет выражения, имеющие один и тот же уровень "связывающей мощности". В частности, для грамматики выражений это ре­шение имеет следующий вид.

1. Сомножитель> или фактор (factor), — это выражение, которое не может быть раз­делено на части никаким примыкающим оператором, ни *, ни +. Сомножителями в нашем языке выражений являются только следующие выражения:

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

б)        выражения в скобках, независимо от того, что находится между ними. Имен­но для предохранения операндов в скобках от действия внешних операторов и предназначены скобки.

Терм (term), или слагаемое, — это выражение, которое не может быть разорвано оператором +. В нашем примере, где операторами являются только + и *, терм пред­ставляет собой произведение одного или несколько сомножителей. Например, терм а* Ь может быть "разорван", если мы используем левую ассоциативность * и помес­тим а\* слева, поскольку а\ * а * b группируется слева как (al * a)* b, разрывая а* Ь. Однако помещение аддитивного выражения слева, типа а 1+, или справа, типа +а\, не может разорвать а* Ь. Правильным группированием выражения а\ + a* b является а\ + (а* Ь), а выражения a* b + а 1 — (а* Ь) + а\. Выражение (expression) будет обозначать любое возможное выражение, включая те, которые могут быть разорваны примыкающими + и *. Таким образом, выражение для нашего примера представляет собой сумму одного или нескольких термов.

I        a\b\Ia\Ib\IQ\l\

F        1\(Е)

Т        F\T*F

Е        Т\Е+Т

Рис. 5.19. Однозначная грамматика выражений

Пример 5.27. На рис. 5.19 приведена однозначная грамматика, порождающая тот же язык, что и грамматика, изображенная на рис. 5.2. Посмотрим на F, Т и Е как на пере­менные, языками которых являются сомножители, слагаемые и выражения в описанном выше смысле. Например, эта грамматика допускает только одно дерево разбора для це­почки а + а* а; оно показано на рис. 5.20.

То, что данная грамматика однозначна, может быть далеко не очевидно. Приведем основные утверждения, поясняющие, почему ни одна цепочка языка не имеет двух раз­ных деревьев разбора.

Цепочка, порождаемая из Т, т. е. терм, должна быть последовательностью из од­ного или нескольких сомножителей, связанных знаками *. Сомножитель, по оп­ределению и как это следует из продукций для F (см. рис. 5.19), есть либо оди­ночный идентификатор, либо выражение в скобках. Вследствие вида продукций для Т единственным деревом разбора для последова­тельности сомножителей будет такое, которое разрывает* f2 * ...*/„ где п > 1, на терм fi * f2 * ■■■*/„-! и сомножитель f„. Причина в том, что F не может поро­

дить выражение вида fn. i *f„ без введения скобок вокруг него. Таким образом, при использовании продукции Т —> Т * F из F невозможно породить ничего, кро­ме последнего из сомножителей, т. е. дерево разбора для терма может выглядеть только так, как на рис. 5.21.

Е +

г г

F F

I I

• Аналогично, выражение есть последовательность термов, связанных знаками +. Когда используется продукция Е—>Е+Т для порождения // + t2 + ... +1„, из Т должно порождаться только t„, а из Ј в теле — // + t2 + ... + !„./■ Причина этого опять-таки в том, что из Т невозможно породить сумму двух и более термов без

заключения их в скобки.

т

/\\

т        * F

/\\

Т * F

Т

/\\

j * F

F

Рис. 5.20. Единственное дерево разбора Рис. 5.21. Форма всех деревьев разбора для цепочки а + а * а        для термов

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

Хотя порождения не обязательно уникальны, даже если грамматика однозначна, ока - зь вается, что в однозначной грамматике и левые, и правые порождения уникальны. Рас­смотрим только левые.

Пример 5.28. Заметим, что оба дерева разбора, представленные на рис. 5.18, имеют крону Е + Е * Е. По ним получаются следующие соответствующие им левые порождения.

а) Е => Е + Е => I + Е => а + Е => а + Е* Е => а + I* Е =>

lm        lm        lm        lm        lm        1т