ідність новий нетермінал t1 і вводиться правило t -> arr mn t1. p> 3. Якщо нетерміналу t відповідає базовий тип rec ([f1: T1, ..., fn: Tn]), то типу Ti ставиться у відповідність новий нетермінал ti для кожного i і вводяться правила t -> Ref i fi ti. p> 4. Якщо нетерміналу t відповідає базовий тип ref (T1), де T1 = int або T1 = real, то вводиться правило t -> T1. p> 5. Якщо нетерміналу t відповідає базовий тип ref (tid (I, B)), а типом tid (I, B) вже зіставлений нетермінал t1, то вводиться правило t -> ^ t1. p> Нетермінали цієї граматики еквівалентні, якщо і тільки якщо відповідні типи структурно еквівалентні.
Залишається перетворити цю граматику до автоматного увазі і застосувати алгоритм знаходження всіх пар еквівалентних станів.
Ставлення структурної еквівалентності дійсно є еквівалентністю, тому що воно рефлексивно, транзитивній і симетрично. Крім того, два типи структурно еквівалентні тоді і тільки тоді, коли вони допускають одні й ті ж послідовності операцій. Це робить таку еквівалентність простий і зрозумілою програмістам. Її основним і досить істотним недоліком є складний і громіздкий алгоритм перевірки еквівалентності. Наскільки відомо автору, структурна еквівалентність була прийнята тільки в мові Алгол 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. Іменований тип еквівалентний сам собі. p> 2. Якщо тип T = tid (I, B) має опис declared (I, B, T1), де T1 - іменований тип, то типи T і T1 еквівалентні. p> Це дуже обмежувальне визначення. Навіть у Паскалі допустимо присвоювання
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 або ^ (тобто не є ідентифікатором типу), вводить унікальне ім'я типу - псевдонім, завдяки чому різні входження одного і того ж вирази типу виявляються нееквівалентними в сенсі іменний еквівалентності. p> У відповідності зі сказаним слід внести зміни в правила DC-граматики для нетермінала type, що визначають атрибут типу. У них включається тепер породження і опис псевдонімів типу. Для генерації нових "імен" можна використовувати самі різні методи; ми тут скористаємося предикатом recorda, генеруючому як псевдонім унікальну посилання...
