Recursive Descent Parsing

The parser turns tokens into an abstract syntax tree (AST). For C, recursive descent works well: each grammar rule = one parser function.

C grammar fragment (simplified):

program  := function_def*
function_def := type IDENT '(' params ')' '{' stmt* '}'
stmt     := expr_stmt | if_stmt | while_stmt | return_stmt | block | decl
expr_stmt := expr ';'
expr     := assignment
assignment := equality ('=' assignment)?
equality := relational (('==' | '!=') relational)*
relational := add (('<' | '>') add)*
add      := mul (('+' | '-') mul)*
mul      := unary (('*' | '/') unary)*
unary    := ('+' | '-' | '!')? primary
primary  := INT | IDENT ('(' args ')')? | '(' expr ')'

Each rule maps to a function:

Operator precedence is encoded by which function calls which: add calls mul (higher precedence), so multiplication binds tighter.

Right-associative ops (=, ?:): recurse on the right side.

Pratt parsers: another approach. Each operator has prefix/infix/postfix handlers + precedence. Easier for languages with lots of operators.

Error recovery: on syntax error, try to skip to a synchronization point (next ; or }) and continue. Avoid cascade errors.