Recursive Descent Parsing

Let TOKEN be the type of tokens, and we have a global next point to the next input token. And suppose we have several helper functions that returns true or false.

• fn term(TOKEN tok) tells if the token next is pointing to matches a given token terminal tok, and advances the next pointer.
• fn S_n() tries to match with n-th production
• fn S() tries all productions

For example,

• for production E -> T, the function can be defined as fn E_1() { return T(); };
• for production E -> T+E, it can be fn E_2() { return T() && term(+) && E(); };
• for all productions, we need backtracking (store current next pointer)

  bool E() {
    TOKEN* save = next;
    return (next = save, E_1())
        || (next = save, E_2())
        || (...);
  }

  // And similarly for T()
  bool T() {
    TOKEN* save = next;
    return (next = save, T_1())
        || (next = save, T_2())
        || (...);
  }

To start the parser, we simply initialize next to point to the first token, and invoke E().