41569 (686874), страница 2

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

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

X: Real;

Y: Array [1..3] Of Integer Absolute X;

Эквивалентность типов

Относительно понятия эквивалентности типов существует несколько точек зрения. Рассмотрим три из них. Все они исходят из того, что эквивалентные типы должны допускать одинаковые последовательности операций.

Структурная эквивалентность

Два атрибута типа T1 и T2 называются (структурно) эквивалентными, если

• их базовые типы BT1 и BT2, соответственно, совпадают или

• BT1=arr(M,N,T1'), BT2=arr(M,N,T2') и T1' эквивалентен T2', или

• BT1=rec([F1:T11,...,Fn:T1n]), BT2=rec([F1:T21,...,Fn:T2n]) и T1i эквивалентен T2i для каждого i, или

• BT1=ref(T1'), BT2=ref(T2') и T1' эквивалентен T2' и

• предположение об эквивалентности T1 и T2 не противоречит условиям 1-4.

Несколько странное условие 5 связано с рекурсивностью типов. Оно делает отношение структурной эквивалентности наибольшим среди отношений, удовлетворяющих условиям 1-4.

П р и м е р:

Пусть

T1=rec([info:int,next:T1])

T2=rec([info:int,next:T2])

Применяя только правила 1-4, получим, что T1 и T2 эквивалентны, если T1 и T2 эквивалентны. Правило 5 заставляет сделать вывод, что T1 и T2 действительно эквивалентны (на основании только правил 1-4 можно сделать и обратный вывод).

Если бы не было ссылочных и, следовательно, рекурсивных типов (как в Фортране или Алголе 60), то определение структурной эквивалентности сводилось бы к условию 1, т.е. к равенству базовых типов.

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

Сначала строится праволинейная грамматика:

1. Для каждого описания идентификатора типа, переменной или параметра declared(I,B,Inf), где Inf равно type(T), var(T) или par(T), типу T ставится в соответствие новый нетерминал t.

2. Если нетерминалу t соответствует базовый тип arr(m,n,T1), то типу T1 ставится в соответствие новый нетерминал t1 и вводится правило t -> arr m n t1.

3. Если нетерминалу t соответствует базовый тип rec([f1:T1,...,fn:Tn]), то типу Ti ставится в соответствие новый нетерминал ti для каждого i и вводятся правила t -> ref i fi ti.

4. Если нетерминалу t соответствует базовый тип ref(T1), где T1=int или T1=real, то вводится правило t -> T1.

5. Если нетерминалу t соответствует базовый тип ref(tid(I,B)), а типу tid(I,B) уже сопоставлен нетерминал t1, то вводится правило t -> ^ t1.

Нетерминалы этой грамматики эквивалентны, если и только если соответствующие типы структурно эквивалентны.

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

Отношение структурной эквивалентности действительно является эквивалентностью, т.к. оно рефлексивно, транзитивно и симметрично. Кроме того, два типа структурно эквивалентны тогда и только тогда, когда они допускают одни и те же последовательности операций. Это делает такую эквивалентность простой и понятной программистам. Её основным и весьма существенным недостатком является сложный и громоздкий алгоритм проверки эквивалентности. Насколько известно автору, структурная эквивалентность была принята только в языке Алгол 68.

Предикат consist в этом случае определим следующим образом:

consist(T1,T2):base_type(T1,BT1),base_type(T2,BT2),

(BT1=int,BT2=real ; % приводимость

equiv(BT1,BT2) ; % эквивалентность

error("Несовместимые типы")).

Именная эквивалентность

При стандартизации языка Паскаль была принята именная эквивалентность. Согласно её определению эквивалентными могут быть только именованные типы, т.е. типы с атрибутами int, real или tid(_,_):

1. Именованный тип эквивалентен сам себе.

2. Если тип T=tid(I,B) имеет описание declared(I,B,T1), где T1 – именованный тип, то типы T и T1 эквивалентны.

Это очень ограничительное определение. Даже в Паскале допустимо присваивание

U:=V,

если переменные U и V описаны как

var U,V: array[1..10]of real,

хотя имеют неименованный тип "массив". Но в том же Паскале этот оператор недопустим из-за неэквивалентности типов переменных, если они описаны как

var U: array[1..10]of real;

var V: array[1..10]of real;

Чтобы охватить все эти случаи, компилятор для каждого вхождения выражения типа, начинающегося с array, record или ^ (т.е. не являющегося идентификатором типа), вводит уникальное имя типа – псевдоним, благодаря чему разные вхождения одного и того же выражения типа оказываются неэквивалентными в смысле именной эквивалентности.

В соответствии со сказанным следует внести изменения в правила DC-грамматики для нетерминала type, определяющие атрибут типа. В них включается теперь порождение и описание псевдонимов типа. Для генерации новых "имен" можно использовать самые разные методы; мы здесь воспользуемся предикатом recorda, генерирующем в качестве псевдонима уникальную ссылку на пустой терм, записываемый по ключу alias. описание этого псевдонима типа включается в виде предиката declared.

type(B,tid(A,B)) -->

[array,`[,n(M),`:,n(N),`],of],type(B,T),

{recorda(alias,_,A),

assert(declared(A,B,type(arr(M,N,T)))}.

type(B,tid(A,B)) -->

[record],field(B,F),fields(B,LF),

{correct(F,LF),

recorda(alias,_,A),

assert(declared(A,B,type(rec([F|LF])))},

[end].

type(B,tid(A,B)) -->

[`^,id(I)],

{(type_id2(I,B,B1,type(_));

assert(declared(I,B,type(referred))),

B1=B),

recorda(alias,_,A),

assert(declared(A,B,type(ref(I,B1)))}.

Предикат consist в этом случае определяется следующим образом:

consist(T1,T2):T1=int,T2=real ; % приводимость

equiv(T1,T2) ; % эквивалентность

error("Несовместимые типы").

equiv(T,T).

equiv(tid(I,B),tid(I1,B1)):declared(I,B,type(tid(I1,B1)));

declared(I1,B1,type(tid(I,B))).

Именная эквивалентность сравнительно просто реализуется. Но это – отношение (рефлексивное и симметричное) не транзитивно, и поэтому не является эквивалентностью ни в математическом, ни в привычном, обыденном смысле. Понятие псевдонима типа обычно не даётся программистам, Поэтому начинающие программисты на Паскале часто делают ошибки, вроде указанных в примере. Мотивацией для введения именной эквивалентности в 1970-е годы послужило желание избежать ошибок программирования, вроде присваивания "яблокам" "крабов", когда и те, и другие описаны как целые. С развитием объектно-ориентированного программирования подобные ухищрения стали излишними, а именная эквивалентность осталась в некоторых языках как анахронизм.

Структурно-именная эквивалентность

Этот тип эквивалентности самый простой: эквивалентными считаются типы, имеющие одинаковый базовый тип. Предикат consist в этом случае определяется следующим образом:

consist(T1,T2):base_type(T1,BT1),base_type(T2,BT2),

(BT1=int,BT2=real ; % приводимость

BT1=BT2 ; % эквивалентность

error("Несовместимые типы")).

При этом нет необходимости вводить псевдонимы типа, как в случае именной эквивалентности. Вместо предиката acc_type при анализе доступа можно применять предикат base_type.

Отношение структурно-именной эквивалентности рефлексивно, симметрично и транзитивно. По вложению оно лежит строго между структурной и именной эквивалентностями. Им легко пользоваться на практике.

Примеры

1.

С помощью несложной программы мы сможем узнать внутренний код произвольного символа.

Program Code_pf_Char;

{Программа читает символ с клавиатуры и выводит на экран

этот символ и соответствующий ему внутренний код}

var

ch: Char; {В эту переменную читается символ}

begin

Write('Введите любой символ: ');

ReadLn(ch); {Читаем один символ}

WriteLn(ch, ' = ',ord(ch)); {Преобразуем его к целому и выводим на экран}

END.

Обращаем внимание: при вызове

WriteLntch,' = ',ord(ch));

третьим параметром обращения указан вызов функции ORD (СН) , что с точки зрения языка является выражением; во многих случаях при вызове процедур и функций в качестве параметров вызова можно указывать не только переменные или константы, но и выражения с их участием.

2.

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

Непроизносимые гласные:

Сочетания "вств" и "стн" транскрибируются как [ств] и [сн] соответственно, т. е.:

1) /вств/ -> [ств]

2) /стн/ -> [лнц]

Реализация двух данных правил на языке Паскаль:

program transcription;

var

Word: String;

I, J, K: Integer;

begin

Write('Введите слово: '); ReadLn(Word);

K := Pos('вств', word);

while (K 0) do

begin

delete(Word, K, 1);

K := Pos('вств', Word);

end;

K := Pos('стн', Word);

while (K 0) do

begin

delete(Word, K+1, 1);

K := Pos('стн', Word);

end;

WriteLn('Транскрипция: ', Word);

end.

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

Список литературы

Для подготовки данной работы были использованы материалы с сайта http://2balla.ru

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

Список файлов курсовой работы