Системы программирования (1119744), страница 7

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 7)

Нужно сделать еще одно замечание, касающееся описанного алгоритма. Как определить, какие именно функции попадают в множество “испытуемых”? Ответ таков: все функции с таким именем, которые могут быть вызваны с таким набором фактических параметров. Это правильно кажется тривиальным, однако оно может помочь в ситуации, когда у некоторых функций есть значения по умолчанию, а у некоторых - '...' в списке параметров.

Шаблоны функций.

Настало время поговорить о типовом полиморфизме. Эта идея в C++ появилась не впервые, она была реализована ещё в языка Ada.

Многие функции делают примерно одно и то же, но работают с разными типами данных. Например, алгоритм сортировки почти не зависит от типа сортируемых элементов. Мы можем описать шаблон, который можно настраивать на типы. Просто надо будет написать соответствующие функции сравнения и т.д.

Пример.

int max (int x, int y) { return x>y? x: y; }

Сделаем теперь функцию независимой от типов.

template<class T> T max (T x, T y) { return x>y? x: y; }

У этой функции только типовые параметры. Ключевое слово class не значит, что T должен быть пользовательским типом. Можно передавать данные встроенных типов точно также. (Создатели языка опять не придумали нового ключевого слова)

Параметров шаблона может быть несколько, тогда они перечисляются через запятую.

void f() {

max (1,2);

/* по параметру автоматически определяется тип шаблона.

вызовется int max<int> (1,2) */

max (‘0’,’a’); // от char

max (‘a’,100); // неоднозначность. так нельзя!!

max (2.5,1); // неоднозначность. int или double ???

Можно, конечно, указывать явное преобразование одного из аргументов (громоздко и неудобно) или вводить для каждого из параметров отдельный тип (но тогда нужна особая операция сравнения). Но есть и две хорошие возможности разрешить неоднозначность:

• явная квалификация: max<int> (‘a’,100);

• перегрузка шаблонных функций:

int max (char c, int i) { return c>i? c: i; }

Можно перегрузить шаблон и так:

int max (int x, int y) { return x>y? x: y; }

Теперь нам непонятно, что вызывать: шаблонную функцию или явную? Модифицируем наш алгоритм поиска best matching функции, добавив шаг между 1 и 2. На первом шаге, не думая о шаблонах, ищем точное соответствие. На новом, *полуторном* шаге, пытаемся сгенерировать подходящую функцию по шаблону, чтобы получить точное соответствие. Если попытка неудачная, переходим к шагу 2 и далее выполняем алгоритм, как и раньше.

Тип параметра шаблона, как указано выше, можно указать и явно. Эта возможность относительно новая в языке. Об этом пишет Бьярн Страуструп в интереснейшей книге ‘Дизайн и эволюция языка C++’. В некоторых ситуациях не обойтись без явного указания.

Пример такой ситуации.

template<class T, class U> T convert (U u) { ... return t; };

void g (int i){

convert (i); // U = int; T – непонятно 

}

Надо учитывать, что при поиске соответствия компилятор не обращает внимания на то, чему мы присваиваем результат работы функции. Контекст не рассматривается!

Из этой ситуации можно выйти так:

convert<double> (i); // U = int; T = double

При спецификации типа указанный тип подставляется на место первого параметра, если указаны два типа – на место первого и второго, и так далее.

Мы можем придать новый смысл функции, например, заставить искать максимальный элемент в массиве. Для этого перегрузим её так:

template<class T > T max (T *p, int size) { ... };

А сможем ли мы искать с помощью нашей шаблонной функции максимум среди об’ектов класса Complex, описанного нами выше? То есть, можно ли написать так:

Complex a(1,2), b(3,4);

max (a,b); // T = Complex

Проблема, очевидно, в том, что в классе не определены операции сравнения. Однако у ТВ как-то получилось это скомпилировать (правда, в Microsoft Visual Studio). Программа даже запустилась и выдала результат! Но результат совершенно не подвластен здравому смыслу. Вы можете попробовать сделать то же самое в g++ и если что покопаться в исходниках и удовлетворить всеобщий интерес рассказом о том, что там происходит.

Вообще, к сожалению, компиляторы далеко не всегда хорошо держат стандарт при работе с шаблонами.

Шаблоны классов.

Шаблоны классов тоже зачастую бывают разумными. Как правило, они применяются при описании контейнеров, то есть типов, которые содержат в себе каким-то образом структурированные об’екты других типов. Например, стек можно реализовать как контейнер. Операции над ним, вообще говоря, не зависят от типа его элементов.

Пример. Контейнер-вектор.

template<class T> class Vector {

T *p;

int size;

public: explicit Vector (int);

T& operator[] (int i);

};

Vector<int> x(20); // вектор из 20 целых чисел

Vector<Complex> y(100); // вектор из 20 комплексных чисел

Инстанцирование – процесс генерации класса по шаблону.

Любая функция из шаблонного класса является шаблонной, так что описывать функции вне класса нужно так:

template<class T> T& Vector<T>::operator[] (int i) { ... }

Пример. Класс с нетиповым параметром.

template<class T, int size> class buffer { ... }

buffer <char,1024> x;

buffer <char,512*2> y;

buffer <int,1024> z;

Возникает вопрос, какие переменные будут иметь одинаковые типы? Есть общее правило: инстанцированные классы будут считаться одинаковыми, если типовые параметры совпадают, а нетиповые равны по значению. x и z, очевидно, разного типа, так как типовые параметры не совпадают. Для нетиповых параметров должна быть определена операция сравнения на равенство. Получается, что параметры шаблона не могут быть вещественными.

Еще одно замечание: нетиповые параметры могут быть только у шаблонов классов, но не у шаблонов функций (так сказала ТВ; но как быть со вставкой выше?).

/* на этом изложение теории языка C++ считается законченным. На лекциях ещё будет рассказ о STL, но это хз когда. */

ЧАСТЬ II

Классическая система программирования. Элементы теории трансляции.

Состав и схема функционирования классической системы программирования (этапы кодирования, тестирования и отладки)

Ассемблер появляется на этапе компиляции, так как в программе могут быть ассемблерные вставки, а также компиляторы иногда переводят программу в ассемблерный код.

Об’ектная программа – машинно-ориентированное представление исходной программы, семантически эквивалентное программе в машинных кодах с неразрешёнными внешними ссылками, содержащие также таблицы с информацией о внешних ссылках, именаз переменных и т.д.

Исполняемый файл – единое целое в машинном коде, адреса отсчитываются относительно некоторого условного адреса.

Транслятор, компилятор, интерпретатор.

Транслятор – это нечто, что может помочь человеку, написавшему программу на языке высокого уровня, обеспечить её выполнение в рамках некоторой среды.

Трансляторы бывают компиляторы и интерпретаторы.

Компилятор действует так.

А так работает интерпретатор.

Интерпретатор считывает исходную программу, предложение за предложением, и выполняет её построчно.

Общая схема работы компилятора.

оаврп

Пример (неоднозначность в языках программирования).

Пусть у нас есть правило вида

S -> if b then S else S | if b then S | a

Вопрос: как разбирать следующую цепочку? -

if b then if b then a else a

Варианты:

if b then (if b then a) else a

if b then (if b then a else a)

Здесь различна сама семантика выполнения условного оператора. Как же решать такую проблему? Можно, конечно, полностью запретить ситуации с подобной неоднозначностью, а можно положиться (в каждом конкретном случае) на алгоритм разбора, требуя от него выбора заранее предписанного варианта. Заметим, что в данном случае возможно описать другую грамматику, свободную от этой проблемы:

S -> if b then S | if b then S' else S | a

S' -> if b then S' else S' | a

Проблема однозначности грамматик в общем случае алгоритмически неразрешима, однако можно анализировать частные случаи. «Симптомами» неоднозначности грамматики можно считать правила вида:

A -> AA | α

A -> AαA | β

A -> αA | Aβ | γ

A -> αA | αAβ | γ

Зададимся вопросом: для любого ли языка можно записать однозначную грамматику, его порождающую? Оказывается, это не так. Будем называть язык неоднозначным, если его нельзя описать ни одной однозначной грамматикой.

Пример неоднозначного языка:

L = {aⁱb^jc^k, i=j либо j=k}

Неоднозначность L строго доказана. Не останавливаясь на доказательстве, поясним его схему «на пальцах». Чтобы построить цепочку с i=j, нужно контролировать выполнение именно этого равенства, а генерация произвольного числа k символов c будет выполняться независимо. Симметричная ситуация и с другим вариантом: отслеживание j=k и приписывание цепочки из i a. Ясно, что процесс генерации цепочки с самого начала может пойти либо по одному, либо по другому пути, однако и в том, и в другом случае возможно построить цепочку с i=j=k, которая, таким образом, будет иметь более одного дерева вывода.

Регулярные грамматики

Еще более сузим класс рассматриваемых грамматик и рассмотрим для него схему построения «синтаксических» деревьев. Когда мы рисовали деревья вывода для условного оператора, мы делали это по схеме «сверху вниз », т.е. от корня к вершине (для дерева как структуры данных корень обыкновенно представляется либо изображается сверху, что и дает название нашему методу). Берем цель грамматики и пытаемся «развернуть» ее различными способами, подставляя в получаемые цепочки выражения для возникающих при этом нетерминалов. Когда все листья дерева будут помечены лишь терминальными символами, построение дерева можно считать оконченным. При этом необходимо так или иначе следить за соответствием символов из разбираемой цепочки тем символам, которые возникают при построении дерева: наша цель, напомним, составить дерево разбора для некоторой конкретной цепочки. Можно, однако, действовать и иначе: исходить из поданных «на вход» терминальных символов и пытаться «свернуть» их в нетерминалы и, в конечном итоге, в цель грамматики, строя, таким образом, дерево «снизу вверх », от листьев к корню. Для регулярных грамматик такой метод особенно удобен. Чтобы работать с символами цепочки слева направо, нам нужна леволинейная грамматика:

Пример.

S -> A┴

A -> Ab | Bb | b

B -> Aa

Символ ┴ - это так называемый маркер конца – удобный символ для обозначения конца цепочки. Его использование зачастую значительно упрощает работу.

Рассмотрим построение дерева разбора для цепочки babb┴.

Ясно, что в каждый момент разбора достаточно только двух первых символов: при начале работы – стартовых символов цепочки, далее – только что построенного нетерминала и следующего входного символа.

Характеристики

Список файлов ответов (шпаргалок)