dzhon_khopkroft_radzhiv_motvani_dzheffri _ulman_vvedenie_v_teoriyu_avtomatov_yazy kov_i_vychisleniy_2008 (852747), страница 51
Текст из файла (страница 51)
221221с корнем, отмеченным S, и кроной w. Если же каждая цепочка имеет не более одного дерева разбора в грамматике, то грамматика однозначна.Пример 5.25 почти показал неоднозначность грамматики, изображенной на рис. 5.2.Нам нужно лишь доказать, что деревья разбора на рис. 5.17 можно пополнить так, чтобыони имели терминальные кроны. На рис.
5.18 приведен пример такого пополнения.∗+∗a)+б)Рис. 5.18. Деревья с кроной a + a * a, показывающие неоднозначность грамматики выражений5.4.2. Èñêëþ÷åíèå íåîäíîçíà÷íîñòè èç ãðàììàòèêВ идеальном мире мы смогли бы дать алгоритм исключения неоднозначности изКС-грамматик, почти как в разделе 4.4, где был приведен алгоритм удаления несущественных состояний конечного автомата. Однако, как будет показано в разделе 9.5.2, несуществует даже алгоритма, способного различить, является ли КС-грамматика неоднозначной.
Более того, в разделе 5.4.4 мы увидим, что существуют КС-языки, имеющиетолько неоднозначные КС-грамматики; исключение неоднозначности для них вообщеневозможно.К счастью, положение на практике не настолько мрачное. Для многих конструкций,возникающих в обычных языках программирования, существует техника устранения неоднозначности. Проблема с грамматикой выражений типична, и мы исследуем устранение ее неоднозначности в качестве важной иллюстрации.Сначала заметим, что есть следующие две причины неоднозначности в грамматике,изображенной на рис. 5.2.1.222Стр. 222Не учитываются приоритеты операторов. В то время как на рис.
5.17, а оператор *правильно группируется перед оператором +, на рис. 5.17, б показано также допустимое дерево разбора, группирующее + перед *. Необходимо обеспечить, чтобы в однозначной грамматике была допустимой только структура, показанная на рис. 5.17, а.ÃËÀÂÀ 5. ÊÎÍÒÅÊÑÒÍÎ-ÑÂÎÁÎÄÍÛÅ ÃÐÀÌÌÀÒÈÊÈ È ßÇÛÊÈ2.Последовательность одинаковых операторов может группироваться как слева, так исправа.
Например, если бы операторы * (см. рис. 5.17) были заменены операторами+, то мы увидели бы два разных дерева разбора для цепочки E + E + E. Посколькуоба оператора ассоциативны, не имеет значения, группируем ли мы слева или справа, но для исключения неоднозначности нам нужно выбрать что-то одно. Обычныйподход состоит в группировании слева, поэтому только структура, изображенная нарис. 5.17, б, представляет правильное группирование двух операторов +.Ðàçðåøåíèå íåîäíîçíà÷íîñòè â YACCЕсли используемая грамматика выражений неоднозначна, нас может удивить реалистичность YACC-программы, приведенной на рис. 5.11. Действительно, данная грамматика неоднозначна, однако генератор синтаксических анализаторов YACC обеспечивает пользователя простыми механизмами разрешения большинства общих причиннеоднозначности.
Для грамматики выражений достаточно потребовать следующее.1. Приоритет у оператора * выше, чем у +, т.е. операторы * должны группироватьсяраньше, чем соседние с обеих сторон операторы +. Это правило говорит нам использовать порождение 1 из примера 5.25, а не порождение 2.2. И *, и + левоассоциативны, т.е. последовательности выражений, связанныхтолько знаком *, группируются слева, и это же относится к последовательностям, связанным +.YACC позволяет нам устанавливать приоритеты операторов путем перечисления ихв порядке возрастания приоритета.
Технически приоритет оператора применяется киспользованию любой продукции, в теле которой этот оператор является крайнимсправа терминалом. Мы можем также объявить операторы как лево- или правоассоциативные с помощью ключевых слов %left и %right. Например, для того,чтобы объявить оба оператора * и + левоассоциативными и с более высоким приоритетом у *, в начале грамматики (см. рис. 5.11) можно поместить следующие инструкции.%left ’+’%left ’*’Решение проблемы установления приоритетов состоит в том, что вводится несколькоразных переменных, каждая из которых представляет выражения, имеющие один и тотже уровень “связывающей мощности”.
В частности, для грамматики выражений это решение имеет следующий вид.1.Сомножитель, или фактор (factor), — это выражение, которое не может быть разделено на части никаким примыкающим оператором, ни *, ни +. Сомножителями внашем языке выражений являются только следующие выражения:5.4. ÍÅÎÄÍÎÇÍÀ×ÍÎÑÒÜ Â ÃÐÀÌÌÀÒÈÊÀÕ È ßÇÛÊÀÕСтр. 223223а) идентификаторы. Буквы идентификатора невозможно разделить путем присоединения оператора;б) выражения в скобках, независимо от того, что находится между ними. Именно для предохранения операндов в скобках от действия внешних операторови предназначены скобки.2.Терм (term), или слагаемое, — это выражение, которое не может быть разорванооператором +.
В нашем примере, где операторами являются только + и *, терм представляет собой произведение одного или несколько сомножителей. Например, термa * b может быть “разорван”, если мы используем левую ассоциативность * и поместим a1 * слева, поскольку a1 * a * b группируется слева как (a1 * a) * b, разрываяa * b. Однако помещение аддитивного выражения слева, типа a1+, или справа, типа+a1, не может разорвать a * b.
Правильным группированием выражения a1 + a * bявляется a1 + (a * b), а выражения a * b + a1 — (a * b) + a1.3.Выражение (expression) будет обозначать любое возможное выражение, включая те,которые могут быть разорваны примыкающими + и *. Таким образом, выражениедля нашего примера представляет собой сумму одного или нескольких термов.I→a | b | Ia | Ib | I0 | I1F→I | (E)T→F|T*FE→T|E+TРис. 5.19.
Однозначная грамматика выраженийПример 5.27. На рис. 5.19 приведена однозначная грамматика, порождающая тот жеязык, что и грамматика, изображенная на рис. 5.2. Посмотрим на F, T и E как на переменные, языками которых являются сомножители, слагаемые и выражения в описанномвыше смысле. Например, эта грамматика допускает только одно дерево разбора для цепочки a + a * a; оно показано на рис.
5.20.То, что данная грамматика однозначна, может быть далеко не очевидно. Приведемосновные утверждения, поясняющие, почему ни одна цепочка языка не имеет двух разных деревьев разбора.• Цепочка, порождаемая из T, т.е. терм, должна быть последовательностью из одного или нескольких сомножителей, связанных знаками *. Сомножитель, по определению и как это следует из продукций для F (см. рис. 5.19), есть либо одиночный идентификатор, либо выражение в скобках.• Вследствие вида продукций для T единственным деревом разбора для последовательности сомножителей будет такое, которое разрывает f1 * f2 * …* fn, где n > 1,на терм f1 * f2 * …* fn-1 и сомножитель fn. Причина в том, что F не может поро224Стр.
224ÃËÀÂÀ 5. ÊÎÍÒÅÊÑÒÍÎ-ÑÂÎÁÎÄÍÛÅ ÃÐÀÌÌÀÒÈÊÈ È ßÇÛÊÈдить выражение вида fn-1 * fn без введения скобок вокруг него. Таким образом,при использовании продукции T → T * F из F невозможно породить ничего, кроме последнего из сомножителей, т.е. дерево разбора для терма может выглядетьтолько так, как на рис. 5.21.• Аналогично, выражение есть последовательность термов, связанных знаками +.Когда используется продукция E → E + T для порождения t1 + t2 + … + tn, из Tдолжно порождаться только tn, а из E в теле — t1 + t2 + … + tn-1. Причина этогоопять-таки в том, что из T невозможно породить сумму двух и более термов беззаключения их в скобки.∗+∗∗∗Рис. 5.20. Единственное дерево разборадля цепочки a + a * aРис. 5.21. Форма всех деревьев разборадля термов5.4.3.
Ëåâûå ïîðîæäåíèÿ êàê ñïîñîá âûðàæåíèÿ íåîäíîçíà÷íîñòèХотя порождения не обязательно уникальны, даже если грамматика однозначна, оказывается, что в однозначной грамматике и левые, и правые порождения уникальны. Рассмотрим только левые.Пример 5.28. Заметим, что оба дерева разбора, представленные на рис. 5.18,имеют крону E + E * E. По ним получаются следующие соответствующие им левыепорождения.а) E ⇒ E + E ⇒ I + E ⇒ a + E ⇒ a + E * E ⇒ a + I * E ⇒lmlmlmlmlmlma+a*E ⇒ a+a*I ⇒ a+a*almlm5.4. ÍÅÎÄÍÎÇÍÀ×ÍÎÑÒÜ Â ÃÐÀÌÌÀÒÈÊÀÕ È ßÇÛÊÀÕСтр.
225225б) E ⇒ E * E ⇒ E + E * E ⇒ I + E * E ⇒ a + E * E ⇒lmlmlmlmlma+I*E ⇒ a+a*E ⇒ a+a*I ⇒ a+a*almlmlmЗаметим, что эти левые порождения различаются. Данный пример не доказывает теорему, но демонстрирует, как различия в деревьях разбора влияют на выбор шагов в левомпорождении. Теорема 5.29. Для каждой грамматики G = (V, T, P, S) и w из T* цепочка w имеет дваразных дерева разбора тогда и только тогда, когда w имеет два разных левых порождения из S.Доказательство.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
