This is a common simplification in compilers. Even C, until 1999, forced you to declare your variables at the top of the function before any code.

Its not a limitation of the parser, but simply that having variable declarations anywhere makes the compiler more complex. Its harder to calculate stack space / stack pointers when the variables are declared all over the place.

To clarify why the stack usage calculation is hard when local variable declarations are allowed everywhere, consider compiling this example code:

    int a;
    if (...) {
        int b;
        int c;
        if (...) {
            int d;
        } else {
            int e;
            int f;
        }
        int g;
    } else {
        int h;
    }
    int i;

Let's start assigning offsets to the variables, starting at offset 0. The "a" variable gets 0, "b" gets 1, "c" gets 2, "d" gets 3, "e" gets 4, "f" gets 5, "g" gets 6, "h" gets 7, and "i" gets offset 8, so we need to allocate 9 * sizeof(int) bytes on the stack for the local variables.

Wait, there is no complication at all, so what's the problem? Well, the problem is unoptimal stack usage: at any point, only 5 ints at most are alive, so you can alias "b" with "h" and "i", and alias "d" with "e" and "g", and save 4 * sizeof(int) bytes of the stack. But to do this you need to track the nesting levels (so you could reset the current allocated offset back to the one used at the start of the block) -- and if you're writing a one-pass recursive-descent compiler, you get this for (almost) free anyway... huh.

Did I miss something? It seems there is actually no complication at all, just unwillingness to implement such a feature.

You ‘have’ to go back to the start of your function to fill in the correct size of the stack frame (An alternative is to make a stack frame for every variable or basic block. That’s a waste of cycles and code, especially on early machines)

Again, the solution to that shouldn’t stop you, as it is similar to how you handle filling in the branch offsets in forward branches in if/then/else, and that’s something you have to do, anyways (yes, you can stream out your object code without going back and filling in branch offsets but that leads to slow, ugly code)

I think the reason this _was_ done in old languages is that parsing and compiling were black arts when those languages were created. COBOL and FORTRAN didn’t use stack frames, Algol invented per-function stack frames and later loosened that to per-block ones. That’s what K&R C did, too.

I don’t know which language invented the idea that you could lossen that further, but it might have been C++.

> You 'have' to go back to the start of your function to fill in the correct size of the stack frame

  foo:
    push ebp
    mov ebp esp
    sub esp .stacksz
    ; ...
    .stacksz = 0x14
    leave
    ret

> similar to how you handle filling in the branch offsets in forward branches in if/then/else, and that’s something you have to do, anyways

Pretty much this. I'm with Joker_vD on this one; I don't see a problem here.

Thanks, that's a great idea -- not sure why I didn't think of that, as I am using the assembler to figure this out for if/else forward branches already (as the parent comment pointed out). I've added a paragraph to the article mentioning this comment. Thanks!

Another approach I thought of is, instead of printing the output right away, append to a list of strings you'll output later, and patch it up yourself. But if we're using an assembler, we might as well get it to work for us. (The patching technique is commonly used for patching binary machine code.)

Neither do I. That’s why I wrote “the solution to that shouldn’t stop you, as it is similar to how you handle filling in the branch offsets in forward branches in if/then/else”.

The above doesn’t solve the problem, though. It moves it to the assembler.

Now do that with the rest of the compilation in one pass, without an AST.

If you target a simple CPU (no out-of-order execution, no pipelines), and are ignoring performance (as early C compilers did. If you wanted performance, you inserted ‘register’ in the right places (and you knew what the right places where because you wrote the compiler or were setting next to the guy who did), or dropped down to assembly), it’s not that difficult.

The tricky bits are the stack offsets to local variables. If you compile

  int a = foo()
  int b = a + 1;

to

  call foo
  push
  add 1
  push

the addresses of variables relative to the stack pointer change when you create new locals, when locals go out of scope, or when you push function arguments onto the stack. The trick is for the compiler to track the address of locals relative to the top of the stack frame and keep track of the depth of the stack frame. Then, when generating code to access a stack-relative location, combine the two to translate ‘relative to top of stack frame’ to ‘relative to stack pointer’. A bit tedious, but doable.

Now, when you want performance (especially on modern CPUs), and don’t want to use stack space for variables kept in registers, things do get significantly more complicated.

    push ebp
    move ebp, esp
    sub esp, fun_0_stacksize

    ; calculating foo() and saving the temporary
    call foo
    push eax

    ; loading the temporary and...
    pop eax
    ; ...assigning it to "a"
    mov [ebp+fun_0_var_a], eax

    ; calculating "a+1" starts by evaluating "a"...
    mov eax, [ebp+fun_0_var_a]
    ; ...and saving it as a temporary...
    push eax

    ; ..then by evaluating 1
    mov eax, 1
    ; ...and saving it as a temporary
    push eax

    ; then you load two temporaries, add them together...
    pop ebx
    pop eax
    add eax, ebx
    ; ...and save the temporary result
    push eax

    ; then you load the temporary result and...
    pop eax
    ; ...save it as "b"
    mov [ebp+fun_0_var_b], eax

    ; at this point, you know the total number of local variables
    ; the "fun_NNN_" prefix is used because EQU constants cannot be
    ; redefined (obviously, or they wouldn't support forward uses)
    fun_0_stacksize EQU 8
    fun_0_var_a EQU -4
    fun_0_var_b EQU -8

    ; epilogue
    mov esp, ebp
    pop ebp
    retn

Notice how accessing the locals is done via a separate Base Pointer register EBP instead of the Stack Pointer register ESP (in fact, ESP-based addressing mode is encoded really, really ugly on x86), so that pushing&popping of temporaries doesn't mess up the loads/stores of local variables.

Yes, the code quality is appalling but... it works. In fact, I think Nils M. Holm's T3X compiler uses a similar approach as well.

Of course, if you can allow yourself to use some IR, you can actually assign registers to variables and temporaries and do a much better job.

But here its only the var syntax that is not allowed, the newvar:=someexpression() is allowed, having the same effect of declaring a new local variable if I understand correctly? Edit: typo

I think it's just a case of keeping it simple. Basically, it looks like Mugo supports what Mugo consumes (and about two simple additions). Adding local `var` parsing likely would complicate the hand-crafted parser.

Yes, that's correct. I actually initially implemented local "var" parsing, but was never using it in the compiler, so I removed it to trim it down and keep things as simple as reasonably possible.