Tutorial on creating a compiler

[lucamar]

It's not just- in my opinion- that compiler texts assume that you're a graduate with good comprehension of maths. They appear to go out of their way to be obtuse, and to insist that "if you're not one of us (which you can be by studying this text) then you're not good enough to know about this stuff".

I think that the problem lies in that most texts emphasize the "theory" part, which leads them down an "abstraction" path that lets us, more "simple" folk, mired at almost the very beginning.

A more practical approach, like say Jack Crensahw's in his Let's build a compiler series, resonates better with us because it sounds as if you were just making a "small" tool step by easy-to-understand step, making the "theory" which led to it easier to grok.

[440bx]

Unfortunately there is little reason to believe that the target audience are reasonably knowledgeable programmers.

The level of programming knowledge in the forum participants varies a great deal, no doubt about that.

As an aside, the Meta-2 PDF that I attached was originally published in 1964. When I started using it for teaching in about 1985 I thought that was ancient... and that was 35 years ago. But it's still useful.

I haven't read all of it yet but, had a quick look.  While the concepts have been "polished" and expanded over time, those presented in that documented haven't really changed that much.  Thank you for sharing!.

You may take a look at mselang, the Pascal compiler of LLVM.

https://github.com/mse-org/mselang

I'll have a look at it.  Thank you for pointing it out.

If possible, I'd like to contribute.

Definitely possible and most definitely welcome!.

Wirth <snip> favoured recursive /ascent/ (Irons et al.).

I have not used recursive ascent to any significant extent. I'll stick to recursive descent because it is very simple, very easy to explain and visualize and, I happen to know it quite well, as a result, I might be able to provide a clear and simple explanation. A very desirable characteristic in a tutorial.

FWIW, I'd also like to see this tutorial made. It'd would be invaluable if it were made easy to understand for programmers with little formal training, whatever the level of experience needed.

I firmly believe that if someone _really_ understands something, they can explain it  in terms that just about anyone can understand.

One of my favorite things to ask mathematicians is "why does minus times minus equal plus?"... the explanation is _trivial_ if you understand it.   If you want to _understand_ why, watch the videos found at http://www.dimensions-math.org/Dim_tour_E.htm

If memory serves, I believe it was in chapter 5 where they made it obvious.  You'll be amazed at how much math you can learn when the person who explains it actually understands what he is talking about.   If such explanations pique your interest, look for James Tanton on youtube.  He is great.

Also very interesting are the book series, "proof without words" from Roger Nelson and some from James Tanton.  Warning: the Nelsen books are often quite overpriced.  Tanton's stuff is excellent and usually very affordable (a lot of it free on youtube.)

The saddest part is, while schools teach all kinds of stuff, they don't teach their students _how to think_.  Paul Zeitz has an excellent class, description and availability at https://www.thegreatcourses.com/courses/art-and-craft-of-mathematical-problem-solving.html

HTH.

I've tried to understand quite some books on compiler design and building and while I did learn quite a lot in the end I failed mainly because most (all?) of them seem to assume you're an university student/graduate of some kind and use difficult-to-parse terminology and lots of difficult-to-follow maths.

I can relate.  Very often the language, in this case Math, used to "explain" a problem is more difficult to understand than how the solution to the problem is derived.  The minus times minus equal plus is a good example of that.

It's not just- in my opinion- that compiler texts assume that you're a graduate with good comprehension of maths. They appear to go out of their way to be obtuse, and to insist that "if you're not one of us (which you can be by studying this text) then you're not good enough to know about this stuff".

Playing devil's advocate, while I feel the same way, one of the principal reasons for the "obtuse" explanations comes from wanting to be extremely accurate and precise, i.e, leave no room for ambiguity (which is desirable, if not downright required.)  That's often not easy to accomplish and, too often collides with simplicity.

I'm not so confident that FORTRAN and COBOL as understood in the 1950s are quite so tractable, and the necessity of considering those might have complicated the field quite a lot.

The first FORTRAN compiler was a mess and, that is what triggered the thought: "there's got to be a better way of doing this", leading to the definitions of grammars, their characteristics, expressive abilities, etc.

I think that the problem lies in that most texts emphasize the "theory" part,

True.  Again, playing devil's advocate, they focus on explaining the power of a particular concept (in this case grammars) not how to use them.  It is (unfortunately) presumed that once the reader understands the power of a parsing technique and its limitations, that the reader will be able to use that knowledge to apply it correctly, effectively and when appropriate. 

Most people learn best by example and contrast.  Theory books are usually lacking in those areas.

[kupferstecher]

What is your goal actually?
 Encouraging people to write their own compiler? Why?
 Encouraging people to participate in the FPC development?

I'd vote for the latter. But than a rough description how the fpc compiler works (and in which unit to find what part of the compiler) would be much better. I don't know if something like that already exists? I'd be interested.

I know there are examples out there but, so far, what I've found are either "toy" compilers, that is, languages that lack too many features to be used in the creation of "real" programs or, as in the case of FPC, a full compiler but, not exactly written in a way to teach someone how to write a compiler.

A compiler designed to be easy to understand only could be an abstraction of a real compiler, and that naturally results in a "toy" compiler. As you said, there already is literature about compiler development, so you better spend your efforts in a fpc specific description.
(Only my opinion)

[440bx]

Encouraging people to write their own compiler? Why?

No.  One goal is providing people the knowledge to write their own compiler if they so desire.  It should also be noted that, many algorithms used in implementing a compiler can be used to implement tasks that have nothing to do with compilers. Scanning and parsing probably being the most common. 

Encouraging people to participate in the FPC development?

No.  Even if it may not be obvious, just by their presence helping other forum members, people are contributing (though indirectly) to FPC development (there would be no development if there weren't people interested in FPC.)

What is your goal actually?

There isn't a single goal.  One goal, a personal one, is having a compiler I really like and, has all the features I want in a compiler (self hosting, as capable as C - that does NOT mean it would resemble C - and as capable as standard Pascal, syntactically simple, easy to learn - less than a day for an experienced Pascal programmer - lightning fast compilation yet produce fast and _extremely_ small executables that compare well to hand written assembly. 

I figured that IF (note the big IF), I decided to do it then, it could also serve as a tutorial on compiler writing and, force a specific level of simplicity (simplicity is _very_ desirable.) A benefit of not doing it all on my own is that, I may benefit from getting some help in some areas, which would definitely make my life easier.  Also, having a large number of eyeballs who _understand_ what is being done significantly lowers the probability that there may be subtle errors in the compiler.

So,  all the above, among others are "my goal".

But than a rough description how the fpc compiler works (and in which unit to find what part of the compiler) would be much better. I don't know if something like that already exists? I'd be interested.

FPC works like any compiler but, because of its size, which is considerable, it is _not_ a _succinct_ and practical way of learning how to write a compiler.  IOW, it's a forest with a lot of trees and inspecting every tree is cumbersome and impractical.

A compiler designed to be easy to understand only could be an abstraction of a real compiler, and that naturally results in a "toy" compiler.

Not the case at all.  My definition of a good program is a program that is _easy to understand_ and, a compiler is just another program.  If anything, Brinch Hansen proved that in his book "on Pascal compilers".  The main reason his implementation of Pascal could be considered a "toy" language is because he compiles for a virtual CPU, which admittedly is simpler than compiling for a real one but, the concepts are the same though the details certainly aren't.

As you said, there already is literature about compiler development, so you better spend your efforts in a fpc specific description.
(Only my opinion)

I disagree. This would be a tutorial on how to write a compiler not on how FPC is implemented.  That said, anyone who knows how to write a compiler will have a much easier time understanding FPC's implementation than someone who does not.

[dtoffe]

I am not really fond of Lex and Yacc, particularly for a tutorial.  lex and yacc have their place but,

It was just an example.

I strongly believe in what Einstein stated "Everything should be made as simple as possible, but no simpler".

You are probably aware that this was the principle after which Wirth got inspiration to design the Oberon language.....

Cheers,

Daniel

[Edson]

Hi.

I've written several articles (in spanish) about "Create your compiler from scratch". It uses Lazarus and MASM32 to create a very basic compiler, just for learning purposes. Fist part is here: http://blog.pucp.edu.pe/blog/tito/2019/01/05/crea-tu-propio-compilador-casero-parte-1/

[440bx]

It was just an example.

I understand.  The reason I mentioned Lex and Yacc is because I wanted to make it clear that there would be no dependence on compiler construction tools (except initially, but only for prototyping and testing the grammar.)

You are probably aware that this was the principle after which Wirth got inspiration to design the Oberon language.....

I didn't remember that until you mentioned it now.

I've written several articles (in spanish) about "Create your compiler from scratch". It uses Lazarus and MASM32 to create a very basic compiler, just for learning purposes. First part is here: http://blog.pucp.edu.pe/blog/tito/2019/01/05/crea-tu-propio-compilador-casero-parte-1/

I've read them.  Nice work!.  What I have in mind is very much along the lines of what you've done, just taken farther.

[af0815]

Hi.

I've written several articles (in spanish) about "Create your compiler from scratch". It uses Lazarus and MASM32 to create a very basic compiler, just for learning purposes. Fist part is here: http://blog.pucp.edu.pe/blog/tito/2019/01/05/crea-tu-propio-compilador-casero-parte-1/

It is very very good written :-) Thanks for the article. I read it with the google translation (i am not able to read spanish) and is complete understandable.

I a waiting hard for the next article "system function" and so on.

[julkas]

Hi.

I've written several articles (in spanish) about "Create your compiler from scratch". It uses Lazarus and MASM32 to create a very basic compiler, just for learning purposes. Fist part is here: http://blog.pucp.edu.pe/blog/tito/2019/01/05/crea-tu-propio-compilador-casero-parte-1/

Good done. Thanks.

[MarkMLl]

As an aside, the Meta-2 PDF that I attached was originally published in 1964. When I started using it for teaching in about 1985 I thought that was ancient... and that was 35 years ago. But it's still useful.

I haven't read all of it yet but, had a quick look.  While the concepts have been "polished" and expanded over time, those presented in that documented haven't really changed that much.  Thank you for sharing!.

I've long been reluctant to post that anywhere, on account of having formally got permission to prepare a copy for teaching. However since there's at least two scanned copies floating around- linked to from the Wp article- I feel that I can probably get away with it by now, and I'm fairly confident in the accuracy of my typesetting. I've got software to go with it if anybody's interested, it often gains a few more experimental facilities for Xmas (this year, if I can spare the time, it will be Smalltalk-style keyword parsing).

Alan Kay, the author of Smalltalk and a very talented worker, had this to say: "The paper itself is a wonderful gem which includes a number of excellent examples, including the bootstrapping of Meta II in itself (all this was done on an 8K (six bit bytes) 1401 ! ) "

On a similar vein, I also have a good two-part article on PROLOG and an implementation in Pascal. It was written for something like TP3 and is very tight indeed, I've often wondered whether I could do anything useful with it (there's precedent: some of the network setup stuff in Windows was for a long time written in PROLOG). Timothy Budd in his Leda book has some thoughts on multi-paradigm languages, but apart from the desirability of a parser being able to handle stuff which isn't really ALGOL-derived I think this is outside a tutorial's scope.

Wirth <snip> favoured recursive /ascent/ (Irons et al.).

I have not used recursive ascent to any significant extent. I'll stick to recursive descent because it is very simple, very easy to explain and visualize and, I happen to know it quite well, as a result, I might be able to provide a clear and simple explanation. A very desirable characteristic in a tutorial.

Again, I'd cite Huub de Beer's historical info linked to from https://wiki.freepascal.org/Make_your_own_compiler,_interpreter,_parser,_or_expression_analyzer#Ancient_history I've no longer got my Wirth books but my recollection is that he started off with ascent but in later versions presented descent as an alternative. Waychoff describes inventing recursive descent as a natural derivative of ALGOL syntax diagrams but later yields precedence to Grau. Wirth's code as found in his Euler compiler is... well, basically one hell of a mess filled with jump tables written in Burroughs ALGOL (which had a language extension for that); if he was still using that sort of technique when he (I suspect hurriedly) constructed Pascal I can sympathise with his not wanting to fix the dangling else problem.

MarkMLl

[440bx]

I've got software to go with it if anybody's interested,

Definitely interested.

Alan Kay, the author of Smalltalk and a very talented worker, had this to say: "The paper itself is a wonderful gem which includes a number of excellent examples, including the bootstrapping of Meta II in itself (all this was done on an 8K (six bit bytes) 1401 ! ) "

Considering the source, that is definitely high praise.

On a similar vein, I also have a good two-part article on PROLOG and an implementation in Pascal.

Prolog... that brings back some memories.  I just played with it when Turbo Prolog came out.  It took some effort to "think in Prolog" but, it was worth it. That said, it's been so long, it would probably take me a few days of retraining my brain to think in Prolog again, not to mention re-learning it.


On a different note, judging by the posts in this thread, I estimate a total of 10 participants interested in a compiler writing tutorial so far.  I have to admit, I was hoping for more but, I'm still open to it.

[marcov]

On a similar vein, I also have a good two-part article on PROLOG and an implementation in Pascal.

Here you have two that compile with FPC:

https://stackoverflow.com/questions/29908207/how-to-compile-vtprolog-from-source-code

https://stackoverflow.com/questions/29907432/how-to-compile-picoprolog-from-source-code

[MarkMLl]

I've got software to go with it if anybody's interested,

Definitely interested.

Zipfile too large for forum, but temporarily at http://www.kdginstruments.co.uk/public/meta2.zip. This should compile without significant issues, use meta2 --help to get command line, it tries to "do the right thing". Be warned that some of this is seriously old code: it's based on an initial implementation in about '86 with organic improvements since then.

There's some highly-tentative attempts to wrap it in a GUI which didn't really get anywhere, when considering that I was influenced by Visual Parse++ (I no longer have a copy but description available via https://mafiadoc.com/parsing-with-sandstones-visual-parse_5cc7544b097c4722768b4635.html but not recursive descent). I've also got examples which I've not attached, but having been built up gradually from rules very similar to what's in Schorre's paper they're best supplied individually with discussion.

MarkMLl

[MarkMLl]

https://stackoverflow.com/questions/29908207/how-to-compile-vtprolog-from-source-code

That's the one, although I can't remember if I seriously tackled it with FPC (it was discussed on the ML, and there's an embedded garbage collector which was considered problematic).

PDFs temporarily at https://www.kdginstruments.co.uk/public/vt_prolog1.pdf https://www.kdginstruments.co.uk/public/vt_prolog2.pdf in case anybody wants them, they were done for the original authors but were never republished. Still a fairly good read.

MarkMLl

[440bx]

Zipfile too large for forum, but temporarily at http://www.kdginstruments.co.uk/public/meta2.zip. This should compile without significant issues, use meta2 --help to get command line, it tries to "do the right thing". Be warned that some of this is seriously old code: it's based on an initial implementation in about '86 with organic improvements since then.

Thank you, much appreciated.