Recursive Decent Parsing: How to turn a Grammar into C code
A predictive parser can be built directly from the productions in the grammar. Non-terminal symbols become function calls; terminal symbols are matched directly against tokens according to the token type returned by the Scanner. To simplify coding and avoid having to pass around a pointer to the current token type, the returned token type is kept in a global variable.
The scanner is always called after a match of a terminal token, to keep the global tokentype always pointing to the next token. This is called the look ahead token. The very first look ahead token has to be read by an initial call to scanner() before any of the grammar’s parsing functions are called. This is done first thing in the Parser, or in main() before calling the Parser.
A function in the Parser may discover that a look-ahead token fails to match an expected symbol in the Grammar. If the match is mandatory, this failure is a syntax error; the Parser must issue an error message and either exit or try to recover. However, if the match is optional, the parsing function simply leaves the look-ahead token alone; some other part of the Parser will match it later (or will issue a syntax error message).
Note: We start with just parsing the input. No actions will be taken on anything we match; we simply match it and move on. (This is like having a DFA inside a scanner that doesn’t have any actions in it to save characters.) Thus, no output will be generated by the parsing process unless the parsing encounters an error.