ToolSphere

Recursive Descent Parser Generator

Computer science

Generate a working recursive descent parser in C or Python from any LL(1) grammar, one function per non-terminal, and trace its calls on a string.

Type a grammar and a string to generate a recursive-descent parser and follow its calls.

Accepted by the generated C parser. Generated code and the call trace follow the grammar.

Grammar (one rule per line)

One rule per line, spaces between symbols: E -> E + T | T. Write ε (or eps) for an empty right side, one that matches nothing. The first rule is the start.

Grammar used

Rewritten first (see the steps in the left recursion calculator):

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

Generated parser

#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;
}

Save as parser.c, compile with gcc parser.c -o parser, then run ./parser and type a string. Each function looks at the next token, picks the one alternative its LL(1) table allows, and calls match() for terminals.

Trace the calls

Accepted

  1. parse_E(): lookahead id, use E → T E'
  2. parse_T(): lookahead id, use T → F T'
  3. parse_F(): lookahead id, use F → id
  4. match(id)
  5. parse_T_prime(): lookahead +, use T' → ε
  6. parse_E_prime(): lookahead +, use E' → + T E'
  7. match(+)
  8. parse_T(): lookahead id, use T → F T'
  9. parse_F(): lookahead id, use F → id
  10. match(id)
  11. parse_T_prime(): lookahead *, use T' → * F T'
  12. match(*)
  13. parse_F(): lookahead id, use F → id
  14. match(id)
  15. parse_T_prime(): lookahead end of input, use T' → ε
  16. parse_E_prime(): lookahead end of input, use E' → ε

On this browser only

Give feedback

Did this tool help?

Tell us what worked, what didn’t, or what you’d like next.

Opens Google Forms in a new tab with this tool’s name filled in. No sign-in or email required. Feedback is optional.

How to use Recursive Descent Parser Generator

  1. 1Type the grammar, one rule per line, or load the expression, statement or declaration example.
  2. 2Leave Remove left recursion and left factor first ticked unless your grammar is already LL(1); the rewritten grammar is shown.
  3. 3Choose C or Python and copy the generated parser.
  4. 4Type a string under Trace the calls to see which function runs, which alternative it picks and every match, indented by call depth.
  5. 5Compile and run the code yourself: it reads one line and prints Accepted or a Rejected message saying what it expected.

About Recursive Descent Parser Generator

What a recursive descent parser is

A recursive descent parser is a top-down parser written as ordinary code. It has one function for each non-terminal of the grammar. A function for A looks at the next input token, the lookahead, and decides which alternative of A applies. It then works through that alternative from left to right: a non-terminal becomes a call to its function, and a terminal becomes a match that checks the token and moves on. The call stack of the program follows the parse tree, which is why compiler courses use it to introduce parsing and why many real compilers still use hand-written ones.

This tool writes that code for you. Type a grammar and you get a complete parser in C or Python, with a lexer, match and reject functions and a main function. It compiles and runs as it is. Every generated parser is tested against the site's LL(1) parser, by compiling the C with gcc and running the Python, on accepted and rejected strings.

Why the grammar must be LL(1)

A function can only choose an alternative from one token if no two alternatives can start with that token. That is exactly the LL(1) condition. Two obstacles are common. Left recursion, as in E → E + T, makes the function for E call itself before reading anything, so it recurses forever. Common prefixes, as in S → b c | b d, make the choice impossible with one token. With the rewrite box ticked, the tool first removes left recursion and then left factors, the same steps as the left recursion and left factoring calculator, and shows the grammar it actually used. If the result is still not LL(1), it says which token causes the conflict and does not generate a parser that would guess.

How each function chooses

The choice comes from the LL(1) parsing table. An alternative A → α is selected by every token in FIRST(α). If α can derive ε, it is also selected by every token in FOLLOW(A), and the end of input counts when FOLLOW(A) contains the end marker. Any other token is a syntax error, and the generated code says what it expected. For the expression grammar the rewrite gives E → T E', E' → + T E' | ε, T → F T', T' → * F T' | ε and F → ( E ) | id. The tool generates this Python function for F:

def parse_F():
    if token == "(":
        # F → ( E )
        match("(")
        parse_E()
        match(")")
    elif token == "id":
        # F → id
        match("id")
    else:
        reject("( or id")

The function for E' takes the + branch on +, and the ε branch on ) or at the end of input. The ε branch matches nothing.

Worked example: tracing id + id

The trace shows the same calls the generated program makes:

Depth Call
0 parse_E(): lookahead id, use E → T E'
1 parse_T(): lookahead id, use T → F T'
2 parse_F(): lookahead id, use F → id, match(id)
2 parse_T_prime(): lookahead +, use T' → ε
1 parse_E_prime(): lookahead +, use E' → + T E', match(+)
2 parse_T(), parse_F(): match(id)
2 parse_T_prime(): end of input, use T' → ε
2 parse_E_prime(): end of input, use E' → ε

The input is used up when parse_E returns, so the string is accepted. For id + the trace stops in parse_T, which expected ( or id but found the end of input. The generated program prints that same message.

Using the generated code

Save the C version as parser.c, compile it with gcc parser.c -o parser and run ./parser. The Python version runs with python3 parser.py. Type one line, such as id + id * id. The lexer reads the longest terminal at each position, so spaces are optional. Function names are parse_ followed by the non-terminal, with a prime written as _prime, so E' becomes parse_E_prime. To build a syntax tree or evaluate expressions, add code inside each branch. That is how syntax-directed translation is usually added to a recursive descent parser.

Common mistakes

  • Leaving left recursion in. A function for E → E + T calls itself first and never returns.
  • Forgetting the ε branch. Without it, a function cannot finish when its non-terminal derives nothing, and valid strings get rejected.
  • Choosing ε on any token. The ε branch belongs only to the FOLLOW tokens. Taking it on any other token hides syntax errors until later.
  • Not checking the end of input. The parser must check that the input is used up after the start function returns. The generated main function does this.

Related tools

Check the sets the code relies on with the FIRST and FOLLOW calculator, and compare with the table-driven LL(1) parser, which makes the same choices with an explicit stack. For bottom-up parsing see the LR parser.

Guides and tutorials

Frequently asked questions

How do you write a recursive descent parser for a grammar?

Write one function per non-terminal. Each function looks at the next token, picks the alternative whose FIRST set (or FOLLOW set, for an ε alternative) contains it, then calls the function of every non-terminal and matches every terminal in that alternative, in order. This tool generates exactly that code in C or Python.

Why can't a recursive descent parser handle left recursion?

For E -> E + T, the function for E would call itself before reading any token, so it recurses forever without making progress. Removing left recursion first, which gives E -> T E' and E' -> + T E' | ε, fixes it. The tool does this when the rewrite box is ticked.

What is the difference between recursive descent and predictive parsing?

A predictive parser is a recursive descent parser that never backtracks, because the grammar is LL(1) and one token decides each choice. The generated code is predictive. A table-driven LL(1) parser makes the same decisions with an explicit stack instead of function calls.

Does the generated C code compile?

Yes. It is plain C11 using only stdio, stdlib and string, and the site's tests compile every example grammar with gcc -Wall -Wextra with no warnings and check its answers on accepted and rejected strings.

How does the parser decide when to use an ε production?

Only when the lookahead is in FOLLOW of the non-terminal, including the end of input if FOLLOW contains the end marker. In the expression grammar, E' -> ε is chosen on ) or at the end of input. Any other token is reported as an error at once.

What happens if my grammar is not LL(1)?

The tool first tries removing left recursion and left factoring. If the result still has a conflict, as with the dangling-else grammar, it names the token and the competing productions instead of generating a parser that would have to guess or backtrack.

Does the parser backtrack?

No. Each function commits to one alternative from the lookahead token, so the parser runs in time linear in the input length. Backtracking recursive descent exists, but it is slow and not what LL(1) exercises ask for.

How do I add semantic actions or build a syntax tree?

Put code in each branch of the generated functions, for example make parse_F return a number for id and let parse_T_prime multiply. This is the usual way syntax-directed translation is attached to a recursive descent parser.

Why are the functions called parse_E_prime?

Non-terminals such as E' are not valid C or Python names, so each function is named parse_ followed by the non-terminal with every prime written as _prime. The prefix also avoids clashes with keywords such as if or while.

Can I use multi-character tokens like id or while?

Yes. The generated lexer matches the longest terminal of the grammar at each position, so id, while and == are single tokens and spaces between them are optional.

Have a suggestion for Recursive Descent Parser Generator?Share your feedback ↗