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.