2

I'm writing a toy compiler for fun.

Basically, my problem is that I don't want to clutter the AST with stuff like debug information (symbol tokens, locations of tokens, etc) as well as data that the semantic analyzer computes.

For example, the semantic analyzer does some type inference and the result type is stored back into the Node type. It looks something like this:

/// A variable declaration in my language looks like this:
/// var x = 10
struct VarDec: Statement {
    var varKeyword: Keyword
    var varName: Id
    var assignment: Symbol
    var initializer: Expr
    var type: Optional<Type>
}

The main problem here is that now the node type has a state, type inference has either been done or not. This makes it hard to reason about. The other thing is that the whole AST gets cluttered with those tokens that are only really needed for error messages.

It has been suggested that I could create another representation of the AST just for semantic analysis that links back to the AST but that seems like a lot of work and redundant code...

Does anybody have an idea how I can clean up this code without having to create multiple trees?

2

It has been suggested that I could create another representation of the AST just for semantic analysis that links back to the AST but that seems like a lot of work and redundant code...

I don't think it means a lot of work and a lot of redundant code.

Your typed AST could mostly contain the type information, and a reference (e.g. a pointer) to the syntactic AST.

You won't have a lot of extra work: you'll need to compute the type information anyway.

You probably won't have a lot of redundant code: each AST node (so each kind of such node) needs to be processed.

FWIW, the Ocaml compiler and the GCC compiler are having several internal representations (often tree like) of the compiled source code.

An alternative might be to have several quite large associative tables mapping syntactic AST to computed attributes (including types) and grow them progressively. I am not sure it would be better (and I don't know of compilers using that, except perhaps some Prolog implementations).

0

My advise would be to keep tokens as tokens, and if anything, perform a type inference step where you wrap each node in another class or struct that does have state.

// Token type struct - immutable
struct VarDec: Statement {
    var varKeyword: Keyword
    var varName: Id
    var assignment: Symbol
    var initializer: Expr
}

// Type-checked token /w state
struct StatementTyped {
    var statement: Statement
    var type: Optional<Type>
}

In this way, you get the best of both worlds.

0

The main problem here is that now the node type has a state, type inference has either been done or not. This makes it hard to reason about.

Only to a person whose brain has been damaged by an overdose of Strict Immutability flavored Kool Aid. The reasoning is actually quite simple: if the value is null, one can clearly deduce that type inference has not run yet. If the value is not null, one can just as clearly deduce that type inference has run already. Where's the hard part?

Also, unless you're running a strict one-pass compiler, your entire AST is going to be one huge mass of mutable state, with each pass refining and simplifying things until you're ready for code generation.

The other thing is that the whole AST gets cluttered with those tokens that are only really needed for error messages.

Error messages are very important for a compiler. Aside from actually compiling working code, producing useful feedback about what the code definitely (errors) or probably (warnings) did wrong is the single most important thing a compiler can do, and if you give useless or misleading error messages, your users will hate you for it.

If you want to keep the interface of the node classes clean, though, one thing you could do is create a separate class for all the token data. Call it LexicalInfo and have it store information like the filename, starting point (line and column) and ending point (line and column, and the lines might be different if you support multiline strings) of each token.

  • Haha a little harsh but I hear you. Sure, type inference was one example but there is more the semantic analyzer does. – NSAddict Jul 21 '15 at 15:40
  • @NSAddict: Sorry. It's just that I've never understood the "difficult to reason about" line, and people who use it always state it as a fact, (or at least an article of faith,) with no evidence provided or (apparently) required, even though the burden of proof should be on the person making the claim. It's hard for someone who reasons about stuff like this all the time to see a claim like that and not come to the conclusion that the problem actually lies with the person who seems to find this to be some really hard thing to do. – Mason Wheeler Jul 21 '15 at 15:46
  • Right, maybe that was an overstatement. But its about the big picture. A compiler is very complex and keeping the bases clean is about the most important thing you can do. – NSAddict Jul 21 '15 at 17:22
  • @NSAddict: The way you "keep the bases clean" in a multi-pass compiler and make things easy to reason about is with a well-defined pipeline. Each step uses the Visitor Pattern to perform a certain operation on the AST. You can then reason that, at any given stage of the pipeline, the AST will be in a certain well-defined state because all of the transformations performed by all previous stages will be complete by that point. Keeping complexity of mutable data down to a comprehensible level is really not that difficult; you just need to apply some discipline and definition. – Mason Wheeler Jul 21 '15 at 17:28
-1

The main problem here is that now the node type has a state, type inference has either been done or not. This makes it hard to reason about.

State isn't that hard to reason about - mutable state is hard to reason about.

And you don't need mutable state to represent a syntax tree pre-inference and post-inference, you just need a placeholder type that represents and instance of "some as of yet unknown type". When you do inference, the compiler then returns new nodes with the inferences replaced with real types.

This gets you the benefit of having multiple trees without the code having multiple trees, and without the general problems that arise from mutable state.

  • 1
    -1, because 1) mutable state is not hard to reason about--programmers do it successfully all the time--and 2) your "alternative" is a distinction without a difference, except that the "replace the tree with an altered copy" version is even more complicated and has more moving parts. The only advantage it can even theoretically have over mutable state is if your AST processing is processing multiple subtrees in parallel, which is almost certainly a bad idea in a compiler backend for various reasons that should be intuitively obvious to anyone with experience in that area. – Mason Wheeler Aug 20 '15 at 17:31
  • @MasonWheeler - sure, it's not particularly harder to reason about, but in my experience actually implementing compilers, a mutating AST (where half is in one state and half another) is a pain to work with and a pain to unit test. – Telastyn Aug 20 '15 at 17:42
  • How do you figure? I've never actually experienced pain with that; the "pain" comes from inherent complexity in the task being performed. In any given stage of the pipeline, either the processing can require that the current stage's processing already be complete on a different node, or it can't. In the latter case, mutability of the AST is irrelevant; in the former, you have to stop what you're doing, look up the other node, and process it either way. If the tree is mutable, you store your results in-place on the tree and return the value; with immutability, that task becomes more complex. – Mason Wheeler Aug 20 '15 at 17:53
  • @MasonWheeler - in my experience, the issue comes in the flow of processing. Processing a node may require another node to be processed, but it hasn't been. Processing it would in turn require others to be processed (while the original node is sitting there waiting for its result). By making the tree immutable, I've found that it pushes my implementations to make fewer assumptions about processing order. – Telastyn Aug 20 '15 at 18:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.