ToolSphere
Back to all articles
student

Recursive Descent Parser in C: Worked Example

2026-11-0312 min read

Try it: free Recursive Descent Parser Generator

Generate a C or Python recursive descent parser from a grammar

Open →

A predictive recursive-descent parser uses a procedure for each grammar variable and chooses an alternative from the next token. It must know which alternative to take without guessing or backtracking. This example uses the recursive-descent parser generator to prepare an expression grammar, generate C, then compile and execute the exact generated source.

The code is a recognizer: it reports whether the input has the grammar's syntax. It does not calculate an arithmetic value, resolve declarations or produce machine code. The generated routines illustrate parsing control flow rather than a complete compiler frontend.

Start with the familiar left-recursive grammar

E -> E + T | T
T -> T * F | F
F -> ( E ) | id

A direct translation of E -> E + T would call parse_E before consuming any token. Repeating that choice would recurse indefinitely. A generator therefore needs either a compatible grammar or an explicit preparation step. For this example, automatic removal of left recursion and factoring are enabled.

The prepared grammar, printed by the library, is:

E -> T E'
E' -> + T E' | ε
T -> F T'
T' -> * F T' | ε
F -> ( E ) | id

The added tail variables represent repetitions of the pending operator-and-operand sequence. This grammar keeps multiplication inside a term and addition between terms. Rewriting changes the parse-tree shape. If you later add AST construction, build the intended left-associated expression explicitly instead of assuming the right-recursive tail has the same tree as the original rule.

Choose alternatives from prediction sets

For a nonempty alternative, the procedure uses its FIRST terminals. When an alternative can produce ε, its selection also depends on the surrounding nonterminal's FOLLOW terminals. That is why an epsilon branch should not simply run whenever another branch fails: an unexpected token can be an error rather than a valid end of a phrase.

The generator checks that the prepared grammar is LL(1), meaning the chosen alternative is unambiguous from one lookahead token in this predictive table. It refuses conflicting grammars with an explanation. Removing immediate recursion alone does not establish LL(1), and factoring the dangling-else grammar does not automatically remove its predictive conflict.

Use the FIRST/FOLLOW calculator to inspect those sets or the left-recursion remover for a separate rewriting trace. The generated routine names are sanitized identifiers, while token matching uses the original terminal spellings.

Complete generated C source

This is the source produced by the library for the prepared grammar, with no handwritten replacement of its parsing procedures:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* Recursive-descent parser for:
 *  E -> T E'
 *  E' -> + T E' | ε
 *  T -> F T'
 *  T' -> * F T' | ε
 *  F -> ( E ) | id
 * Reads one line, prints Accepted or Rejected. */

static const char *TERMINALS[] = { "id", "+", "*", "(", ")" };
static char input[1024];
static size_t pos = 0;
static char token[64];

/* Longest terminal at the current position; end of line is $. */
static void next_token(void) {
    while (input[pos] == ' ' || input[pos] == '\t') pos++;
    if (input[pos] == '\0') { strcpy(token, "$"); return; }
    for (size_t i = 0; i < sizeof TERMINALS / sizeof *TERMINALS; i++) {
        size_t n = strlen(TERMINALS[i]);
        if (strncmp(input + pos, TERMINALS[i], n) == 0) { strcpy(token, TERMINALS[i]); pos += n; return; }
    }
    token[0] = input[pos++];
    token[1] = '\0';
}

static int is(const char *t) { return strcmp(token, t) == 0; }

static void reject(const char *expected) {
    printf("Rejected: expected %s but found %s\n", expected, is("$") ? "end of input" : token);
    exit(1);
}

static void match(const char *t) {
    if (is(t)) next_token();
    else reject(t);
}

static void parse_E(void);
static void parse_E_prime(void);
static void parse_T(void);
static void parse_T_prime(void);
static void parse_F(void);

static void parse_E(void) {
    if (is("(") || is("id")) {
        /* E → T E' */
        parse_T();
        parse_E_prime();
    } else {
        reject("( or id");
    }
}

static void parse_E_prime(void) {
    if (is("+")) {
        /* E' → + T E' */
        match("+");
        parse_T();
        parse_E_prime();
    } else if (is("$") || is(")")) {
        /* E' → ε */
        /* ε: match nothing */
    } else {
        reject("+, ) or end of input");
    }
}

static void parse_T(void) {
    if (is("(") || is("id")) {
        /* T → F T' */
        parse_F();
        parse_T_prime();
    } else {
        reject("( or id");
    }
}

static void parse_T_prime(void) {
    if (is("*")) {
        /* T' → * F T' */
        match("*");
        parse_F();
        parse_T_prime();
    } else if (is("+") || is("$") || is(")")) {
        /* T' → ε */
        /* ε: match nothing */
    } else {
        reject("*, +, ) or end of input");
    }
}

static void parse_F(void) {
    if (is("(")) {
        /* F → ( E ) */
        match("(");
        parse_E();
        match(")");
    } else if (is("id")) {
        /* F → id */
        match("id");
    } else {
        reject("( or id");
    }
}

int main(void) {
    if (!fgets(input, sizeof input, stdin)) input[0] = '\0';
    input[strcspn(input, "\r\n")] = '\0';
    next_token();
    parse_E();
    if (is("$")) printf("Accepted\n");
    else reject("end of input");
    return 0;
}

The tokenizer reads grammar terminals, preferring longer matching spellings and skipping supported whitespace. Here id is a literal terminal token; the code is not a general C lexer that recognizes arbitrary variable names or numeric literals. An unknown character is retained as an unmatched token, allowing the parser to explain what it expected.

Each parse routine tests the current lookahead, then calls another routine for a nonterminal or match for a terminal. match advances only when the expected token is present. A completed start routine must also reach the end of input, so accepting a valid prefix while ignoring trailing tokens is not enough.

Compile the exact generated program

The source above was saved and compiled with the following command in the verification scratch directory:

gcc -std=c11 -Wall -Wextra -o parser parser.c

Compilation succeeded without warnings. Each test below started a fresh process, supplied one line on standard input and recorded the program's actual output and exit status. The filenames in the command are illustrative local names; the source is the same generated C printed above.

Input Actual output Exit status
id + id * id Accepted 0
( id + id ) * id Accepted 0
id + Rejected: expected ( or id but found end of input 1
id id Rejected: expected *, +, ) or end of input but found id 1

An incomplete expression is rejected at the point where an operand is expected. A second id without an operator is also rejected, because the parser does not stop after the first valid expression and ignore the remainder. The rejection message is part of the program's output, not a separate diagnosis invented for this article.

Follow the procedure calls for the accepted example

The generator's teaching trace for id + id * id records the procedure, selected production and terminal matches. Indentation below is call depth:

parse_E(): lookahead id, use E → T E'
  parse_T(): lookahead id, use T → F T'
    parse_F(): lookahead id, use F → id
      match(id)
    parse_T_prime(): lookahead +, use T' → ε
  parse_E_prime(): lookahead +, use E' → + T E'
    match(+)
    parse_T(): lookahead id, use T → F T'
      parse_F(): lookahead id, use F → id
        match(id)
      parse_T_prime(): lookahead *, use T' → * F T'
        match(*)
        parse_F(): lookahead id, use F → id
          match(id)
        parse_T_prime(): lookahead end of input, use T' → ε
    parse_E_prime(): lookahead end of input, use E' → ε

This trace is generated by the same planned grammar as the C procedures. It is a readable simulation of their parsing decisions, not a transcript from a debugger stepping through native machine instructions. The compiled-program runs above independently verify the observable acceptance and rejection results.

Common implementation errors

Do not keep left recursion in a procedure that calls itself before matching anything. Do not use an unconditional epsilon branch for every unexpected token. Do not omit the final end-of-input test, or id id may appear accepted after the first id. Keep token matching separate from the procedure's choice of grammar alternative.

A recognizer is also different from an evaluator. Adding a return value to each routine requires a defined semantic action and associativity policy. The generated code here does not claim either. Its input buffer and supported grammar model suit small coursework exercises, not hostile unbounded files or a production programming-language parser.

Adapt the example safely

Change the grammar in the interactive generator, inspect the rewrite and prediction choices, then regenerate rather than editing a printed branch without updating its sets. Test valid, incomplete and extra-token inputs. If the tool reports a remaining LL(1) conflict, changing the order of if branches hides the conflict instead of solving it.

The compiler lab links this predictive approach with precedence and LR parsing. Use the left-recursion guide when you need to understand which transformation makes the procedures safe to enter.

Looking for other tools?

Explore ToolSphere Homepage →