Evolving data structure

I'm trying to write a compiler for a C-like language in Haskell. The compiler progresses by transforming an AST. The first pass parses the input to create the AST, tying a knot with the symbol table to allow symbols to be located before they have been defined without the need for forward references.

The AST contains information about types and expressions, and there can be connections between them; e.g. sizeof(T) is an expression that depends on a type T, and T[e] is an array type that depends on a constant expression e.

Types and expressions are represented by Haskell data types like so:

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

Where Unop includes operators like address-of (&), and dereference (*), and Binop includes operators like plus (+), and times (*), etc...

Note that each type is assigned a unique Id. This is used to construct a type dependency graph in order to detect cycles which lead to infinite types. Once we are sure that there are no cycles in the type graph, it is safe to apply recursive functions over them without getting into an infinite loop.

The next step is to determine the size of each type, assign offsets to struct fields, and replace ExprFields with pointer arithmetic. In doing so, we can determine the type of expressions, and eliminate

1 Answer

There's no ideal solution to this problem, since each one has different pros and cons.

I would personally go with using a single data type "tree" and add separate data constructors for things that need to be differentiated. I.e.:

data Type
  = ...
  | TypeArray Id Type Expr
  | TypeResolvedArray Id Type Int
  | ...

This has the advantage that you can run the same phase multiple times on the same tree, as you say, but the reasoning goes deeper than that: Let's say that you are implementing a syntax element that generates more AST (something like include or a C++ template kind of deal, and it can depend on constant exprs like your TypeArray so you can't evaluate it in the first iteration). With the unified data type approach, you can just insert the new AST in your existing tree, and not only can you run the same phases as before on that tree directly, but you will get caching for free, i.e. if the new AST references an array by using sizeof(typeof(myarr)) or something, you don't have to determine the constant size of myarr again, because its type is already a TypeResolvedArray from your previous resolution phase.

You could use a different representation when you are past all of your compilation phases, and it is time to interpret the code (or something); then you are certain of the fact that no more AST changes will be necessary, and a more streamlined representation might be a good idea.

By the way, you should use Data.Word.Word instead of Data.Int.Int for array sizes. It is such a common error in C to use ints for indexing arrays, while C pointers actually are unsigned. Ple

answered 2012-05-25T23:04:10.760

Evolving data structure

1 Answer

Your Answer