Карпов - Основы построения трансляторов (2005) (943926), страница 16
Текст из файла (страница 16)
3.4). Таблица 3.4. Атрибутная грамматикадвоичных чисел Здесь значения атрибутов всех нетерминалов, стоящих в левых частях правил грамматики, определяются через значения атрибутов их непосредственных потомков в правых частях правил (т. е. все атрибуты — синтезированные). Структуру дерева вывода любой цепочки в этой грамматики можно расширить, добавив атрибуты и их значения во всех узлах. Аннотированное дерево рис.
3.7 показывает, что значение строки 110.01 есть 6.25 в десятичной записи. Вычисления значений этих синтезированных атрибутов происходит по дереву снизу вверх в соответствии с правилами, определенными в атрибутной грамматике табл. 3.4. Структура и значение Рис. 3.7. Аннотированное дерево вывода цепочки 110.01 Семантические атрибуты для нетерминалов данной грамматики и способ построения функциональных зависимостей между ними могут различаться, даже если мы хотим приписать один и тот же смысл цепочкам порождаемого языка.
Для той же грамматики бз2, порождающей двоичные вещественные числа, можно построить совершенно другую семантику, эквивалентную семантике атрибутной грамматики табл. 3.4. Определим для нетерминалов той же грамматики С другие семантические атрибуты (табл. 3.5). Таблица 3.5. Определение для грамматики б,, других семантических атрибутов Нетерминал Примечание Атрибут 1 — целочисленное значение, приписываемое двоичному символу, представленному  — масштаб (вес) данного двоичного символа В 1 — значение, приписываемое подцепочке двоичных символов выведенных из 1., с учетом их положения во всей ичных символов, выведенных из У. епочки двоичных символов, выве- ~ денных из 1.
— — — + — —— ! 5.1 1:- — значение, приписываемое двоичной цепочке символов, выведенных из 5 На основе этой таблицы атрибутов следует изменить семантические функции, связанные с грамматикой 6;., для вычисления численного значения двоичной цепочки. Построим следующую атрибутную грамматику, позво- УОО Глава 3 ляющую получать искомый результат — численное значение каждой двоич- ной цепочки (табл. 3.6). Т а бл и ца 3.6. Атрибутная грамматика 3.3.2. Координаты мобильного робота Рассмотрим другую задачу. Пусть для управления мобильным роботом ис- пользуется язык, предложение которого — это перечисление отдельных ша- гов движения робота в направлениях север, ~ог, запад, восток. Пример пред- ложения языка: Ьерп север запад север север запад юг восток север епд. Перемещение мобильного робота происходит на координатной плоскости, каждый шаг имеет длину 1.
Шаг на север увеличивает на 1 вторую координа- ту робота, шаг на юг уменьшает значение его второй координаты на 1. Оче- видные изменения первой координаты происходят и при движениях робота на запад и восток. Начальное положение робота — координата (О, 0). Построим атрибутную грамматику, позволяющую вычислить окончательные координаты робота по любому предложению языка управления. Синтаксиче- Каждый бит двоичного числа, порождаемый из нетерминала В, имеет в цепочке битов свой индивидуальный вес 2"', с которым он входит в суммарное значение числа. Этот вес определяется масштабом ~, указывающим положение этого символа относительно запятой.
Атрибут.л приписан и цепочке символов, выводимых из нетерминала Е, он имеет значение положения относительно запятой крайнего правого бита цепочки, выводимой из Л. Атрибуты "масштаб" цепочек символов Х, и цепочек символов В, стоящих в правой части правила 2 грамматики, вычисляются через атрибуты правой части (иными словами, через атрибуты предков) и являются унаследованными. Поэтому в общем случае последовательность вычислений по аннотированному дереву вывода в атрибутной грамматике проходит дерево не только снизу вверх, но и в различных направлениях.
Структура и значение ские правила грамматики можно построить многими способами. Пусть КС грамматика языка выглядит так: Я вЂ” +Ьефп Мепд М вЂ” +Мй ~.0 0 — ~север ~ юг ~ запад ~ восиок Свяжем с нетерминалами Я и М один векторный параметр ~ =(х„у), имею щий смысл пары координат, приписанных этому нетерминалу ~более точно координат мобильного робота, который из начальной точки прошел путь, вы водящийся из этого нетерминала). Такой же параметр свяжем с нетермина лом Х)„он будет иметь смысл приращения координат. Параметр 1, приписан ный начальному символу грамматики Я, будет давать искомые координать робота после прохождения всего пути, который выводится из 5.
Атрибутна~ грамматика этого языка будет иметь вид, представленный в табл. 3.7. Аннотированное дерево вывода цепочки Ьерп север север ~ог запад север восток север епд приведено на рис. 3.8. Все атрибуты здесь синтезирован ные. Вычисление вектора, определяющего координаты робота после прохож дения им всего пути, выполняется по правилам приведенной выше атрибут ной грамматики. Рис. 3.8. Аннотированное дерево вывода, показывающее вычисление координат мобильного робота Структура и значение Эта цепочка имеет два различных дерева вывода (рис.
3.9). Как терминалы, так и нетерминалы снабжены здесь индексами. чтобы иметь возможность идентифицировать их. Рис. 3.9. Различные деревья вывода цепочки аФИе о бо я1, .я2 Поскольку семантические вычисления основываются именно на дереве вывода, очевидно, что различные деревья вывода могут привести к различным интерпретациям этой цепочки. Пусть семантический параметр„сопоставленный каждому нетерминалу грамматики, — это блок последовательных вычислений с одним входом и одним выходом. Терминалу ю сопоставим простейший блок. Например, можно его интерпретировать, как оператор присваивания. Тогда в соответствующей атрибутной грамматике каждому синтаксическому правилу (продукции) естественно сопоставить семантические правила получения структуры сложного блока (соответствующего левой части продукций) из более простых (табл.
3.8). Построенная по этим правилам интерпретация цепочки 1~ЬНе о до ю1', ь~ на основе двух различных деревьев вывода рис. 3.9 представлена ниже. Табл и ца 3.8. Лтрибутная грамматика б„~„~, оператора цикла Глава 3 Таблица 3.8 (окончание) Рис. 3.10. Интерпретация цепочки ~иЫ!е Ь бо з1, з2 (б) на основе одного из ее возможных деревьев вывода в грамматике б ~о, (а) Глава 3 в языках программирования затрудняют понимание языка: представление программиста о структуре цепочек и та структура, которую будет выбирать для интерпретации транслятор, могут не совпадать, и этого можно не заметить.
Следует обратить внимание, что неоднозначные грамматики иногда используются в информатике, но они обязательно сопровождаются дополнительными комментариями и правилами для разрешения противоречий. Эти правила должны учитываться как разработчиком транслятора при реализации транслятора, так и программистом при написании программ. Для того чтобы в грамматике б„~„~,. избавиться от такой неоднозначности, можно изменить синтаксис, например, можно ввести правило обязательного "закрытия скобок" после оператора цикла.
А именно. понимая служебное слово до как открывающую скобку, введем од как закрывающую: б'„д„. Š— +Я~Я; А 5-+ъ Ы1е 6 до Л од ~ л В качестве закрывающей скобки можно использовать и служебное слово еид. Будет ли однозначной эта новая грамматика? Мы увидим далее. что ответ на этот вопрос положителен. Однако в общем случае проблема однозначности КС-грамматик (т. е.
проблема определения того, что любая цепочка языка, порождаемого данной грамматикой, имеет только одно-единственное дерево вывода) является неразрешимой ~с;и. главу 4~, 3.4.2. Грамматика условных операторов Очень похожа ситуация с грамматикой, задающей условный опер пор в языке Милан. Для простоты будем считать, что в условном операторе может встретиться только оператор, а не список операторов. Соответствующая грамматика определяется так: 0,~. Я-+Ы Ь 1'пеп Я е!ве 5' ~ !К Ь 1'пеп Я ~ т Очевидна семантика этих правил.
Табл. 3.9„ставящая в соответствие каждой продукции семантическое правило, представлена ниже. Оказывается, эта грамматика двусмысленна. Например, для цепочки: Ы Ь~ $Ьеп Ю о2 Феп ю1еЬе л~ можно построить два дерева вывода. Эти деревья вывода определяют различную интерпретацию этой цепочки в соответствии с семантическими правилами табл. 3.9. Одно из возможных деревьев вывода представлено на рис. 3,12. В соответствии с ним вся цепочка, рассматриваемая как один оператор Ло, представляет собой полный условный оператор Ю Ь~ Феп 5~ еЬе Ь.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
