Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений (1082271), страница 51
Текст из файла (страница 51)
Поскольку грамматика, представленная на рис. 5.2, дает две различные структуры любой цепочке терминалов, порождаемой заменой трех выражений в Е+ Е * Е идентифвкаторами, для обеспечения уникальности структуры она не подходит. В частности, хотя оиа может давать цепочкам как арифметическим выражениям правильное группированне, ояа также дает им и неправильное. Для того чтобы использовать грамматику вы)жженнй в компиляторе, мы должны изменить ее, обеспечив только правильное группнрование. ЕЗ С другой стороны, само по себе существование различных порождений цепочки (что яе равносильно различным деревьям разбора) еще не означает порочности грамматики.
Рассмотрим пример. Пример 5.26. Используя ту же грамматику выражений, мы находим, что цепочка а+ Ь имеет много разных порождений. Вот два из ннх. 1. ЕеЕчЕ~!ч-Е~аоЕ=оао7=оа+Ь 2 Е ~ Е я Е =: Е з- I =е Т ч-! ~ 7 + Ь =: а + Ь Заметим, что настоящей разницы между структурами, заданными этими двумя порождеявями, нет. Каждая из ннх говорит, что а и Ь вЂ” идентификаторы, и что их значения нужно сложить.
В действительности, оба эти порождения приводят к одному и тому же дереву разбора, если применяются конструкции теорем 5.! 8 и 5.12. ЕЗ Два примера, приведенные выше, показывают, что неоднозначность происходит не от вножественности порождений, а от существования двух и более деревьев разбора. Итак, вы говорим, что КС-грамматика 0 = (Г, Т, Р, 5) является неоднозначной, если найдется хотя бы одна цепочка зе в 7, для которой существуют два разных дерева разбора, каждое 5.4. НЕОДНОЗНАЧНОСТЬ В ГРАММАТИКАХ И ЯЗЫКАХ 221 с корнем, отмеченным 8, и кроной ж. Если же каждая цепочка имеет не более одного дерева разбора в грамматике, то грамматика однозначна.
Пример 5.25 почти показал неоднозначность грамматики, изображенной на рис. 5.2. Нам нужно лишь доказать, что деревья разбора на рис. 5.17 можно пополнить так, чтобы они имели терминальные кроны. На рис. 5.12 приведен пример такого пополнения. 'т~ !'! ! з т в ! ! в в Рис. 5 18 Деревья с кроной а + а ь а показывающие неоднозначность грамматики выражений 5.4.2.
Исключение неоднозначности из грамматик В идеальном мире мы смогли бы дать алгоритм исключения неоднозначности из КС-грамматик, почти как в разделе 4.4, где был приведен алгоритм удаления несущественных состояний конечного автомата. Однако, как будет показано в разделе 9.5.2, не существует даже алгоритма, способного различить, является ли КС-грамматика неоднозначной. Более того, в разделе 5.4.4 мы увидим, что существуют КС-языки, имеющие только неоднозначные КС-грамматики; исключение неоднозначности для них вообще невозможно. К счастью, положение на практике не настолько мрачное.
Для многих конструкций, возникающих в обычных языках программирования, существует техника устранения неоднозначности. Проблема с грамматикой выражений типична, и мы исследуем устранение ее неоднозначности в качестве важной иллюстрации. Сначала заметим, что есть следующие две причины неоднозначности в грамматике, изображенной на рис. 5.2. 1. Не учитываются приоритеты операторов. В то время как на рис.
5.17, а оператор * правильно группируется перед оператором ь, на рис. 5.17, б показано также допустимое дерево разбора, группирующее + перед *. Необходимо обеспечить, чтобы в однозначной грамматике была допустимой только структура, показанная на рис.
5.17, а. 222 ГЛАВА б. КОНТЕКСТНО-СВОБОДНЬИ ГРАММАТИКИ И ЯЗЫКИ 2. Последовательность одинаковых операторов может группироваться как слева, так и справа. Например, если бы операторы * (см. рис, 5.17) были заменены операторами +, то мы увидели бы два разных дерева разбора для цепочки Е+ Е+ Е. Поскольку оба оператора ассоциативны, не имеет значения, группируем ли мы слева или справа, но для исключения неоднозначности нам нужно выбрать что-то одно.
Обычный подход состоит в группировании слева, поэтому только струкзура, изображенная на рис. 5.17, б, представляет правильное группирование двух операторов ч. Разрешение неоднозначности в ТАСС Если используемая грамматика выражений неоднозначна, нас может удивить реалистичность т'АСС-программы, приведенной на рис. 5.11. Действительно, данная грамматика неоднозначна, однако генератор синтаксических анализаторов т'АСС обеспечивает пользователя простыми механизмами разрешения большинства общих причин неоднозначности. Для грамматики выражений достаточно потребовать следующее.
1. Приоритет у оператора * выше, чем у +, т.е. операторы * должны группироваться раньше, чем соседние с обеих сторон операторы +. Это правило говорит нам использовать порождение 1 из примера 5.25, а не порождение 2. 2. И ', и + левоассоциативны, т.е. последовательности выражений, связанных только знаком ', группируются слева, и это же относится к последовательностям, связанным ~-. УАСС позволяет нам устанавливать приоритеты операторов путем перечисления их в порядке возрастания приоритета. Технически приоритет оператора применяется к использованию любой продукции, в теле которой этот оператор является крайним справа терминалом. Мы можем также объявить операторы как лево- или правоассоциативные с гюмощью ключевых слов %1ейг и вгйц1зс.
Например, для того, чтобы объявить оба оператора * и + левоассоциативными и с более высоким приоритетом у *, в начале грамматики (см. рис. 5.11) можно поместить следующие ин- струкции. $1егс $1егс Решение проблемы установления приоритетов состоит в том, что вводится несколько ршнмх переменных, каждая из которых представляет выражения, имеющие один и тот же уровень "связывающей мощности". В частности, для грамматики выражений это решение имеет следующий вид. 1.
Сомложитель„или факшо)э (гасгог), — это выражение, которое не может быть разделено на части никаким примыкающим оператором, ни *, ни +. Сомножителями в нашем языке выражений являются только следующие выражения: 5.4. НЕОДНОЗНАЧНОСТЬ В ГРАММАТИКАХ И ЯЗЫКАХ 223 а) идентификаторы. Буквы идентификатора невозможно разделить путем присоединения оператора; б) выражения в скобках, независимо от того, что находится между ними.
Именно для предохранения операндов в скобках от действия внешних операторов и предназначены скобки. 2. Терм (гепп), илн слагаемое,— зто выражение, которое не может быть разорвано оператором +. В нашем примере, где операторами являются только + и ', терм представляет собой произведение одного или несколько сомножителей. Например, терм а ' Ь может быть "разорван", если мы используем левую ассоциативность * и поместим а1* слева, поскольку а! * а *Ь группируется слева как (а! в а)" Ь, разрывая а * Ь.
Однако помещение аддитивного выражения слева, типа а1+, или справа, типа +а1, не может разорвать а* Ь. Правильным группированием выражения а! ч- а *Ь является а! +(а ' Ь), а выражения а * Ь ч- а! — !а в Ь) ч- а1. 3. Выражение (ехргеьвюп) будет обозначать любое возможное выражение, включая те, которые могут быть разорваны примыкающими ч- и *. Таким образом, выражение для нашего примера представляет собой сумму одного или нескольких термов. -+ а~Ь|Та!!Ь|й)!Т1 Т~ сЕ) Т вЂ” э Е! Т" ŠŠ— э Т/Еч-Т Рис. 5.1й Однозначная грамматика выражений Пример 5.27. На рис.
5.19 приведена однозначная грамматика, порождающая тот же язык, что и грамматика, изображенная на рис. 5.2. Посмотрим на Е, Т и Е как на переменные, языками которых являются сомножители, слагаемые и выражения в описанном выше смысле. Например, эта грамматика допускает только одно дерево разбора для цепочки а 4 а ' а; оно показано на рис. 5.20.
То, что данная грамматика однозначна, может быть далеко не очевидно. Приведем основные утверждения„поясняющие, почему ни одна цепочка языка не имеет двух раз- ных деревьев разбора. ° Цепочка, порождаемая из Т, т.е. терм, должна быть последовательностью из одного или нескольких сомножителей, связанных знаками в. Сомножителем по оп- ределению и как это следует из продукций для Е !см. рис. 5.19), есть либо оди- ночный идентификатор, либо выражение в скобках. ° Вследствие вида продукций для Т единственным деревом разбора для последовательности сомножителей бУдет такое, котоРое РазРывает/; * Тг * ...в5т где п > 1, на терм Тг * Тг * ...в/;, г и сомножнтельум Причина в том, что Е не может поро- ГЛАВА б.
КОНТЕКСТНО-СВОБОДНЫЕ ГРАММАТИКИ И ЯЗЫКИ 224 дить выражение вида~„'.! * Г„без введения скобок вокруг него. Таким образом, при использовании продукции Т вЂ” ь Т* г" из г" невозможно породить ничего, кро- ме последнего из сомножителей, т.е. дерево разбора для герма может выглядеть только так, как на рис. 5.21. ° Аналогично, выражение есть последовательность термов, связанных знаками +. Когда используется продукция Е-» Е+ Т для порождения !!+ гз+ ... + г„, из Т должно порождаться только г„, а из Е в теле — 1, + ге+ ... + гт!. Причина этого опять-таки в том, что из Т невозможно породить сумму двух и более термов без заключения их в скобки. Г1~ 1 "1' ! ! ! Р Р ! ! ! ! ! а ! ! т Г1~ Рис. 5.2!. Форма всех деревьев разбора дея терман Рис. 5.20. Единственное дерево разбора для цепочки а + а а а 5.4,3. Левые порождения как способ выражения неоднозначности порождения.
а) Е ~ Е+ Е г» ! ч Е ~ а+ Е =» а+ Е а Е ~ а + ! а Е =» чи ! lи и и хеи а + а а Е =» а .ь а а У =» а + а а а и и $.4. НЕОДНОЗНАЧНОСТЬ В ГРАММАТИКАХ И ЯЗЫКАХ 225 Хотя порождения не обязательно уникальны, даже если грамматика однозначна, окавввается, что в однозначной грамматике и левые, и правые порождения уникальны.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
