Р.У. Себеста - Основные копцепции языков программирования (2001) (1160794), страница 36
Текст из файла (страница 36)
Вывод продолжается до тех пор, пока сентенциаяьная форма не перестанет содержать нетерминальные символы. Сентенпиальная форма, состояшая только из терминальных символов, или лексем, является порожденным предложением. Вывод может быть как левосторонним, так и правосторонним, а также может использовать другой, отличный от этих двух, порядок замены. Отметим, что на язык, порождаемый грамматикой, порядок вывода никак не влияет. Выбирая альтернативные правые стороны правил замены нетерминальных символов в выводе, можно порождать различные предложения языка. Весь язык может быть создан путем перебора всех сушествуюших комбинапий альтернатив. Этот язык, как и большинство других, бесконечен, так что за конечное время все предложения языка поролить невозможно.
В листинге 3.2 приведен пример еше одной грамматики дяя части типичного языка программирования. <присвоить> -э <идентификатор> := <выражение> <идентификатор> ь А ! В ! С <выражение> -ь <идентификатор> + <выражение> <идентификатор> * <выражение> ! ! <выражение> ) ! <идентификатор> Глава 3. Описание синтаксиса и семантики 130 Грамматика, приведенная в листинге 3.2, описывает операторы присваивания. у которых правыми сторонами являются арнфметнческне выражения с операторами умножения н сложения, а также круглыми скобками. Например, оператор А:=В* (А+С) порождается следующим левосторонннм выводом: <присвоить»= <идентификатор> : <выражение> > А := <выражение> => А : <идентификатор> * <выражение> => А := В * <выражение> > А : В * ( <выражение> ) > А := В * ( <идентификатор> + <выражение> ) => А : В * ( А + <выражение> ) > А := В * ( А + <идентификатор> ) > А т В * ( А + С ] З.З.1.6.
Дегзевфза синтезксического анализа Одно нз самых привлекательных свойств грамматик состоит в естественности нх описания иерархической синтаксической структуры предложений опрелеляемого нмн языка. Указанные иерархические структуры называются деревьями сннтакснческого аналнза(рагяе тгее). Например, дерево синтаксического анализа, приведенное на рнс. 3.1, показывает структуру полученного выше оператора присваивания. <ириоеоить> <идентифиттор>;= <еырежеим> Т д <идеитифитетор> ' <еырежеиие> <идеитифтетор> + <еыриаиие> итифиетотт> Рис. 3. А Дерево синтаксического анаеиза простого оператора А:= В и (А + Сг Каждый внутренний узел дерева синтаксического анализа помечен нетермннальным символом; а каждый лист — терминальным символом.
Каждое поддерево дерева сннтакснческого анализа описывает один экземпляр абстракннн оператора. 131 3.3. Формальные методы описания синтаксиса З.З. 1.7. Неоднозввачиоств Грамматика, порождаюшая предложение, лля которого существует несколько деревьев синтаксического анализа, называется неоднозначной (ааЬтйоцв). Рассмотрим грамматику. показанную в листинге 3.3, незначительно отличаюшуюся от грамматики, приведенной в листинге 3.2. .присвоить> -> <илеитиФикатор> := <выражение> <идентификатор> -ь Л ) В ) С <выражение> -э <вырая:ение> в <выражение> <выражение> " <выражение> ( <выражение> ) <идентификатор> Грамматика, показанная в листинге З.З, является неоднозначной, поскольку предло- жение Лт=н+С-Л имеет два разных дерева синтаксического анализа, показанных на рис.
3.2. <присвоить> <присвоить> <идентификатор>:= <вырвжвиив> <идвнтификвтор>:= <вырвжвиив> А <выреквиив> + <выражение> А <вырвжвиив> ' <выражение> <иАвитификвтор> <вырвжвиив> <вырвжвнив> <вырнквнив> + <вырвжвнив> <идвитификвтор> ! ! ! ! ! ! В <идвнтификвтор> ! С <идвитификвтор> <идвитификвтор> <идвитнриквтор> А ! ! ! А В С Рис 3 2 Леа ртгктттчныт дерева от тык>так<к<чески о он атнзи дтя однтхто выра>гения А: = В е С ь А Глава 3.
Описание синтаксиса и семантики Неоднозначность появляется вслелствие определения грамматикой несколько меньшей синтаксической стрултьры. чем это было сделано грамматикой, привеленной в листинге 3.2. Данная грамматика в отличие от предыдушей, позволяет дереву синтаксического анализа выражения расти не только вправо, но и влево. Синтаксическая неоднозначность структур языка представляет собой проблему, поскольку семантику таких структур компиляторы часто определяют, исходя из их синтаксической формы. В частности, изучив дерево синтаксического анализа, компилятор решает, какие команлы генерировать лля оператора.
Если структура языка допускает сушествование нескольких де- ревьев синтаксического анализа. то значение структуры не может определяться олнозначно. Исслелование этой проблемы с помощью двух конкретных примеров провозится в следующих трех разделах. З.З.1.8. Приоритет опероторо Как указывалось ранее.
грамматика так описывает определенную синтаксическую структуру. что смысл этой структуры может отчасти определяться деревом синтаксического анализа. В частности. тот факт. что оператор в арифметическом выражении порожлаегся ниже на лереве синтаксического анализа (и. следовательно. должен вьшислягься первым). можно использовать. чтобы указать на более высокий приоритез л зго оператора. чем у оператора. порождаемого выше. Например.
на первом из представ юнных на рис. 3.2 лерсвьев синтаксичссьо~о анализа оператор умножения генерируегся ниже по дереву, что может указывать на его более высокий приоритет по сравнению с операнром сложения того же выражения. Впрочем. на втором из изоораженных на рис. 3.2 деревьев синтаксического анализа лемонстрируется противоположное. Следовательно. эти два дерева синтаксического анализа отображают противоречивую информанню о приоритетности операторов. Отметим, что хотя грамматика. привеленная в листинге 3.2. и является однозначной.
она имеет необычный приоритет операторов. В этой грамматике на дереве синтаксического анализа прелложения. состоящего из нескольких операторов. независимо от их конкретного вила, крайний справа оператор выражения находится в самой нижней точке. тогла как остальные операторы постепенно перемешаются вверх по дереву при продвижении к крайнему слева оператору выражения. Например, на дереве синтаксического анализа. изображенного на рис. 3.1, оператор сложения является крайним справа оператором выражения и самым ю<жним оператором на дереве синтаксического анализа и получает. таким образом, более высокий приоритет при выполнении. чеч расположенный левее оператор умножения. Для того чтобы отлелить операторы сложения и умножения лрут от друга. следует написать грамматику так, чтобы они располагались на лереве синтаксического анализа в порядке от высшего ло низшему.
Такое упорядочение может поддерживаться вне зависимости от порядка появления операторов в выражении. Правильный порядок устанавливается с помощью отдельной абстракнии для операндов операторов. имеюиизх различные приоритеты. Это требует дополнительных нетермииальных символов и некоторых новых правил. Пример подобной грамматики приведен в листинге 3.4. <присвоить> -э <идентификатор> : <выражение> <идентификатор> -э А ) В ! С <выражение> -э <выражение> + <теом> <терм> <терм> -+ <терм> ' <множитель> <множитель> <множитель> -э ( <выражение> ) <идентификатор> 3.3. Формальные методы описания синтаксиса 133 Грамматика, показанная в листинге 3.4, порождает тот же язык.
что и грамматики. показанные в листингах 3.2 и 3.3, но в ней указан привычный приоритет операторов умножения и сложения. Ниже следует вывод выражения А:= В + С ' А с использованием грамматики, показанной в листинге 3.4. <идентификатор> := свыражение> А := <выражение> А := <выражение> + <терм> А := <терм> + <терм> А : <множитель> + <терм> А := <идентификатор> + стерм> А := В + <терм> А :- В + <терм> * <множитель> А : В ж <терм> <множитель> А := В + <идентификатор> к <множитель> А : В + С * <множитель> А := В ч С * <идентификатор> А : В + С * А <присвоить» = => => > => => На рнс.
3.3 показано дерево синтаксического анализа, которое с использованием грамматики листинга 3.4 однозначно определяется для приведенного выше предложения. <лрисвоить> <иавнтификвтор>:= <вмрвжвнив> <тврм> <терм> <множитель> <идвнтифнквтор> А 1 ! <множитвль> <множитель> ! ! <ндвнтификвтор> <ндвнтификвтор> ! ! В С Рис З.З.
Использование однозначной граччатикн пазватяет однозначно опредеяить дерево синтакси- ческого анатиза выраженняА т= В+ С 'А Глава Э. Описание синтаксиса и семантики Связь между деревьями синтаксического анализа и выводами очень тесная: одно может быть легко получено из другого. Любой вывод на основе олнозначной грамматики имеет одно дерево синтаксического анализа, хотя зто дерево может соответствовать разным выводам. Например, нижеследующий вывод предложения А:= В + С и А отличается от данною выше вывода того же выражения.
Это — правосторонний вывод, тогда как предыдущий был левосторонним выводом. Тем не менее. оба этн выводы представляют- ся одним и тем же деревом синтаксического анализа. <идентификатор> <идентификатор> <идентификатор> <присаоить» = => <выражение> <выражение> + <терм> <аыражение> + <терм> * <множитель> => <идентификатор => <выражение> + <терм> <идентификатор> > <идентификатор> <идентификатор> <идентификатор> > * А <идентификатор> <идентификатор> <идентификатор> <идентификатор> <идентификатор> А : В + С * А <выражение> + <терм> * А выражение> + <множитель> * А <выражение> + => <идентификатор > <выражение> + С * А <терм> + С * А <множитель> + С * А <илентификатор> + С * А В + С * А => => => Дерево синтаксического анализа этого предложения, определяемое грамматикой, представленной на листинге 3.4, показано на рис.
3.4. Приведенное на рис. 3.4 дерево синтаксического анализа показывает, что левый оператор сложения находится ниже правого. Такой порядок является правильным, если сложение считать левоассоциативным, как обычно. В большинстве случаев ассоциативность сложения в компьютере несущественна (в математике сложение ассоциативно, что означает равнозначность правого и левого ассоциативных порядков, т.е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
