Р.У. Себеста - Основные копцепции языков программирования (2001) (1160794), страница 45
Текст из файла (страница 45)
1984; Водчч(п е! а1., 1982). Эти работы показали, что этот метод вполне осуществим, но он ни разу не использовался для порождения пригодного к использованию компилятора. С одной стороны, денотационные описания очень сложны, с другой — они лают великолепный метод краткого описания языка. Несмотря на то что использование денотационной семантики обычно приписывается Скопу и Стречи (Бсоц апд 5!гас)зеу. 1971), происхождение общего денотационного подхода к описанию языка можно проследить до девятнадцатого века (Ргейе, ! 892). Форма Бэкуса-Наура и контекстно-свободные грамматики эквивалентны метаязыкам, которые практически идеально подходят лля описания синтаксиса языков программирования. Точными методами описания являются не только они, но и деревья синтаксического анализа, которые вместе с порождающими действиями, образуют графическое представление основных синтаксических структур.
Более того, они естественным образом связаны с устройствами распознавания порождаемых ими языков, что приводит к относительно легкому построению синтаксических анализаторов, входящих в состав компиляторов этих языков. Графическим представлением грамматик являются синтаксические графы. Атрибутивная грамматика — описательный формализм, который может описывать как синтаксис, так и статическую семантику языка. Существуют три основных метода описания семантики языка: операционный, аксиоматический и денотационный.
Операционная семантика является методом описания смысла языковых конструкций в терминах их воздействия на идеальную машину. Аксиоматическая семантика, основанная на формальной логике, была придумана как сред- 16У Разюма ство доказательства правильности программ. В денотационной семантике для выражения смысла языковых конструкций используются математические объекты. Преобразование языковых сущностей в математические объекты выполняется с помощью рекурсивных функций.
Описание синтаксиса с использованием контекстно-свободных грамматик и формы БНФ всесторонне рассмотрено в книге Кливленда и Узгачиса (С(еате!апд апд Цз8а!В. !976). Синтаксические графы были разработаны в компании Вштоц8Ьз с целью использования их в качестве компактного описания синтаксиса языка А).ООС 60 в рамках проекта по разработке компилятора (Тау!ог с!. а1..
1961). Позже они были модифицированы А.Шаи (Арейа!), Руководителем вычислительного центра в Швейцарском федеральном технологическом институте (ЕТН) в Цюрихе. В печати эта модифицированная версия впервые появилась в виде книги Рутишаузера о языке АЕОО(. 60 (Кц!!з!зацзег, 1967). Исследование аксиоматической семантики было начато Флойдом (Р1оуг), 1967) и позже развито Хоаром (Ноаге. 1969). С помощью этого метода Хоаром и Виртом (Ноаге апд %!пй. 1973) была описана семантика большей части языка Разса1. В число неописанных моментов входили побочные эффекты функций и операторы йшо, поскольку эти объекты считались сложными лля описания. Техника использования предусловий и постусловий во время разработки программ описывалась (и пропагандировалась) Дийкстрой (Щйз!га, 1976), также они подробно рассмотрены в работе Гриса (Опек, ! 981).
Хорошими вволными курсами в денотационную семантику ма~уз служить работы Горлона (Оогдоп, 1979) и Стоя (Бгоу, 1977). Введение во все три метода семантического описания, представленные в данной главе, можно найти в книге Маркотти (Магсопу е! а1., 1976). Еще одним полезным справочником по большей части описанного материала может служить книга Пагана (Райап, 1981). Форма использованных в главе функций денотационной семантики полобна форме, использованной в книге Мейера (Меуег, 1990).
1. Дайте определение понятий "синтаксис" и "семантика". 2. Для кого создается описание языка". 3. 4. 5. 6. 7. 8. 9. Опишите работу обычного генератора языка. Опишите работу обычного устройства распознавания языка. Чем отличается "прелложение" от "сентенциальной формы".' Дайте опрелеление леворекурсивного грамматического правила. Какие три дополнения обычно делаются в формах РБНФ? Опишите статическую и динамическую семантики. Для чего в атрнбутивной грамматике служат предикаты? Глава 3. Описание синтаксиса и семантики 1. 2.
3. 3.2. В:= С * (А + С + В] 3.3. А:= А )В + (С)) 4.1. А:= (А ~- В) * С 4.2. А : = В + С ~- А 43. А:.= А * (В + С) 4.4. А:- В (С * (А + В)) <$> -ь <А> 169 Упражнения 1О. 11. 12. 13. 14. 15. 1б. 17. Чем различаются синтезированный и унаслелованный атрибут? Как определяется порядок вычисления атрибутов для деревьев с заданной атрибу- тивной грамматикой? Назовите основное применение атрибутивной грамматики. В чем заключается проблема операшюнной семантики при использовании про- граммно реализованного чистого интерпретатора". Объясните смысл в аксиоматической семантике прелусловий н постусловий данно- го оператора. Опишите подход к использованию аксиоматической семантики для доказательства правильности данной программы.
Опишите основную концепиию денотанионной семантики. Чем отличается операинонная семантика от ленотационной? Двумя математическими моделями описания языка являются порожлеиие н распо- знавание. Опишите. каким образом каждая из них может определять синтаксис языка программирования.
Создайте описания в форме РБНФ и синтаксического графа следуюших объектов. 2.1. Оператор заголовка ркосе<Ьлке языка Рааса). 22. Оператор вызова ркосейикв языка Разса1. 2.3. Оператор вмзсо)з языка С. 2.4. Определение ипхоп языка С. 2.5. Литеральные константы к1оак языка С. Используя грамматику. приведенную в листинге 3.2, продемонстрируйте дерево синтаксического анализа и левосторонний вывод для следуюших выражений. 31. А:= А ';В + (С А)) Используя грамматику.
приведенную в яистинге 3.4. пролемонстрируйте лерево синтаксического анализа н левосторонний вывод лля следуюших выражений. Докажите неоднозначность следуюшей грамматики: <А>-ч <А>+ <А> ! <идентификатор> <идентификатор> -+ а!Ь!с Модифнцируйте грамматику, приведенную в листинге 3.4, для введения унарного оператора вычитания. имеюшего более высокий приоритет, чем операторы + и '.
Опишите на русском языке язык, определяемый следуюшей грамматикой: <5> -~ <А> <В><С> 7. Рассмотрите следуюшую грамматику: Какие из следуюшнх предложений принадлежат к языку, генерируемому этой грамматикой? 8.1. ЬааЬ. Рассмотрите слелуюшую грамматику: <$> — > а <5> с <В> ! <А> ! Ь <А>-+с <А>!с <В> -зй!<А> Какие из следующих предложений принадлежат к языку, генерируемому этой грамматикой? 9.1.
аьсб. Напишите грамматику лля языка, состоящего из строк, имеющих и (и > 0) экземп- ляров буквы а, за которыми следует такое же число экземпляров буквы Ь. К этому языку, например, принадлежат строки аЬ, аааааЬЬЬЬ и ааааааааЬЬЬЬЬЬЬЬ, но не при- надлежат строки а, аЬЬ. Ьа и аааЬЬ. Создайте деревья синтаксического анализа для предложений ааЬсс и аааЬЬЬс, полу- ченных при использовании грамматики, описанной в упражнении 1О.
1УО 1О. 11. <А>-~а <А>!а <В> -Ф Ь <В> ! Ь <С> -з с <С> !с <Я> -> <А> а <В> Ь <А> -э <А> Ь ! Ь <В> -з а <В> ! а 8 2. ЬЬЬаЬ. 8.3. ЬЬааааа. 8.4. ЬЬааЬ. 9.2. асеев. 9.3. асссЬсс. 9.4. асд. 9.5. ассе. Глава 3. Описание синтаксиса и семантики 12. 13. 14. 15. 16. 17. 18.
Используя команды виртуальной машины, представленные в разделе 3.6.!.!. лайте в рамках операнионной семантики определение следующих объектов. 12.1. Оператор хороас языка Рааса!. 12.2. Оператор хох-с(оипсо языка Рааса!. 12.3. Оператор00языкаГО)ц'ВАНвформе00 8 К = всагт, епс), втер. 12.4.
Структура дй-ЕЬеп-е2ве языка Рааса). 12.5. Оператор хок языка С. !2.6. Оператор вийксЬ языка С, Найдите слабейшее предусловие для каждого из слелующих присваиваний. 131. а:= 2 * (Ь - 1) - 1 (а > О) 132. Ь:= (с + 10) l 3 [Ь > 6) 13.3. а:= а + 2 * Ь вЂ” 1 (а > 1) 13.4.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
