Working Through WACC – chapter 15, arrays and pointer arithmetic

WACC is this excellent book and I am blogging my way though it

This was by far the hardest chapter so far. This was a surprise to me since I thought I understood arrays and pointer arithmetic, and I always start each chapter out with “do I know the part of C that we are implementing?”, and if I can anser “Yes” it feels like the process should not be to painful.

Was I ever wrong!

Easy Issues First

You may recall that early on I punted the handling of ++ and — because the parser logic back in https://jollygoodsw.wordpress.com/2025/03/14/working-through-wacc-chapter-5-local-variables/ was not clever enough to deal with postfix operators, now we can

So lets catch that punt.

Parsing Postfix operators

The book has this

<postfix-exp> ::= <primary-exp> { "[" <exp> "]" }

but to incorporate other, extra credit, post fix operators like ++ and — it has to be

 <postfix-exp> ::= <primary-exp> {postfix-op}
 <postfix-op> = "++" | "--" | "[" <exp> "]"

I originally tacked the ++ and — operators as coming after the indexer but the other way round is equally valid. ie

arr++[i]
arr[i]++

are both valid.

Fiddly Lookahead

Also we now need a lookahead for parsing

<factor> ::= <const> | <identifier>
   | "(" { <type-spec> }+ [ <abstract-dec> ] ")" <factor>
   | <unop> <factor> | "(" <exp> ")"
   | <identifier> "(" [ <argument-list> ] ")"

The Crazy World of C Declarators

Once more we hit the ‘making it up as you go along’ world of C. K&R freely admit they were doing that and some of their decisions stick out. The syntax for declaring variables is one such odd decision.

I coded up the logical to parse things following the EBNF given in the book, I always ended up with everything inside out. The one that made it stick out was this.

int (*array)[5];

My parser said this Array(Pointer(Identifier("array")), 5)

and

int *array[5];

produced Pointer(Array(Identifier("array"), 5))

Reading the first one, there is a thing in (), so parse that first, its a pointer, then there is [5] this says ‘an array of five of them’. And that’s what the parser output says, an array of pointers. But thats not what it means, the first one is a pointer to an array , the second one is an array of pointers.

So what the heck is going on? Then it hit me

Declarations in C are statements about expressions, not statements about variables!

For simple things it doesnt matter

int x;

says ‘the expression x is an int’.

int *x;

says ‘the expression *x is an int’

So far it seems pedantic, but how about this

int *x, y;

This says ‘the expression *x is a int, also the expression y‘.

So, in effect, each declaration is a puzzle. For example 'int (*array)[5];' asks ‘what type would x have to be so that (*array)[i] is an int?’

This is why the parse produces everything inside out. The answer to the puzzle is that array would have to be an array of pointers, the thing in () would be parsed first, dereferencing the pointer, we then treat that as an array, index into it, and get an integer.

All c programmers are so used to 'int *px;' meaning ‘px is a pointer to an int’ that they don’t really look at it. It really doesn’t make sense as a declaration of the type of x. A saner language, rust, says px: &i32. – ie ‘px is the address of an int’

The net result of this is that you have to parse the declaraion using the EBNF, this produces the inverse declaration; the puzzle. To solve this you have to turn it inside out.

It took me a long long time to find out where Nora’s implementation turns it inside out (I learned how to debug ocaml code along the way). Its the function called process_declarator (listing 15:15), the book does not describe it this way though. Because my front end is radically different – I directly parse to Tacky – I do not pay attention to the snippets that create Nora’s intermediate representation. Ah well. So now I have a function that does the same thing.

Dereferencing Pointer Index Expression

Second thing I got really tangled up in was this. Quote form the book

According to the C standard, the subscript expression [] is equiva-
lent to *( + ). So, to implement a subscript expression, we’ll gen-
erate the TACKY for pointer addition from Listing 15-27 but return a
DereferencedPointer(result) to the caller instead of a PlainOperand(result).

Reminder that a DeferencedPointer is Nora’s trick for managing the result of a ‘*’ operand. Its not clear what to do with that result until it is used because it means radically different things depending on whether its on the left of the right of an assignment. (Discussed at length is last chapter’s post). So I naively did this and got chaos from some tests. Why? compare these 2 array operations.

    int array2d[2][3];
    int *p2d = array2d[2];

    int array1d[5];
    int a15 = array1d[5];

The first one is purely pointer arithmetic, there is no actual dereferencing. It generates the following TACKY

GetAddress Variable("array2d$0", Array(Array(Int32, 3), 2)) 
  Variable("$temp$0", Pointer(Array(Int32, 3)))
AddPtr Variable("$temp$0", Pointer(Array(Int32, 3))) 
  Int64(2) 12 Variable("$temp$1", Pointer(Array(Int32, 3)))
Copy Variable("$temp$1", Pointer(Int32)) Variable("p2d$1", 
  Pointer(Int32))

Note that the deref operation dropped a level of indirection on the pointer; started with Pointer(array(Int32, 3)) , ended with Pointer(Int32)

The second one really needs a deref, here is its TACKY

GetAddress Variable("array1d$2", Array(Int32, 5))
  Variable("$temp$2", Pointer(Int32))
AddPtr Variable("$temp$2", Pointer(Int32)) Int64(5) 4 
  Variable("$temp$3", Pointer(Int32))
Load Variable("$temp$3", Pointer(Int32))
  Variable("$temp$4", Int32)
Copy Variable("$temp$4", Int32) Variable("a15$3", Int32)

The Load instruction is the dereference – ie ‘fetch what this pointer points at’.

This again took a time to figure out. The code that sorts this out is my make_rvalue in exprs.rs https://github.com/pm100/mycc/blob/2869e630faaed670fd47a9446f9b570640a143e7/src/expr.rs#L631

But any way….

Ran 889 tests in 91.052s

OK

woohoo

---

On to Chars and Strings, not going to try to guess how hard this will be!