Build compiler Object Oriented

4
votes

I'm currently working on a project for my class. I'm building a compiler with Flex (lex) and Bison (YACC) and C. I have done just a little bit of semantic an syntax analysis but i have been thinking how im going to implement the object oriented part. That is, how can I handle classes, overloading, polymorphism and heritage.

I can't seem to find something useful on google and the dragon book its just too low level. I mean too focused on building a compiler from scratch. So I was hoping that someone could point me to a good book, tutorials,example, something that can help me to clear my doubts.

Thanks in advance for the help, and im sorry if someone thinks this is asking to have my homework done.

1
oopcompiler-constructionyacclex
Syntax is just a [nice] way to interact with the semantics of a language... this question is "far too broad". One "simple" way to do OO is to use a chained model like JavaScript. (OO does not require classes, chaining implicitly provides a form of overloading, and polymorphism can be obtained with duck-typing.) – user166390
@pst: That assumes you're willing to do dynamic typing. And even then you have to implement polymorphism somehow, and objects don't come for free in the first place. – user395760
@delnan Dynamic typing and weak typing are orthogonal. Consider Python and Objective-C. In any case, a [fixed] chained model is still applicable for statically-typed languages. There is no "one OO" approach. – user166390
@pst: Don't make me laugh. I'm well aware (and, like you, quick to point out) that weak typing != dynamic typing. But duck typing almost universally means dynamic typing (structural typing is a slightly different deal). The exception being C++-esque templates, but in that case the static type checking happens after the templates are instanciated, and the duck typing is limited to compiletime computations (i.e. you can't take that approach and try to type "ordinary" code with it). – user395760
@delnan Why did we ever go down this duck-typing path? Was it because I used "JavaScript" as a descriptor? – user166390

1 Answers

4
votes

I agree with the first comment that this question is far too broad to be answered. But I'll try anyway.

There are several aspects to your question:

  1. What are the semantics of the commonly used concepts of object-oriented programming?
  2. How can they be implemented in a compiler?
  3. How are they usually implemented in other compilers?
  4. What are good resources for further studies?

Semantics

Varies widely between languages and there also is quite a bit of confusion/controversity about what OOP actually means (a nice presentation on that topic: http://www.infoq.com/presentations/It-Is-Possible-to-Do-OOP-in-Java which also has some examples of implementing OOP-features). Just pick one model and look up a reference that defines the semantics such as a language specification or a scientific paper on the model.

Javascript probably is the easiest model to implement as it very directly maps to the implementation without much of a necessary surrounding framework in the compiler. A static version of the Java model (compile time class compilation instead of runtime classloading) shouldn't be too hard either. More sophisticated models would be C++ (which allows multiple inheritance) and Smalltalk or Common Lisp/CLOS (with Meta-object-protocols).

Possible Implementations

Again a wide range of choices. As the semantics are fixed and mostly rather straightforward the implementation effort most strongly depends on the performance you want to archive and the existing infrastructure of your compiler. Storing everything in lists and scanning them for the first entry that satisfies the rules probably is the easiest implementation.

Usual Implementation

Most programming languages out of the Java/C#/C++ area do static compile-time name/signature lookups to find the definitions of the things referred to and use a http://en.wikipedia.org/wiki/Virtual_method_table to resolve polymorphic calls. They also use the Vtable pointer for instanceof-checks and for checking down-casts.

Resources

While only 30 pages are directly concerned with objects I still think Lisp in Small Pieces (LiSP) is a great book for learning to work at that level within a compiler. It focusses on implementing language features, trade-offs in implementations and fitting the pieces together. (if (you can get over the the syntax used) (it's great)).