CompilersSyntax AnalysisHard

Recursive Descent Parser

Master the fundamental concepts of syntax analysis through this focused micro-challenge.

~90 minutes Syntax Analysis Ready to learn

Topic Overview

Recursive Descent Is the Default Hand Parser

Most production parsers start as recursive descent: one function per grammar rule, mutual recursion for expressions and statements. Python's parser, many DSL compilers, and Clang's early parsing paths use this style because it maps directly onto the grammar and produces great errors.

One Function Per Rule

Write parse_expression(), parse_statement(), parse_function() that consume tokens and return AST nodes. Each function checks the current token, dispatches on it, and recursively calls sub-parsers. Left recursion in the grammar must be rewritten or handled with precedence climbing.

c
Loading…

peek() inspects without consuming; advance() moves forward
Match expected tokens or report syntax error
Build AST nodes bottom-up as you return from recursion
Expression parsing often delegates to Pratt or precedence layers

Connecting to real compilers

Production compilers embed this step inside a longer pipeline. GCC flows through cpp, cc1, assembly, and ld; Clang uses the driver, Sema, LLVM IR passes, and a target backend. LLVM bitcode, JVM bytecode, and WASM are other familiar IRs at the same layer. The exercise isolates one pass so you can test it alone before chaining it to the next stage.

Why for this exercise

You will implement a recursive descent parser that consumes your lexer's token stream and builds an AST. This exercise requires parsing expressions with correct operator precedence and handling statements, function declarations, and blocks.

Implementation Task

Your Task

Write a recursive-descent parser for expressions, with one C function per precedence level, and print the tree it builds as an S-expression so precedence and associativity are visible.

Input

One expression per line. Blank lines are ignored. Tokens:

numbers (0: 9 runs) and identifiers ([A-Za-z_][A-Za-z0-9_]*)
operators == != < > <= >= + - * / ! and parentheses ( )
spaces and tabs are ignored

Grammar (lowest precedence first)

c
Loading…

All binary operators are left-associative: a - b - c is (- (- a b) c).

Output

One line per input line:

a number or identifier prints as itself;
a binary operation prints as (OP LEFT RIGHT);
unary minus prints as (neg X) and ! as (not X);
parentheses in the source create no node of their own.

If the line is not a valid expression, print only the first error instead:

Situation	Output
a character that starts no token	`error at column C: unexpected character 'X'`
`primary` finds no number, identifier or `(`	`error at column C: expected expression`
a `(` group is not closed	`error at column C: expected ')'`
a complete expression is followed by more tokens	`error at column C: unexpected token 'TEXT'`

C is the 1-based column where the offending token starts; at the end of the line it is the line length + 1. The lexer's error wins if the bad character is reached first (i.e. tokens are read on demand, left to right).

Example

Input:

c
Loading…

Output:

c
Loading…

Requirements

A Parser holding the current token, with advance, check and match helpers.
One function per grammar rule, each returning an AST node; print the tree after parsing succeeds, then free it.

Hidden tests cover every comparison operator, chains of unary operators, deep nesting, and each of the four errors.