Разработка компиляторов
Представление типов
Удобным путем представления выражений над типами являются графы. Мы можем конструировать деревья или DAG'и (ориентированные ациклические графы), листьями которых будут примитивные типы. Например:
Использование dag'ов более предпочтительно, поскольку в этом случае происходит иногда весьма значительная экономия памяти (вместо самих типов в этом случае хранится ссылка на них).
Мы можем использовать и линейное представление деревьев или dag'ов, например,
proc, 2, m1, m2, m2, где m1 - указатель в таблицу на тип pointer, integer, а m2 - указатель в таблицу на тип char.
Рассмотрим еще один способ кодирования типов, который был использован в компиляторе C, разработанном Ричи (D.M.Ritchie). Ограничимся тремя конструкторами типов: указателями, функциями и массивами: pointer (t) обозначает указатель на тип t , freturns (t) обозначает функцию от некоторых аргументов, которая возвращает значение типа t и, наконец, array (t) обозначает массив некоторой неопределенной длины элементов типа t . Приведем примеры типов:
char freturns (char) pointer (freturns (char)) array (pointer (freturns (char))).
Каждый из этих типов может быть представлен последовательностью битов. Поскольку у нас есть только три конструктора типа, мы можем использовать для кодирования два бита:
pointer 01 array 10 freturns 11
Примитивные типы кодируются четырьмя битами:
boolean 0000 char 0001 integer 0010 real 0011
Используя такой способ кодирования, приведенные выше типы мы можем закодировать следующим образом:
char 000000 0001 freturns (char) 000011 0001 pointer (freturns (char)) 000111 0001 array (pointer (freturns (char))) 100111 0001
Теперь вернемся к обсуждению структуры таблицы идентификаторов. Одно из полей ( toMode ) мы собирались использовать для определения типа идентификатора. Определив представление типов, которые могут появиться в программе, мы можем теперь зафиксировать, что поле toMode в - это либо указатель на дерево или dag , либо ссылка в таблицу типов ModeTab , хранящую линейное представление типов.
