How does the compiler allocate memory without knowing the size at compile time?

This is not a "static memory allocation". Your array k is a Variable Length Array (VLA), which means that memory for this array is allocated at run time. The size will be determined by the run-time value of n.

The language specification does not dictate any specific allocation mechanism, but in a typical implementation your k will usually end up being a simple int * pointer with the actual memory block being allocated on the stack at run time.

For a VLA sizeof operator is evaluated at run time as well, which is why you obtain the correct value from it in your experiment. Just use %zu (not %ld) to print values of type size_t.

The primary purpose of malloc (and other dynamic memory allocation functions) is to override the scope-based lifetime rules, which apply to local objects. I.e. memory allocated with malloc remains allocated "forever", or until you explicitly deallocate it with free. Memory allocated with malloc does not get automatically deallocated at the end of the block.

VLA, as in your example, does not provide this "scope-defeating" functionality. Your array k still obeys regular scope-based lifetime rules: its lifetime ends at the end of the block. For this reason, in general case, VLA cannot possibly replace malloc and other dynamic memory allocation functions.

But in specific cases when you don't need to "defeat scope" and just use malloc to allocate a run-time sized array, VLA might indeed be seen as a replacement for malloc. Just keep in mind, again, that VLAs are typically allocated on the stack and allocating large chunks of memory on the stack to this day remains a rather questionable programming practice.

In C, the means by which a compiler supports VLAs (variable length arrays) is up to the compiler - it doesn't have to use malloc(), and can (and often does) use what is sometimes called "stack" memory - e.g. using system specific functions like alloca() that are not part of standard C. If it does use stack, the maximum size of an array is typically much smaller than is possible using malloc(), because modern operating systems allow programs a much smaller quota of stack memory.

Memory for variable length arrays clearly can't be statically allocated. It can however be allocated on the stack. Generally this involves the use of a "frame pointer" to keep track of the location of the functions stack frame in the face of dynamicly determined changes to the stack pointer.

When I try to compile your program it seems that what actually happens is that the variable length array got optimised out. So I modified your code to force the compiler to actually allocate the array.

#include <stdio.h>
int main(int argc, char const *argv[])
{
    int n;
    scanf("%d",&n);
    int k[n];
    printf("%s %ld",k,sizeof(k));
    return 0;
}

Godbolt compiling for arm using gcc 6.3 (using arm because I can read arm ASM) compiles this to https://godbolt.org/g/5ZnHfa. (comments mine)

main:
        push    {fp, lr}      ; Save fp and lr on the stack
        add     fp, sp, #4    ; Create a "frame pointer" so we know where
                              ; our stack frame is even after applying a 
                              ; dynamic offset to the stack pointer.
        sub     sp, sp, #8    ; allocate 8 bytes on the stack (8 rather
                              ; than 4 due to ABI alignment
                              ; requirements)
        sub     r1, fp, #8    ; load r1 with a pointer to n
        ldr     r0, .L3       ; load pointer to format string for scanf
                              ; into r0
        bl      scanf         ; call scanf (arguments in r0 and r1)
        ldr     r2, [fp, #-8] ; load r2 with value of n
        ldr     r0, .L3+4     ; load pointer to format string for printf
                              ; into r0
        lsl     r2, r2, #2    ; multiply n by 4
        add     r3, r2, #10   ; add 10 to n*4 (not sure why it used 10,
                              ; 7 would seem sufficient)
        bic     r3, r3, #7    ; and clear the low bits so it is a
                              ; multiple of 8 (stack alignment again) 
        sub     sp, sp, r3    ; actually allocate the dynamic array on
                              ; the stack
        mov     r1, sp        ; store a pointer to the dynamic size array
                              ; in r1
        bl      printf        ; call printf (arguments in r0, r1 and r2)
        mov     r0, #0        ; set r0 to 0
        sub     sp, fp, #4    ; use the frame pointer to restore the
                              ; stack pointer
        pop     {fp, lr}      ; restore fp and lr
        bx      lr            ; return to the caller (return value in r0)
.L3:
        .word   .LC0
        .word   .LC1
.LC0:
        .ascii  "%d\000"
.LC1:
        .ascii  "%s %ld\000"

The memory for this construct, which is called "variable length array", VLA, is allocated on the stack, in a similar way to alloca. Exactly how this happens depends on exactly which compiler you're using, but essentially it's a case of calculating the size when it is known, and then subtracting [1] the total size from the stack-pointer.

You do need malloc and friends because this allocation "dies" when you leave the function. [And it's not valid in standard C++]

[1] For typical processors that use a stack that "grows towards zero".