Working through ‘WACC’ – chapter 5, Local Variables

This is a post in a long series about the book .Writing A C Compiler’. The first post that explains the project is here Working through ‘Writing A C Compiler’ – Jolly Interesting Stuff

In this chapter we get variables. This means

• declarations
• parsing ‘=’
• scopes
• name resolution

Guilty Admission

You will see why I am saying this later.

The precedence aware parsing logic works, but it seems like magic to me, it gets even more complex here because we have to deal with left and right associative operators.

I have read and reread the code but still don’t really understand it, its laziness on my part. I get determined to grok it, but end up going “it works, I’ll come back to it”

So its still magic to me

Variable Renaming

In order to deal with variable scoping like this

int x = 4;
if (y == 7){
    int x = 42;
    ....
}

where those two x’s are different variables, Nora uses a renaming scheme. Like this:

int x0 = 4;
if (y1 == 7){
    int x2 = 42;
    ....
}

Then having a table that keeps track of the mapping between these name pairs. (Ignore the fact that we have not got to if or blocks of code delimited by {})

I implemented that scheme but made an error. I implemented the one shown above, x => x0 etc. This is wrong because if you have a variable called x1 as well then you can end up with two things called x10. There is, in fact, a later (after we have supports for code blocks) test that picks that up and I failed it. I missed the fine print where Nora said to actually use names like a.0, b.1 etc. I actually ended up using a$0, b$1 because they stood out more as obviously fake names

An alternate Scoping Mechanism

When I read this discussion about scope management for names I was surprised by it, in other interpreters and compilers I have built for other languages, like the Lox language in Crafting Interpreters (CI),I did not do this. I recalled what they did instead and wondered if that would be a better way, the renaming seemed a little clunky.

The CI mechanism works like this

Each block represents what CI calls an environment, the main content of which is names and their meanings. Each environment has a pointer to its parent environment.

Whenever the program enters a new scope block a new environment is added to the start of the chain, when the scope exits it is deleted.

When a new name is defined, int x = 4; say, it is added to the environment at the start of the chain. When the interpreter or compiler needs to know what a given name means it works down the chain starting at the newest following the links up to the parent until it finds it, or drops off the end when it hits the global environment (actually working up the diagram above).

I thought this is more elegant than the book’s proposed scheme. I also thought that this mechanism knows the maximum amount of local storage space it needs because you can walk the chain after each block exit and see how much space is used, and take the max. That might be useful later.

However, I realized that the TACKY representation would no longer be so simple and self-contained. A line like this

Copy Int(1) Variable("x")

Is ambiguous if there are multiple x’s in scope. The TACKY code would need to include a snapshot of the symbol chain at every point. I realized that the CI mechanism works for:

• Interpreters
• Compilers that generate code directly rather than using an intermediate representation

So renaming it is.

Validate option

This chapter also adds a new cli flag –validate to run the lex, parse and then the name resolution / semantic analysis before the TACKY generation.

I added this but it is a synonym for –parse becuase my parser generates the TACKY directly, it does not go through a separate analysis phase

Extra Credit

First are the compound assignments, +-, -=, *=, etc.

The trick it to treat them like this

x += 1; 
// is really
x = x + 1;

So a combination of binary operator and assignment. I treated these operators as an extension of the = binary operator

If the operator was simply an equals then just generate a TACKY copy of the right-hand expression (1 in the example above)

But if its a compound operator:

• generate a temporary variable
• emit TACKY BinaryOperator <op>, left, right, left
• emit tacky Copy temp, left ..

well I just learned the value of this blog to me, walking through the code to add the above explanation I realized it was wrong. This blog is like my rubber ducky Rubber Duck Debugging – Rubber Duck Debugging – Debugging software with a rubber ducky

Emit

• TACKY BinaryOperator op, left, right, left

And return left

Then on to

Pre and Post Increment/Decrement

Ie the ++ and -- operators.

This seems innocent enough but in fact was my first major blockage. The problem is this table

credit: Operator Precedence and Associativity in C – C Programming Tutorial – OverIQ.com

Notice that

• postfix ++ and — have a higher precedence to prefix
• postfix ++ and — have a higher precedence than the unary operators, which up until now had the highest precedence

I didnt really take this in and did a naive implementation of them, but got caught out by two tests

    int a = 1;
    int b = 2;
    int c = -++(a);
    int d = !(b)--;

and

   int a = 1;
   int b = !a++;

The first one caught me by surprise because I had never seen anything like it before. The problem was that in my parser (b)is not an lvalue it is a temporary. It needs to parsed as

int d = !(b--);

I was parsing the second one as

int b = (!a)++;

Because ! has the highest precedence in the parser code I had, so this also failed because (!a) is not an lvalue.

It should be parsed as

int b = !(a++)

These both come down to postfix ++ and -- have a higher precedence than ! (and all other unary operators). The failure comes because at the chapter 5 progress point we are implementing this EBNF

<exp> ::= <factor> | <exp> <binop> <exp>
<factor> ::= <int> | <identifier> | <unop> <factor> | "(" <exp> ")"

Note that any expression is either a factor or are binary op pair. In turn a factor is either an int, identifier or a unary op followed by another factor or an expression in parentheses. This means that the unary operators are always parsed out first, which is not what we want if we have a postfix operator. Simple fix I thought, quick mod to some precedence tables maybe ….. ummm … stuck .. not so simple

So I reread other resources that might cover this topic, I had read about Pratt parsers in https://craftinginterpreters.com/ and found a more detailed discussion by the same author, Pratt Parsers: Expression Parsing Made Easy – journal.stuffwithstuff.com. Sadly all these examples do not discuss the situation where a unary has a lower precedence that a postfix.

I emailed Nora asking for a hint, in particular “can the grammar engine we have in chapter 5 deal with these operators?” she replied (many thanks to her for always replying to my emails) saying

If you skip ahead to the “Parsing Subscript Expressions” subsection in Chapter 15 (p. 396 if you’re using a physical book) you can see how to refactor the grammar to handle postfix operators.

Harumph, so I decided to postpone the extra credit for ++ and -- till then.

I have them implemented but they fail those two tests. There ought to be a note in the extra credit section indicating that the parser needs a lot more work to deal with these operators. I would have waited to chapter 15 to assign them as extras.

---

On to chapter 6!