Compiler tutorial: suggest more stuff

[DoubleDutch]

Any news on more installments to the tutorial? So far it's been great!

[Trond]

Nagging for more helps.

Function calls are here: http://pbtut.blogspot.com/2010/01/15-fu ... calls.html

Features:
- Up to 10 parameters (can be extended by changing a number)
- Any level of nesting calls
- Conforms to stdcall standard
- Demonstration of the code actually working by pasting it into PB and calling a PB procedure.

[DoubleDutch]

Great stuff! Keep it coming...

[X]

Compile to exe would be great

[alokdube]

make an interpreter out of it, that we can simply tag in the webgadget
more like "if tag=pb , send stuff between script and /script to interpreter and print the output here.

[Mok]

*digging out*
OK, quite nice
But I have a question about the 4th chapter (addition). The compiler creates the following code for "1+2+3"

Code: Select all

!MOV  eax, 1
!PUSH eax
!MOV  eax, 2
!POP  ecx
!ADD  eax, ecx
!PUSH eax
!MOV  eax, 3
!POP  ecx
!ADD  eax, ecx

Wouldn't it be faster and more efficient with the following?

Code: Select all

!MOV  eax, 1
!ADD  eax, 2
!ADD  eax, 3

[X]

I think this is discontinued, the tutorials are not completed (missing the compiler part ...), and it looks abandoned (it's been awhile since an update).

[DoubleDutch]

It's a shame, it would have been good to see more tutorials.

[Trond]

I got a bit tired, and it was a mess to manage, that's why I didn't make any more tutorials.

@Mok:

So our generated code for the expression "1+2" just got worse by a huge amount. Previously just two instructions, now it's five!
You just have to get used to this. It is possible to generate better code, but it is harder. For beginners, this will do. Remember, it's probably way faster than a normal interpreter would be.
Try the program with a few expressions and see if it generates valid code. That is the most important of all. If the generated code doesn’t work correctly, it doesn't matter it it's really, really fast.

The reason we do it this way is to allow for operator precedence (1+2*3=7, not 9) and parentheses later, without having to write complex code.

The "compiler part" is not "missing", what you see is the compiler. But the output needs to be run through and assembler to create an executable or linkable object file.

Edit: By the way, a later chapter deals with how to get rid of the unnecessary pushes and pops. http://pbtut.blogspot.com/2009/09/optim ... k-and.html

[Mistrel]

I haven't really read much into your sources but your approach to "3. Expressions: a digit" and "4. Addition" is completely backwards.

The correct procedure is to convert your infix (normal left-right expressions) to postfix using a stack. Then it's almost a 1:1 conversion directly to assembly.

http://www.maths.abdn.ac.uk/~igc/tch/mx ... ode74.html

The compiler has input an expression in normal form from your program. It has decided that it is grammatically correct and has converted it into postfix form. Now it has to understand it -- i.e. work out what it is asking for. The compiler does not actually perform the operations called for by the expression (that is done when you run the program) but it generates a stream of machine instructions that will have the effect of evaluating the expression. To give you a taste of what happens let me invent a totally fictitious compiler and equally fictitious machine language.

The expression (a + b)*(c + d ) would be converted into something like the following

Code: Select all

fetch value of a into register
add value of b to register
put result into temporary store T
fetch value of c into register
add value of d to register
multiply value of T into register

The point is that the actual machine operations are usually rather elementary things (on small computers there would probably be far more instructions used than in this example simply because the instructions are that much more elementary).

Let's get on with the problem. The beauty of postfix expressions is that they are very easy to evaluate. That's why I converted into postfix in the first place. And here is the evaluation algorithm, which once more uses the two `predicates' isvar(x) and isop(x):

Code: Select all

01 algorithm evaluate(s,n)
02 // s is a postfix string of length n
03   for i = 1 to n begin
04     if isvar( s(i) )  then push(value of s(i) )
05     if isop( s(i) ) then begin
06       x = pop
07       y = pop
08       do y s(i) x and push result (note the order)
09     end
10   end
11   x = pop
12   return x
13 end.

The basic action is this: as each variable appears in the expression its value is pushed onto the stack (4). When an operation appears (5) the top two values are taken off the stack (6,7) and this operation is performed on them. The result is pushed back onto the stack (8). This means that, at any stage, the next operator applies to the previous two values on the stack. At the end there should be just one value left in the stack -- the result. Pop this (11) and return it as the answer.

A compiler, as I said, does not actually perform the calculation -- you are not running the program yet. At line 8 the compiler will write the machine code for performing the operation, rather than actually performing it.

Also see:
http://en.wikipedia.org/wiki/Reverse_Polish_notation

Considering the wide range of platforms today I would rather see a concerted effort writing a compiler which parses the source code to C or C++. That way you can leverage the compilers that have already been written for other platforms without having to learn the actual assembly.

[Trond]

I haven't really read much into your sources but your approach to "3. Expressions: a digit" and "4. Addition" is completely backwards.

The correct procedure is to convert your infix (normal left-right expressions) to postfix using a stack.

I can assure you that my approach is both the simplest and that it is correct. There is no rule which says how you have to do this. The only (and really the only) reason people convert into postfix notation is that they don't know how to easily compile infix expressions. But I do know how to easily compile infix expressions, so the conversion to postfix notation would just be a waste of time.

Of course, my approach is not the most efficient, but it is very simple to write, understand and extend once you understand BNF (which you have to understand sooner or later even when using RPN).

[Trond]

The difference between this and our previous infix syntax is that the original (1) and (2) have been compressed into the single production (1) which forces the presence of brackets.

Woa! That is cheating big time. It basically makes the compiler not respect precedence rules, which is the problem we are trying to solve in the first place. They just skip the problem altogether.

[Mistrel]

The reason postfix notation is efficient is because it can be done in a single pass.

[Trond]

The reason postfix notation is efficient is because it can be done in a single pass.

You have been deceived. To compile via postfix you do two passes. The first from infix to postfix, the second from postfix to asm.
I compile directly from infix to asm in just one pass.

Read more of the tutorial and you'll understand it better.