6

I am writing a compiler, for which I devised a rather classic architecture: it's composed of sequential passes piped together, starting with a lexer and a parser, continuing with a macro processor, then a semantic analysis/type checker pass, and finally an intermediate code generator (and maybe IR optimizer that will come later).

My current approach is the following. The parser is building an AST, where each type of AST node inherits from an "AST" base class. I plan that virtual functions of the AST will implement the functionality of subsequent passes. To provide a simplified example:

  • macroExpand() finds, evaluates and substitutes all the macros in the AST, recursively;
  • typeCheck() performs type checking, type inference and general semantic analysis/error checking on the now-desugared tree, completing each node with type annotations (which are implemented as member variables);
  • codeGen(), finally, generates some kind of IR from the annotated AST.

However, I'm afraid that having all this functionality in one single class violates the single-responsibility principle.

I reckon that macro expansion especially does not fit in: I was thinking about integrating semantic analysis and code generation into just one set of functions instead of separating them, simply because I don't think I need to traverse the entire tree twice, and I would have to look at the types at codegen time anyway, even if I've pre-inferred and pre-checked them previously.

But even with this structural change, there are still at least two completely different sets of methods on my AST classes. I don't yet see any particular reason why this in itself would be bad in my specific case, but I'm pretty sure the single responsibility principle was discovered for a good reason.

One way to remedy (?) this issue would be to use the visitor pattern and write separate visitor class hierarchies for the AST for each purpose (macro expansion, semantic analysis and/or code generation). But I really don't feel like doing so. (In all honesty, I really dislike the idea.) So far it only seems to introduce unnecessary complexity and burden (by means of forcing me to maintain parallel class hierarchies).

Currently, I'm writing this compiler in C++, but I'm pretty sure that if I were using a language that permitted after-the-fact modification and augmentation of classes (e.g. Objective-C categories), I would surely make use of this feature of the language and I would just decorate my base AST classes with the necessary set of methods, independently of the "core" interface and implementation of said classes.

I could sort of simulate that in C++ by putting all the method declarations in one header file, but writing the implementation of each category of functions in different implementation files. This, however, contradicts the usual "one class, one file" practice.

To sum up, my question is: is my current approach of giving two or three different functionality to one class really bad?

  • If so, are any of my suggested fixes considered to be good practice, or…

  • If it isn't, can you suggest something better?

  • 1
    I'm a really big fan of the Visitor Pattern for this kind of stuff. I think of the Visitor Pattern as enabling Extension Methods on my AST hierarchy, so that the responsibility of an AST transformation can be separated from the AST itself. And you don't really end up with parallel class hierarchies in the standard GoF visitor implementation (though a separate representation for each phase would probably simplify your code). Multiple passes are no big deal unless you're micro-optimizing already. – amon Oct 9 '15 at 20:55
  • 1
    Unlike @amon, I hate visitor pattern, but if you aren't using JS or Ruby or something else where you can easily subdivide a class, it's what you're stuck with if you want to keep responsibilities separate. – sqykly Oct 10 '15 at 15:55
  • @sqykly I despise the visitor pattern too. As I said, if I were writing this in a language that supports extending classes post-compilation, I would just extend the AST classes with code generation. I finally ended up doing a bunch of if (auto node = dynamic_cast<…>())s; it's a little bit C-is (in C, I usually put a type field into the AST and switch on it during AST traversal), but it's still better than 1. forcing everyone to accept the gorilla (codegen) that comes with the banana (AST), and 2. forcing myself into the cage of visitor patterns… – H2CO3 Oct 11 '15 at 6:57
  • To clarify my comment, I do think that if you are stuck writing C++, visitor pattern is the least worst case. Doesn't mean anyone has to like it. – sqykly Oct 12 '15 at 5:49
2

You're bumping up against a classic problem in programming language theory, the expression problem. It exposes a weakness of both classic object-oriented design (that it's hard to add operations to a data structure with multiple subtypes) and algebraic data types (that it's hard to add new type cases to an adt when there are multiple operations defined on it).

There are various solutions; the visitor pattern is certainly a common one, but in my opinion object-oriented pattern matching is probably the nicest - there's an implementation for c++ here.

  • +1. Probably anything looks nicer than the visitor pattern… And pattern matching would be especially nice in this case; before committing to an external library (and learning it, and including an additional dependency in my project), though, I'd like to first see my compiler work. For now, I've added a bunch of dynamic_casts, which is essentially C-style if (ast->type == AST_TYPE_FOO)… but it's still better than having to clutter all my code with visitors. – H2CO3 Oct 11 '15 at 6:59
6

Yes, that's a terrible, terrible plan. Those are completely different things. Violating SRP is just the beginning of your problem. Other problems are things like not being able to offer parse-only support for tooling, for example.

A semantic analyser should perform a translation from an AST to a semantic graph. The AST should not be mutated, nor should it ever hold any semantic information. The AST should never hold any code generation information. The AST should never, ever, do anything but hold syntax.

The issue of parallel class hierarchies just doesn't come up in reality because all of these trees and graphs do completely different things with completely different representations and implementations. If your semantic tree closely parallels your syntax tree, you're probably building either a very basic interpreter or doing it very wrong.

  • Yes, the thing is quite basic in the sense that there is no need per se for a semantic graph, the AST can be codegenned directly (there's no much magic going on in the semantic analysis pass, just basic bottom-up type inference, think C.) I'm not doing any high-level optimizations at the moment either. – H2CO3 Oct 9 '15 at 20:11

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.