Предыдущая страница реферата | 2  3  4  5  6  7  8  9  10  11  12 | Следующая страница реферата

Применяя только правила 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,

Рекомендуем скачать другие рефераты по теме: сочинение сказка, рефераты,, оформление доклада титульный лист.



Предыдущая страница реферата | 2  3  4  5  6  7  8  9  10  11  12 | Следующая страница реферата

Поделитесь этой записью или добавьте в закладки