You are writing a three-pass compiler for a simple programming language into a small assembly language.

The programming language has this syntax:
```
    function   ::= '[' arg-list ']' expression

    arg-list   ::= /* nothing */
                 | variable arg-list

    expression ::= term
                 | expression '+' term
                 | expression '-' term

    term       ::= factor
                 | term '*' factor
                 | term '/' factor

    factor     ::= number
                 | variable
                 | '(' expression ')'
```

Variables are strings of alphabetic characters. Numbers are strings of decimal digits representing integers. So, for example, a function which computes a^2 + b^2 might look like:
```
    [ a b ] a*a + b*b
```

A function which computes the average of two numbers might look like:
```
    [ first second ] (first + second) / 2
```

You need write a three-pass compiler. All test cases will be valid programs, so you needn't concentrate on error-handling.

The first pass will be the method `pass1` which takes a string representing a function in the original programming language and will return a (JSON) object that represents that Abstract Syntax Tree. The Abstract Syntax Tree must use the following representations:
```
  // Each node is of type 'AST' and has the following fields:
  // 'string op', 'AST* a', 'AST* b', and 'int n'
  AST ("+", a, b)       // add subtree a to subtree b
  AST ("-", a, b)       // subtract subtree b from subtree a
  AST ("*", a, b)       // multiply subtree a by subtree b
  AST ("/", a, b)       // divide subtree a from subtree b
  AST ("arg", n)        // reference to n-th argument, n integer
  AST ("imm", n)        // immediate value n, n integer
```

Note: arguments are indexed from zero. So, for example, the function

`[ x y ] ( x + y ) / 2` would look like:
```
  new AST ("/", new AST ("+", new AST ("arg", 0), new AST ("arg", 1)), new AST ("imm", 2))
```

The second pass of the compiler will be called `pass2`. This pass will take the output from `pass1` and return a new Abstract Syntax Tree (with the same format) with all constant expressions reduced as much as possible. So, if for example, the function is `[ x ] x + 2*5`, the result of `pass1` would be:
```
new AST ("+", new AST ("arg", 0), new AST ("*", new AST ("imm", 2), new AST ("imm", 5)))
```

This would be passed into `pass2` which would return:
```
new AST ("+", new AST ("arg", 0), new AST ("imm", 10))
```

The third pass of the compiler is `pass3`. The `pass3` method takes in an Abstract Syntax Tree and returns an array of strings. Each string is an assembly directive. You are working on a small processor with two registers (`R0` and `R1`), a stack, and an array of input arguments. The result of a function is expected to be in `R0`. The processor supports the following instructions:
```
    "IM n"     // load the constant value n into R0
    "AR n"     // load the n-th input argument into R0
    "SW"       // swap R0 and R1
    "PU"       // push R0 onto the stack
    "PO"       // pop the top value off of the stack into R0
    "AD"       // add R1 to R0 and put the result in R0
    "SU"       // subtract R1 from R0 and put the result in R0
    "MU"       // multiply R0 by R1 and put the result in R0
    "DI"       // divide R0 by R1 and put the result in R0
```

So, one possible return value from `pass3` given the Abstract Syntax Tree shown above from `pass2` is:
```
    [ "IM 10", "SW", "AR 0", "AD" ]
```

Here is a simulator for the target machine. It takes an array of assembly instructions and an array of arguments and returns the result.
```
#include <vector>
#include <stack>
#include <string>
#include <utility>

using namespace std;

int simulate (const vector <string> &assembly, const vector <int> &argv) {
  int r0 = 0, r1 = 0;
  stack <int> istack;
  for (auto &ins : assembly) {
    string code = ins.substr (0, 2);
         if (code == "IM") { r0 = stoi (ins.substr (3)); }
    else if (code == "AR") { r0 = argv.at (stoi (ins.substr (3))); }
    else if (code == "SW") { swap (r0, r1); }
    else if (code == "PU") { istack.push (r0); }
    else if (code == "PO") { r0 = istack.top (); istack.pop (); }
    else if (code == "AD") { r0 += r1; }
    else if (code == "SU") { r0 -= r1; }
    else if (code == "MU") { r0 *= r1; }
    else if (code == "DI") { r0 /= r1; }
  }
  return r0;
}
```

Boilerplate:
```cpp
#include <vector>
#include <string>
#include <regex>

struct AST;

struct Compiler {

  std::vector <std::string> compile (std::string program) {
    return pass3 (pass2 (pass1 (program)));
  }

  // Turn a program string into a vector of tokens.  Each token
  // is either '[', ']', '(', ')', '+', '-', '*', '/', a variable
  // name or a number (as a string)
  std::vector <std::string> tokenize (std::string program) {
    static std::regex re ("[-+*/()[\\]]|[A-Za-z]+|\\d+");
    std::sregex_token_iterator it (program.begin (), program.end (), re);
    return std::vector <std::string> (it, std::sregex_token_iterator ());
  }

  // Returns an un-optimized AST
  AST *pass1 (std::string program) {
    auto tokens = tokenize (program);
    return 0;
  }

  // Returns an AST with constant expressions reduced
  AST *pass2 (AST *ast);

  // Returns assembly instructions
  std::vector <std::string> pass3 (AST *ast);
};
```