Т. Пратт, М. Зелковиц - Языки программирования - разработка и реализация (4-е издание_ 2002) (1160801), страница 34
Текст из файла (страница 34)
Определив основной набор терминальных символов, можно использовать их для конструирования более сложных цепочек. Например, правило <условный операюр> 1Г <булево выражение> Влип <оператор> е1ве <оператор> / тГ <булево выражение> Гаеп <оператор> определяет язык, состоящий из конструкций <условный оператор>, определенных при помощи терминальных символов <булево выражение> и <оператор>, которые, в свою очередь, определяются другими правилами грамматики. Обратите внимание на то, что приведенное правило порождает два возможных вида условных операторов (разделенных вертикальной чертой !).
Каждый вариант получается посредством конкатенации различных элементов, которыми мотут быть литеральные цепочки (например, т1 или е1ве) илп синтаксические категории. Когда в правиле указывается некоторая синтаксическая категория, это означает, что в этом месте может быть использована любая цепочка символов языка, определяемого данной категорией. Например, если предположить, что категория <булево выражение> состоит из набора строк, представляющих собой некоторые логические выражения, то любое из этих выражений может быть вставлено между 1( и айеп в условном операторе.
В отечественной литературе чан»с используется понятие «нетерминальнмй символ», или просто «нетерминзлк — Примеч науч рмХ 3.3. Формальные модели трансляции 117 Другой тип грамматических правил использует рекурсивное определение синтаксической категории. Например, рекурсивное правило <целсе без знака> := <цифра>)<целсе без знака><цифра> определяет <целое без знака> как последовательность элементов <цифра>. В первом из двух вариантов <целое без знака> определяется как одна цифра, а ва втором варианте к этой исходной цифре добавляется вторая, третья и т.
д. Полная НФБ-грамматика — это просто набор подобных правил, которые в совокупности определяют иерархию языков, завершающуюся синтаксической категорией самого верхнего уровня, которая н случае языков программирования называется <про гра и ной>. В табл. 3.1 представлена более сложная грамматика, определяющая синтаксис класса простых операторов присваивания, в которой в качестве основньцх синтаксических категорий (предполагается, что они определены ранее) используются <ицентификатор> и <чиспо>. Таблица 3.1. Грамматика для простых операторов присваивания <переменнвя> = <арифметическое выражение> <терм> ) <арифметическое выражение> т <терм> ) <врифметическое выражение> — <терм> <первичное выражение> ) <терм> х <первичное выражение> ) <терм> / <первичное выражение> <переменнвя> ) <число> ) )<арифметическое выражение>) <идентификатор> ) <идентификатор> )<список индексов>1 <врифметическое выражение> ) <список индексов>, <врнфметическое выражение> <оператор присваивания>::= <арифметическое выражение>:;= <терм>с= <первичное выражение>::= <переменная>: = <список индексов> Деревья грамматического разбора Имея некоторую грамматику, мы можем последовательно использовать правила подстановки для генерации цепочек нашего языка.
Например, следующая грамматика генерирует все последовательности (цепочки), состоящие пз сбалансированных круглых скобок (то есть такие последовательности, в которых каждой открывающей скобке соответствует закрывающая): 3 ~(3)~0 Любую цепочку мы можем преобразовать путем замены любого нетерминального символа на правую часть любого правила подстановки, в которой этот нетерминальный символ имеется в леной части. Например, цепочку (()0) мы можем получить из 5 следующим образом: 1) заменяем $ по правилу Я вЂ” к (5) и получаем (5); 2) заменяем Б в (5) по правилу Я вЂ” ) 33 и получаем (ВВ); 3) заменяем первое Я в (55) по правилу Я -е 0 и получаем (0Я); 4) заменяем Б в (0Я) по правилу Я -е 0 и получаем (00).
Если использовать символ =ь для указания того, что одна цепочка выводима из другой, весь вывод можно записать следующим образом: В =о (В) ~ (33) =ь (03) =е (00) 1 18 Глава 3. Вопросы трансляции языка Каждый член этого вывода является сетглтенцигьтьяой формой, и мы формально определяем язык как множество сентенциальных форм, которые состоят только из терминальных символов' и выводимы из исходного символа грамматики. Исполъзование формальной грамматики для определения синтаксиса языка программирования важно как для программистов, использующих этот язык, так и для его разработчиков. Пользователь может получить из нее ответы на сложные вопросы относительно вида программы, пунктуации и структуры. Разработчик может испол ьзоватщ рамматику для того, чтобы опредслить все допустимые в данном языке структуры исходных программ, с которыми, возможно, придется взаимодействовать транслятору.
И программист, и разработчик имеют общее, согласованное определение, которое можно исполъзовать для разрешения споров о допустимых синтаксических конструкциях. Формальное определение синтаксиса помогает также устранению незначительных синтаксических различий между отдельными реа|щзациями языка. Чтобы определить, представляет ли данная цепочка синтаксически правильную программу на языке, определяемом НФБ-грамматикой, нужно использовать грамматические правила для проведе|щя синтаксического анализа или грамматического разбора этой цепочки.
Если разбор прошел успешно, то данная цепочка принадлежит указанному языку. Если же не удается провести ее грамматический разбор с лом о|цыо заданных правил грамматики, то она не принадлежит этому языку. На рис. 3.3 представлено дерево грамматического разбора, которое получилось в результате синтаксического анализа оператора присваивания Н = у х |0+ я с использованием НФБ-грамматики, правила которой представлены в табл. ЗыЕ НФБ-грамматнка сопоставляет каждой цепочке определяемого с ее поьющью языка некоторую структуру, как показано на рис.
3.3. Заметим, что такой структурой всегда будет дерево вниду ограничений, налагаемых на правила НФБ-грамматики. Листьями такого дерева являются отдельные символы или лексемы (лексические единицы) входной цепочки. Каждая промежуточная точка ветвления в дереве сопоставлена с некоторой синтаксической категорией, которая указывает класс, к которому принадлежит расположенное ниже ее поддерево. Корню дерева соответствует синтаксическая категория, указывающая на весь язык, — в нашем случае это категория <оператор присваивания>.
Дерево грамматического разбора предоставляет интуитивную семантическую структуру для болъшей части программы. Так, например, НФБ-грамматикадля языка Рггвса! определяет сгруктуру любой программы в виде последовательности объявлений и операторов со вложенными блоками. Структура операторов, в свою очередь, состоит из разного рода выражений, а сами эти выражения составлены из простых и индексированных переменных, примитивных операций, вызовов функций и т, д, На самом нижнем уровне даже идентификаторы и числа разлагаются на свои составные части. При изучении грамматики программист получает возможность глубже понять различные структуры, из которых составляются синтаксически правил ьн ыс программы. Важно отметить, что не все| да в грамматике данному элементу п рограм- Вьгпол заверюастси, если в веночке боль|ос пег ии одного пот срм| шала.
Отса>Г|а и название чтсрмпиальиый сиз|вот» |от аигл. |сгптгвв| — заключительный, конечный), в том смысле, что иа ием завсрюаетсв вьгвол. — П|рииеч. |гаук. ред. 3.3. Формальные модели трансляции 119 мы присваивается та структура, которая кажется для него естественной. Один и тот же язык может быть определен множеством различных грамматик, как можно легко заметить, проведя некоторые манипуляции с той траьтмати кой, что приведена в табл.3.1.
Например, в табл. 3.2 задана грамлтатика, определяющая тот же язык, что и грамматика в табл. 3.1, но заметьте, что структуры, опредсляемые этой новой грамматикой, далеки от структур, которые можно было бы определить интуитивно. <оператор присваивания> <арифметическое выражение> <переменная> <идентификатор> <терм> <терм> ! х <первичное в жение> <первичное выражение> <арифметическое выражение> ) <переменная> <идентификатор 'т' Рис. 3 3. Дерево грамматического разбора для оператора присваивания <оператор присваивания>::= <арифметическое выражение>п= <переменная> = < арифметическое выражение > <терм> ~ <арифметическое выражение> х <терм> ~ <арифметическое выражение> + <терм> <первичное выражение> ~ <терм> — <первичное выражение> ) <терм> у <первичноевыражение> <переменная> ~ <чиспо> ~(<арифметическое выражение>) <идентификатор> ~ <идентификатор> [<список индексов>) <арифметическое выражение> ) <список индексов>, <арифметическое выра:кение> <терм>п= <первичное выражение>::= <переменная>п= <список индексов> <арифметическое выражение> > <терм> ! <первичное выражение> ! <переменная> <идентификатор> Таблица 3.2.
Альтернативная НФБ-грамматика <терм> ! <первичное выражение> <переменная> ! <идентификатор> 120 Глава 3. Вопросы трансляции языка Несмотря на чрезвычайно простую структуру НФБ-грамматики, она может быть с успехом использована для определения синтаксиса большинства языков программирования. Только та область синтаксиса, которая связана с контекстной зависимостью, не может быть определена при помощи этой грамматики. 11е могут быть заданы с помощью одной лишь НФБ-грамматики такие ограничения, как, например + один и тот же идентификатор не может быть описан дважды в одном блоке; + каждый идентификатор должен быть описан в каком-либо блоке, определяющем область его использования; + на массив, определенный как двухмерный, нельзя ссылаться с помощью трех индексов.
Ограничения такого рода должны быть определены как дополнение к формальной НФБ-грамматике. В главе 4 мы обсудим некоторые формальные методы, которые помогают преодолеть недостатки модели НФБ. Процесс использования НФБ-грамматики при построении дерева грамматического разбора для определенной программы хорошо изучен. В разделе ЗА мы кратко опишем одну простую методику грамматического разбора — рекурсивный спуск — это поможет читателю составить представление о возникающих в связи с ним проблемах. Неоднозначность Как говорилось ранее, неоднозначность — это проблема синтаксиса Рассмотрим фразу «Тйеу аге йу1пя р!апезм Мы можем представить ее двумя способами: Тнеу / иге / 11у1пур1ипеж ГОни /являются /летящими самолетами.) Тнеу/игеГ1у1пд/р1ипегь ГОни/летят/самолетами.) Обе эти фразы имеют вполне определенное, хотя и различное, значение.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
