Я пытаюсь написать компилятор для C-подобного языка в Haskell. Компилятор развивается путем преобразования АСТ. Первый проход анализирует ввод для создания АСТ, связывая узел с таблицей символов, чтобы позволить размещать символы до того, как они были определены без необходимости прямых ссылок.
AST содержит информацию о типах и выражениях, и между ними могут быть связи; например sizeof(T)
- это выражение, которое зависит от типа T
, а T[e]
- тип массива, который зависит от постоянного выражения e
.
Типы и выражения представлены типами данных Haskell, например:
data Type = TypeInt Id
| TypePointer Id Type -- target type
| TypeArray Id Type Expr -- elt type, elt count
| TypeStruct Id [(String, Type)] -- [(field name, field type)]
| TypeOf Id Expr
| TypeDef Id Type
data Expr = ExprInt Int -- literal int
| ExprVar Var -- variable
| ExprSizeof Type
| ExprUnop Unop Expr
| ExprBinop Binop Expr Expr
| ExprField Bool Expr String -- Bool gives true=>s.field, false=>p->field
Где Unop
включает в себя такие операторы, как address-of (&
) и разыменование (*
), а Binop
включает в себя такие операторы, как plus (+
) и times (*
), и т.д....
Обратите внимание, что каждому типу присваивается уникальный Id
. Это используется для построения графа зависимости типа для обнаружения циклов, приводящих к бесконечным типам. Как только мы уверены, что в графе типов нет циклов, безопасно применять к ним рекурсивные функции, не входя в бесконечный цикл.
Следующий шаг - определить размер каждого типа, назначить смещения для структурных полей и заменить ExprField
на арифметику указателя. При этом мы можем определить тип выражений и исключить ExprSizeof
s, ExprField
s, TypeDef
s и TypeOf
из графа типов, поэтому наши типы и выражения эволюционировали, а теперь выглядят более например:
data Type' = TypeInt Id
| TypePointer Id Type'
| TypeArray Id Type' Int -- constant expression has been eval'd
| TypeStruct Id [(String, Int, Type')] -- field offset has been determined
data Expr' = ExprInt Type' Int
| ExprVar Type' Var
| ExprUnop Type' Unop Expr'
| ExprBinop Type' Binop Expr' Expr'
Обратите внимание, что мы устранили некоторые из конструкторов данных и немного изменили некоторые из других. В частности, Type'
больше не содержит Expr'
, и каждый Expr'
определил его Type'
.
Итак, наконец, вопрос: лучше ли создавать два почти одинаковых набора типов данных или пытаться объединить их в один тип данных?
Сохранение двух отдельных типов данных делает его явным, что некоторые конструкторы больше не отображаются. Однако функция, которая выполняет постоянную фальцовку для оценки постоянных выражений, будет иметь тип:
foldConstants :: Expr -> Either String Expr'
Но это означает, что мы не можем выполнять постоянное сгибание позже с помощью Expr'
(представьте себе некоторый проход, который управляет Expr'
, и хочет сбрасывать любые возникшие константные выражения). Нам понадобится другая реализация:
foldConstants' :: Expr' -> Either String Expr'
С другой стороны, сохранение одного типа позволило бы решить проблему с постоянной сгибанием, но не позволяло бы проверяющим тип статическим инвариантам.
Кроме того, что мы помещаем в неизвестные поля (например, смещения полей, размеры массивов и типы выражений) во время первого прохода? Мы могли бы подключить отверстия с помощью undefined
или error "*hole*"
, но это похоже на то, что произойдет ожидание (например, NULL
указатели, которые вы даже не можете проверить). Мы могли бы изменить неизвестные поля на Maybe
s и подключить отверстия с помощью Nothing
(например, указателей NULL
, которые мы можем проверить), но в последующих проходах было бы раздражать необходимость вытягивать значения из Maybe
, которые всегда будут Just
s.