Jolly Good Software

Working Through WACC – Pause after part 1

—

by

paulmoore100
in

I am blogging my way through this book:-

I have reached the end of Part I and this blog post is a summary of thoughts about the progress.

Summary

This is a great book. Although I have diverged from some of the design details (more later) I have mainly stuck to its plan.

The test suite is a fantastic resource. The final test run of Part 1 has 571 tests in it.

Error Handling

There is no discussion of how to handle errors, Nora’s reference implementation (nlsandler/nqcc2: Reference implementation for Writing a C Compiler ) just dies with an error message for the first error it hits. Mine does too.

A real compiler must

  • report where the error is
  • recover and continue

The first part requires cooperation with the lexer. The second one is worthy of more discussion. The compiler needs to reset to some state where it can continue. The Crafting Interpreters book talks at length about error handling including error recovery.

The way I do error reporting at the moment is via the excellent anyhow – Rust, using its bail! macro. For example here is the code that detects a duplicate default label in a switch statement

if context.default_statement_seen {
        bail!("Duplicate default statement");
}

This in turn means that the code is written in the current best practice error handling mode.

  • everything returns a Result<T>
  • all calls have a ‘?’ on the end
  • The error is caught at the top of the parser and reported to the user (its here that the source line, line number and column are obtained from the lexer)

As an example here is the complete code of the parsing of a default label

fn do_default(&mut self) -> Result<()> {
   self.next_token()?;

  if let Some(context)=self.switch_context_stack.last_mut(){ 
       if context.default_statement_seen {
           bail!("Duplicate default statement");
       }
       context.default_statement_seen = true;
  } else {
       bail!("Default outside of switch");
  };
  self.do_case_or_default(false)?;
  Ok(())
}

At the moment I do not try to recover, the first error ripples all the way up to the parser entry point, a nice message is issued and compilation stops. I could try to continue after running the lexer to some synchronization point, say the end of the current statement and then resume parsing (remembering that we had a fatal error so exiting once the parse is complete). I have one serious issue waiting for me in the weeds though:-

Looking at the code about you see that there is a switch context stack, when I enter a switch a new context is pushed onto that stack, when exited it is popped off. Thats how, for example, I can reject a default thats outside a switch, if the stack is empty we are not in a switch.

Heres part of the code

fn do_switch(&mut self) -> Result<()> {
  ...
  self.switch_context_stack.push(SwitchContext {
     cases: Vec::new(),
     value,
     default_statement_seen: false,
     before_first_case: true,
     // bootstrap the label chain
      next_drop_thru_label: next_drop_thru_label.clone(),
      next_case_label: next_case_label.clone(),
  });
  // the entire body of the switch statement is handled by this call
   // including the cases and breaks
   self.do_statement()?;

   // at the end of the switch, add the exit label
   // plus any pending labels
   self.instruction(Instruction::Label(label_end.clone()));
   let last_case_label = self
       .switch_context_stack
       .last()
       .unwrap()
       .next_case_label
        .clone();
    if !last_case_label.is_empty() {           self.instruction(Instruction::Label(last_case_label));
   }
   self.switch_context_stack.pop();
   self.break_label_stack.pop();
   Ok(())

The problem is that if the parsing of the body the self.do_statement()?; in the middle, fails then those pops at the end wont be run. This issue occurs with the symbol table too as we enter and leave code blocks. Leaving the code as is means I have corrupted internal state so I cannot simply recover

Some languages have a ‘finally’ or ‘defer’ feature that allows you to say ‘before this function / scope exits always run this code’, but not rust. (This is a fiercely debated topic in c++, see for example Stroustrup: C++ Style and Technique FAQ). There is however scopeguard – Rust which does the same thing. I am going to incorporate that when I do the next round of error cleanup.

Where I Diverged

This is an updated version of my original diagram of how Nora’s design flows. I have added the symbol table in, it is used in all phases of the compilation.

This means that the TACKY in the book is not free standing, it needs the symbol table too. I liked the idea of having TACKY being self contained so I extended the TACKY model to include the type information that was in the symbol table. For example this c code

int a(int a) {
    return a * 2;
}

int main(void) {
    return a(1);
}

generates

Dumping TackyProgram
Function: Int32 a([("a$0", Int32)]) global:true
      Binary Multiply Variable("a$0", Int32) Int32(2) Variable("$temp$0", Int32)
      Return Variable("$temp$0", Int32)
      Return Int32(0)
Function: Int32 main([]) global:true
      FunCall "a" [Int32(1)] Variable("$temp$1", Int32)
      Return Variable("$temp$1", Int32)
      Return Int32(0)

Every object is annotated with its type.

I also do not generate the pre TACKY AST model, ie I make only one logical pass over the code; the parser generates TACKY as it goes. This impacts the code generation, as I mentioned in a previous post

So my flow looks like this

MOIRA is what I christened the intermediate form in the backend (Nora calls it the ‘Assembly AST’), Machine Oriented Instruction RepresentAtion. Still not sure its needed, there is a second pass on it, but I think that could be done as the TACKY code is read. The original C compiler generated assembly directly in a single pass, so its fundamentally doable

Assembler

I started out using MASM. This seemed like the obvious choice as it is installed with MSVC , which is the tool chain I am using. I then hit a roadblock, I could not work out how to call a function that was a reserved word, for example ‘add’. I discussed this at length in a previous post, so I won’t go into detail here. So, I switched to using NASM. This, BTW, has a fantastic resource, a complete list of x64 instructions and what combination of operand they support NASM – The Netwide Assembler

Somebody recently posted a response to my question on StackOverflow assembly – How to call a function in MASM /ML64 that has the same name as a reserved word – Stack Overflow that looks like it might work, so maybe I will circle back to this decision.

Nand2Tetris

The reason I came here in the first place was to create a c compiler for that system. I promised myself when I hit this point (end of part 1) I would make a start on that. I must admit that I have already started on the next chapter and will probably punt till later.

I will probably do a post at some point describing that system and the challenges it represents for c

Comments

Leave a comment