Р.У. Себеста - Основные копцепции языков программирования (2001) (1160794), страница 37
Текст из файла (страница 37)
(А + В) С = А + (В + С)). Целочисленная машинная арифметика также ассоциативна. В некоторых случаях, правда, сложение с плавающей точкой не является ассоциативным. Предположим, что число с плавающей точкой хранится с точностью до семи цифр, и нужно сложить одиннадцать чисел, одно из которых равно 1О', а остальные равны 1.
Если меньшие числа (единицы) будут по одному добавляться к большему, то последнее они никак не изменят, поскольку меньшие числа приходятся на восьмой разряд большого числа. Впрочем, если сначала выполнить сложение всех малых чисел, а результат добавить к большому, то результат с точностью в семь знаков составит 1.000001'1О . Вычитание и деление не ассоциативны как в математике, так и в компьютерной технике. Следовательно, правильная ассоциативность может оказаться существенной для выражений, содержащих какое-либо из указанных действий.
3.3. Формальные методы описания синтаксиса З.З.1.9. Ассоциативность операторою Еще одним интересным вопросом, касающимся грамматик выражений, является вопрос, верно ли описана ассоциативность операторов; т.е. в правильном ли порялке появляются соседние операторы, имеющие одинаковый приоритет, на деревьях синтаксического анализа выражений, содержащих несколько таких операторовр Ниже представлен пример такого оператора присваивания: А:В+С+А <ори<влить> <идентифмзтор> = <вмражение> <вмражение> т <терм> <множнтель> <терм> <множитель> <идентификатор> ! ! <идентификатор> д ! с <множитель> <идентификатор> в Рнс.
3.4. Дерево силтаьсичсскаса аники>а ттрвдтоотсенилА:= В + С е А, т<ттюслтриртю- мтве ассаяиативнаслть ста>к<влил <множитель> -> <показатель> *" <множитель> <показатель> <показатель> а ( <выражение> ] ! <идентификатор> мотут использоваться для описания оператора возведения в степень как правоассопиа- тнвного оператора.
3.3.1.10. Одновномное гродддлотнко дгве опероторо Хл'-п)зезз-е1ее Повторим правила формы БНФ, представленные в разделеЗ.ЗА.З, лля отдельной формы оператора хк-с)твп-в1вв: <условный оператор> -ь 1к <логическое выражение> Фавн <оператор> 136 Глава 3. Описание синтаксиса и семантики Если в правиле формы БНФ левая часть содержится в начале правой, правило называется леворекурсивным Пейгесогзве).
Такая левая рекурсия устанавливает левую ассоциативность. Например, левая рекурсивность правил грамматики листинга ЗА приводит к ее левой ассоииативиости по отношению к умножению и сложению. В большинстве языков, имеюших такую возможность, оператор возведения в степень является правоассоциативным. Для указания на правоассоциативность используется правая рекурсия. Грамматическое правило называется праворекурсивным (гтйптгесигзттте), если его левая часть появляется в правом коппс его правой части. Например, правила ьт <логическое выра.ечиа> Еукеп <опесатор> е1ве .опесатор> Если, полтимо этого, у нас есть правило <оператор> -> <условии>1 сператос>, то наша грамматика неоднозначна.
Простейшая сентенциальная форма. илли>стрирчошая эту неоднозначность. имеет вид: йк' <логическое выражение> Еттеп йк' <логическое выраже"ие> Еутеп <оператср> е1ве <оператор> Приведенные на рис. 3.5 два дерева синтаксического анализа показывают неоднозначность этой формы высказывания. Пралтическне проблемы, связанные с проблемой оператора е1ве, подробно рассматриваются в главе 7.
<условный атщитор> И <полете<кое выражение> квеп <опервтор> е1ее <опервтор> <условный оператор> ы <логическое выражение> сьев <опервтор> <условный опервтор> ке <логическое выражение> кьео <опервтор> <условный оператор> те <логическое вырвжение> кьеп <оператор> е1ее <опервтор> Рис. 3.5.
рви рагаычных дерева сантакслческого анагвза для одной и я|ой же фортгы выскаэываггтнт Разработаем теперь однозначную грамматику, описыааюшую данный оператор И. В большинстве языков правило для конструкций йЕ состоит в следуюшем: оператор е1ве (если он есть) соответствует ближайшему предыдуцтему оператору еутеп. для которого такое соответствие еше не установлено. Следовательно. ме кду оператором с<тел 3.3. Формальные методы описания синтаксиса и соответствующим ему оператором е1ве не может существовать оператора дк без оператора в1ве. Таким образом, в ланной ситуапии мы должны различать операторы, для которых соответствие найлено, и те, для которых оно не найдено.
В последнем случае операторами, для которых соответствующая пара не найдена, будут операторы е1ее, которых будет меньше, чем существующих операторов дк, при этом для остальных операторов соответствие должно быть найдено. Проблема описанной выше грамматики заключается в том, что в ней все операторы считаются синтаксически эквивалентными, т.е. совпадающими между собой. Для отражения существования различных видов операторов должны использоваться различные абстракнии, или нетерминальные символы. Однозначная грамматика, основанная на описанных идеях, привелена ниже: <оператор> -э <согласованное выражение> (<несогласованное выражение> <согласованное выражение> -> дк <логическое выражение> креп <согласованное выражение> е1ее <согласованное выражение> ! любое выражение, не содержащее оператор 11 <несогласованное выражение> -э йх <логическое выражение> сэзеп <оператор> дк <логическое выражение> сЬеп <согласованное выражение> е1ве <несогласованное выражение> Если использовать эту грамматику, то лля предложения, приведенного на рис.
3.5, существует только одно возможное дерево синтаксического анализа. 3.3.2. Расширенная форма БНФ Из-за некоторых незначительных неудобств, присущих форме БНФ. в нее были внесены некоторые дополнения. Версии формы БНФ. лля которых таких дополнений было сделано больше всего. стали называться расширенными формами БНФ, или просто РБНФ (ЕВЕР— ех~епдед ВХР), хотя сами эти формы не совсем идентичны.
Данные расширения не увеличивают описательную силу формы БНФ; они всего лишь увеличивают удобство ее чтения и использования. Различные версии формы РБНФ, как правило, включают три дополнения. Первое из них обозначает необязательную часть правой стороны правила, которая помещается в квадратные скобки. Например, оператор выбора языка С может быть описан следующим образом. <выбор> -+ дх ( <выражение> ) <оператор> [е1ве <оператор>) Без использования квадратных скобок синтаксическое описание данного оператора потребовало бы двух правил. Вторым дополнением является использование в правой части правила фигурных скобок, указывающих на то, что заключенная в скобки часть может повторяться неограниченное число раз нли вообще пропускаться.
Это дополнение позволяет создавать списки с помощью олного правила, не используя рекурсию и лополнительное правило. Например, список идентификаторов, разделенных запятыми, может быть описан так: <список идентификаторов> -ь <идентификатор> (, <идентификатор>( Глава 3. Описание синтаксиса и семантики Это правило представляет собой замену рекурсии формой подразумеваемой итерации; заключенная в скобки часть может повторяться любое число раз. Третье обычное дополнение связано с многовариантным выбором.
Когда из группы должен выбираться один элемент, варианты выбора помешаются в круглые скобки и разделяются оператором ИЛИ ( 1 ). Например, следуюшее правило описывает оператор хок языка Разса1. <оператор цикла> -э кок <переменная> := <выражение> (со 1 с(оипео) <выражение> <1о <оператор> Повторим, что лля описания этой структуры потребовалось бы два правила формы БНФ. Квадратные, фигурные и круглые скобки в дополнениях формы РБНФ являются метасимволами. Это означает, что они являются способами обозначения, а не терминальными символами в синтаксических объектах, которые они помогают описывать. Если эти метасимволы являются также терминальными символами описываемого языка.
то последние должны подчеркиваться отдельно. форма Внаи <выражение> ь <выражение> ~ <терм> <выражение> — <терм> <тесм> <терм> -з <терм> * <множитель> <терм> / <множитель> 1 <множитель> форма РБНФ: <выражение> ~ <терм> ((+1-) <терм>1 <терм> -э <множитель> ((*1/) <множитель>) Некоторые версии формы РБНФ допускают приписывание к правой фигурной скобке числовых верхних индексов, чтобы указать на верхний предел числа возможных повторов фрагмента, заключенного в скобки.
В некоторых версиях также используется верхний инлекс+ лля указания на олно нлн несколько повторений. Например, правила <составной оператор> -з Ьеадп <оператор> 1<оператор>1 впа <составной оператор> -з Ьеазп (<оператор>)' вос1 эквивалентны. 3.3.3. Синтаксические графы Граф (стара) представляет собой набор узлов, некоторые из которых соелиняются линиями, называемыми ребрами. Ориентированный граф(гйгес(ед бгарй) — граф с ориентированными ребрами; т.е. на одном из их концов имеется стрелка, указывающая направление.
Ограниченной формой ориентированного графа является дерево синтаксического анализа. На ориентированном графе представляется информация о правилах форм БНФ и РБНФ. Такие графы называются синтаксическими графами (зуп(ах ргар(зз), синтакси- 139 3.3. Формальные методы описания синтаксиса ч«кими диаграммами или синтаксическими схемами. Для каждой синтаксической единицы используется огдельный синтаксический граф, так же. как нетерминальиый символ в грамлтатике.
Для представления терминальных и нетерминальных символов правой части грамматического правила на синтаксическом графе используются различные типы узлов. Прямоугольные узлы содержат название синтаксической единицы (нетермттнального симво.ю), Терлтинальные символы находятся в кругах или эллипсах. На рис. 3.6 показан синтаксис оператора хк' языка Аба в форме РБНФ и в форме оингоксического графа. Отметим.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
