Recursive Descent Parsing for Expression Analysis

This content is based on a presentation from a previous object-oriented programming seminar, revised from the original slides and supplemented with new information. The course has officially provided a tutorial on recursive descent parsing in the first unit training guide, but it is short and lacks code examples. This article can serve as a supplement to the official guide and is intended for student reference.

What is Recursive Descent

In this unit's OO assignment, expressions are derived from formal grammar rules defined by EBNF. Each rule is called a production, and the symbol on the left side of the production is a non-terminal (e.g., expression, term, etc.), while symbols not appearing on the left are terminals (e.g., x, +, 1, etc.).

Recursive descent is a top-down parsing method used in compiler theory. It involves writing analysis subroutines (methods) for each non-terminal, which call each other to handle nested grammatical structures.

With formal grammar rules, we can use recursive descent parsing to write an expression parser, and the structure of the parser aligns closely with the defined grammar rules, making the code architecture clear and easy to extend (when subsequent assignments add or modify grammar rules, only the corresponding parsing methods need to be added, and the affected methods need to have their internal logic modified).

Revisiting Expression Evaluation

In the data structure course during the first year, we have studied and practiced the problem of evaluating expressions multiple times, using the two-stack approach, maintaining an operand stack and an operator stack. This method has certain limitations, especially when the grammar rules become more complex (such as introducing exponents, custom functions, and unary operators), increasing the complexity of the parsing program and reducing readability due to increased conditions. (This method is still feasible for OO assignments, but its maintainability may decrease with iterations in the second and third assignments)

Let us now revisit expression evaluation using recursive descent parsing, using a simpler syntax for introduction.

Consider the following version of expression evaluation:

  • Only integers
  • Support +, -, *, / operations (priority same as mathematical meaning)
  • Allow parentheses and nested parentheses
  • Integers and parentheses can have one sign before them

(Division is the same as C language integer division, ensuring no division by zero occurs during computation)

Problem Solving Steps

  1. Define the grammar
  • Analyze the components and relationships of the expression
  • Provide a formal definition using BNF or EBNF (In this OO assignment, the formal definition is already given by the guide, so this step is not required)
  1. Write parsing functions for each non-terminal in the grammar rules
  • A function parses only one non-terminal (or a production)
  • When encountering a sub-component, call the corresponding parsing function
  • Define the return value of the function
    • This problem requires evaluation, so each function returns a int
    • If building an expression tree, each parsing function returns a pointer to an expression tree node (in Java, this is an object variable)
  • Syntax error (Wrong Format) detection
    • The syntax analysis cennot continue (the current character does not satisfy the grammar rule)
    • The statement should end but hasn't

Grammar Descripsion

Using EBNF to describe the grammar rules for the above expression (the non-terminal definitions are indicated by ->):

Expr    -> Term     | Expr ('+'|'-') Term
Term    -> Factor   | Term ('*'|'/') Factor
Factor  -> ['+'|'-'] ( Number | '(' Expr ')' )
Number  -> Digit { Digit }
Digit   -> '0'|'1'|'2'|'3'|...|'9'

Where

  • {}: repetition, allows 0 or more occurrences
  • []: optional, allows 0 or 1 occurrence
  • (): grouping, used to control precedence of productions
  • |: or, select one from multiple options
  • Characters (strings) enclosed in single quotes are terminals

Different formal descriptions can represent the same language (if the question is not specified), for example:

  • The production for Expr and Term can be rewritten in a loop form instead of left recursion
    • Expr -> Term { ('+'|'-') Term }
  • The Factor and its leading symbol can be split
    • Factor -> Sign UnsignedFactor
    • Sign -> '+' | '-'
    • UnsignedFactor -> Number | '(' Expr ')'
  • An unsigned number Number can also be treated as a single terminal
    • Requires lexical analysis to achieve

Eliminate Left Recursion

After having the formal grammar rules, can we immediately start writing a recursive descent parser? No. In the example above, the productions for Expr and Term contain left recursion. Left recursion means a production like A -> A b. If the grammar contains left recursion, it cannot directly use recursive descent parsing because it would cause infinite recursion (recursive descent parsing is usually greedy, and for the left recursive Expr, the parser cannot determine the right boundary of the Expr on the right side of the production, thus unable to determine when to stop recursion).

To use recursive descent parsing, we need to rewrite the grammar rules: rewrite productions containing left recursion into right recursion or loop forms (using {} notation) to eliminate left recursion.

For example, for the Expr production, there are two rewriting methods:

  • Expr -> Term | Term ('+' | '-') Expr
  • Expr -> Term { ('+' | '-') Term }

Both are correct, but the loop form is recommended. Using the right recursion form would result in a lot of stack operations (function recursive calls) in the recursive descent parser. If the expression is long, it could lead to stack overflow (e.g., x+x+x+x+...+x, where the number of x is as large as possible within the expression length limit).

Here is a small extension: why does the guide use left recursion to describe expression and term?

According to personal understanding, the syntax tree derived from the left recursive grammar rules matches the actual operation order. In mathematical terms, binary operators like +, * are left-associative, and the operators on the left are evaluated first, corresponding to the left recursive form.

Writing the Parser

Here is the C language implementation of the above expression evaluation code:

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

/*
  Expr    -> Term     | Expr ('+'|'-') Term
  Term    -> Factor   | Term ('*'|'/') Factor
  Factor  -> ['+'|'-'] ( Number | '(' Expr ')' )
  Number  -> unsigned number
*/

// These functions call each other, and in C, they need to be declared in advance
// Expression evaluation, each parsing subroutine returns a value
int Expr();
int Term();
int Factor();
int Number();

#define MAX_LEN 100 // Maximum length of the expression
char buffer[MAX_LEN + 5]; // Input buffer
int pos; // Current position index

#define chr (buffer[pos]) // Get the current character
#define nxt (pos++) // Move forward 1 character

#define WF do{puts("WRONG FORMAT!"); exit(1);}while(0)

// Expr -> Term | Expr ('+'|'-') Term
int Expr() {
    int ans = Term();
    while (chr == '+' || chr == '-') {
        if (chr == '+') {
            nxt;
            ans += Term();
        } else {
            nxt;
            ans -= Term();
        }
    }
    return ans;
}

// Term -> Factor | Term ('*'|'/') Factor
int Term() {
    int ans = Factor();
    while (chr == '*' || chr == '/') {
        if (chr == '*') {
            nxt;
            ans *= Factor();
        } else {
            nxt;
            ans /= Factor();
        }
    }
    return ans;
}

// Factor -> ['+'|'-'] ( Number | '(' Expr ')' )
int Factor() {
    int sign = 1; // positive
    // ['+' | '-']
    if (chr == '+') nxt;
    else if (chr == '-') {
        nxt;
        sign = -1; // negative
    }
    // Number | '(' Expr ')'
    // The production has an 'or' relationship => look ahead 1 character to determine whether to parse a number or a parenthesis
    if (chr == '(') {
        nxt;
        int inner = Expr();
        if (chr == ')') nxt; // expect ')' here
        else WF;
        return sign * inner;
    } else if (chr >= '0' && chr <= '9') {
        return sign * Number();
    } else WF; // either '(' or Number
}

int Number() {
    int ans = 0;
    while (chr >= '0' && chr <= '9') {
        ans = (ans << 3) + (ans << 1) + (chr - '0');
        nxt;
    }
    return ans;
}

int main() {
    while (scanf("%s", buffer) != EOF) {
        pos = 0;
        int ans = Expr();
        if (chr != 0) WF; // not reach end
        printf("%d\n", ans);
    }
    return 0;
}

The above code can pass the accoding-303 expression evaluation test.

Implementing recursive descent parsing in Java follows a similar structure to the above C code.

Complexity Analysis

Time complexity: $O(n)$

  • The parsed string is traversed from left to right, with linear time complexity without backtracking
  • The number of branches in the 'or' relationship in the grammar rules affects the constant, with more branches resulting in a larger constant.

Space complexity: $O(n)$

  • Corresponds to the depth of the recursion stack, which is also the height of the syntax tree
  • Converting right recursion to loops can optimize space complexity

OO Expression Assignment

Having understood the concept of recursive descent through the relatively simple expression evaluation, we can now return to the OO expression assignment.

Grammar Rule Preparation

Since the assignment provides the formal description of the expression grammar rules, there is no need for extensive understanding of the expression's syntax. Simply follow the rules.

Before starting recursive descent, we need to check if the grammar rules contain any left-recursive productions. If they do (for example, expression and term), we need to rewrite them into loop forms.

Additionally, we can make some modifications that do not affect the correctness of the grammar according to personal preferences, such as treating the "blank item" as a single symbol (terminal), thereby no longer needing to process blank characters. For blank characters, the parse method does not need to return anything, and the return type can be set to void.

Parser Implementation

If we need to parse a string enput to obtain an expression tree, the recursive descent parser acts as a factory in the factory pattern, with the input being a string and the product being an expression tree object.

Each non-terminal XXXX corresponds to a parseXXXX method, which returns the result obtained by parsing that grammar component.

  • The syntax tree node or calculated value depends on the specific situation.
  • For blank items, simply skip them, and no return value is needed.

For grammar components with "or" relationships, we need to determine the next direction of analysis (i.e., choose one branch from several). To avoid inefficient backtracking, we need to use a "lookahead" approach, reading the next character in advance to determine the next direction (in the above C code, a lookahead is needed when parsing Factor). Since Java's iterator can only move forward using the next method (and cannot stop at the current value like *it in C++), it is not recommended to use Java's iterator when writing a recursive descent parser. The simplest way is to maintain an integer index pointing to the current parsing position.

Here is a Java recursive descent expression tree construction code template:

/* Definition of the expression tree node class */

// Abstract base class for nodes
public abstract class TreeNode {
    // ......
}

// Leaf node (number)
public class NumberNode extends TreeNode {
    // ......
    public NumberNode(int number) { /* ... */ }
}

// Addition node
public class AddNode extends TreeNode {
    // ......
    public AddNode(TreeNode left, TreeNode right) { /* ... */ }
}

// Subtraction SubNode, Multiplication MulNode, Division DivNode definitions omitted

/* Recursive descent parser */
public class ExprBuilder {
    private final String expr; // Expression to parse
    private int pos; // Current position index

    public ExprBuilder(String expr) {
        this.expr = expr;
        this.pos = 0;
    }

    // parseXXXX represents the method for parsing the XXXX grammar component
    // Only Expr is the top-level symbol of the grammar, so this method is public
    // Throwing an exception indicates a format error in the expression to be parsed
    public TreeNode parseExpr() throws Exception {
        // Use expr.charAt(pos) to get the current character
        // .....
    }

    private TreeNode parseTerm() throws Exception { /* ... */ }

    private TreeNode parseFactor() throws Exception { /* ... */ }

    private TreeNode parseNumber() throws Exception { /* ... */ }
}

It can be seen that the parser written using recursive descent is very concise, with a clear structure, good readability, and high extensibility.

Advantages of Recursive Descent Parsing

  1. Correctness

    Each non-terminal parsing function (method) strictly follows the production rules, and just reading the code and performing simple tests ensures the correctness of the parser.

  2. Readability and Extensibility

    During the iterative development of three assignments, for non-terminals (such as expressions and terms) whose rules remain unchanged from the previous assignment, there is no need to modify them; only the parsing methods of non-terminals with changed or added rules need to be modified.

    From now on, say goodbye to the complicated and hard-to-read "nightmare" regular expressions. (If lexical analysis or matching of function names/numbers/variables is needed, only a few very simple regular expressions are required, and the difficulty will not exceed the regular expressions in the Pre assignment.)

  3. Format Checking

    When the next character read during parsing does not meet any direction of the current production, causing the syntax analysis to fail, an exception is thrown indicating WRONG FORMAT. Exceptions thrown by inner methods are passed up level by level to the top level and then thrown outward.

Finally, I wish all students can complete the first unit of OO successfully!

Appendix

Here are two programming problems that use recursive descent parsing for implementation.

CCF-CSP 2019 December 3rd Chemistry Equation

/* CCF CSP 201912-3 Chemistry Equation */

/* 
Recursive descend
BNF: 
<equation> ::= <expr> "=" <expr> // 2H2+O2=2H2O
<expr> ::= <coef> <formula> | <coef> <formula> "+" <expr> // 2H2+O2, 2H2O
<coef> ::= <digits> | ""    // 
<digits> ::= <digit> | <digits> <digit>
<digit> ::= "0" | "1" | ... | "9"
<formula> ::= <term> <coef> | <term> <coef> <formula>   // H2O CO2 Ca(OH)2 Ba3(PO4)2
<term> ::= <element> | "(" <formula> ")" // H, Ca, (OH), (PO4)
<element> ::= <uppercase> | <uppercase> <lowercase> // H, Ca, O, P, C
<uppercase> ::= "A" | "B" | ... | "Z"
<lowercase> ::= "a" | "b" | ... | "z"

11
H2+O2=H2O
2H2+O2=2H2O
H2+Cl2=2NaCl
H2+Cl2=2HCl
CH4+2O2=CO2+2H2O
CaCl2+2AgNO3=Ca(NO3)2+2AgCl
3Ba(OH)2+2H3PO4=6H2O+Ba3(PO4)2
3Ba(OH)2+2H3PO4=Ba3(PO4)2+6H2O
4Zn+10HNO3=4Zn(NO3)2+NH4NO3+3H2O
4Au+8NaCN+2H2O+O2=4Na(Au(CN)2)+4NaOH
Cu+As=Cs+Au
*/

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <map>
#include <cassert>
using namespace std;
typedef long long ll;

#define MAXN 1000
char input[MAXN + 5];
int offset;

#define RST (offset = 0)
#define CHR (input[offset])
#define NXT (offset++)

struct ElementSet {
    map<string, int> content;
    ElementSet() {}
    ElementSet(string element, int coef) {content[element] = coef;}
    void merge(const ElementSet &s) {
        map<string, int>::const_iterator it1 = s.content.begin(), ie1 = s.content.end();
        while (it1 != ie1) {
            if (this->content.count(it1->first)) {
                this->content[it1->first] += it1->second;
            }
            else {
                this->content[it1->first] = it1->second;
            }
            it1++;
        }
    }
    void times(const int coef) {
        map<string, int>::iterator it1 = this->content.begin(), ie1 = this->content.end();
        while (it1 != ie1) {
            this->content[it1->first] *= coef;
            it1++;
        }
    }
    bool equals(const ElementSet &b) {
        map<string, int>::const_iterator it1 = this->content.begin(), ie1 = this->content.end();
        map<string, int>::const_iterator it2 = b.content.begin(), ie2 = b.content.end();
        while (it1 != ie1 && it2 != ie2) {
            if (it1->first != it2->first) return false;
            if (it1->second != it2->second) return false;
            it1++; it2++;
        }
        return (it1 == ie1) && (it2 == ie2);
    }
};

bool Equation();
void Expr(ElementSet &es); 
int Coef();
// Digits
// Digit
void Formula(ElementSet &es);
void Term(ElementSet &es);
string Element();
// uppercase
// lowercase

bool Equation() {
    ElementSet left, right;
    Expr(left);
    assert(CHR == '=');
    NXT;
    Expr(right);
    return left.equals(right);
}

void Expr(ElementSet &es) {
    int coef = Coef();
    ElementSet formula;
    Formula(formula);
    formula.times(coef);
    es.merge(formula);
    while (CHR == '+') {
        NXT;
        formula.content.clear();
        coef = Coef();
        Formula(formula);
        formula.times(coef);
        es.merge(formula);
    }
}

int Coef() {
    if (CHR >= '0' && CHR <= '9') {
        int ret = 0;
        while (CHR >= '0' && CHR <= '9') {
            ret = (ret << 3) + (ret << 1) + (CHR - '0');
            NXT;
        }
        return ret;
    }
    else return 1;
}

void Formula(ElementSet &es) {
    ElementSet term;
    Term(term);
    int coef = Coef();
    term.times(coef);
    es.merge(term);
    while (CHR && CHR != '+' && CHR != ')' && CHR != '=') { // !!!
        term.content.clear();
        Term(term);
        coef = Coef();
        term.times(coef);
        es.merge(term);
    }
}

void Term(ElementSet &es) {
    if (CHR >= 'A' && CHR <= 'Z') {
        string ele = Element();
        es.merge(ElementSet(ele, 1));
    }
    else if (CHR == '(') {
        NXT; // '('
        ElementSet formula;
        Formula(formula);
        NXT; // ')'
        es.merge(formula);
    }
    else assert(0);
}

string Element() {
    assert(CHR >= 'A' && CHR <= 'Z');
    char ele[3] = {CHR, 0, 0};
    NXT;
    if (CHR >= 'a' && CHR <= 'z') {ele[1] = CHR; NXT;}
    return string(ele);
}


int main()
{
    // freopen("test.in", "r", stdin);
    int n; scanf("%d", &n);
    while (n--) {
        scanf("%s", input);
        RST;
        printf("%c\n", Equation() ? 'Y' : 'N');
    }
    return 0;
}

accoding-4395 Searching for the Truth in Expressions

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

/********** Formula ***********
 * <EXPR> ::= <TERM> {"+"|"-" <TERM>}
 * <TERM> ::= <FACTOR> {"*"|"/" <FACTOR>}
 * <FACTOR> ::= (<NAME> [<FUNC> | <METHOD> {<METHOD>}]) | ("(" <EXPR> ")" {<METHOD>})
 * <FUNC> ::= "(" <EXPR> {"," <EXPR>} ")"
 * <METHOD> ::= "." <NAME> <FUNC>
 * <NAME> ::= [IDENTIFIER]
 *******************************/ 

#define WF puts("WRONG FORMAT");

#define MAX_EXPR_LENGTH 125
char buf[MAX_EXPR_LENGTH];
char *p_str = buf;

static int count = 0;
#define SAVE (++count)

typedef struct Val {
    unsigned char type; // 0: variable, 1: temporary result
    union {
        char var;
        int res;
    } val;
} Val;
void disp(const Val *v) {
    if (v->type == 0) {
        putchar(v->val.var);
    } else {
        printf("%d", v->val.res);
    }
}
Val ValVar(char var) {
    Val r;
    r.type = 0;
    r.val.var = var;
    return r;
}
Val ValRes(int res) {
    Val r;
    r.type = 1;
    r.val.res = res;
    return r;
}


Val Expr();
Val Term();
Val Factor();
Val Func(char name, const Val* self);
Val Method(const Val *self);
Val Name();

int main()
{
    gets(buf);
    Expr();
    return 0;
}


Val Expr(){
    if (!(*p_str)) WF;

    Val term = Term();
    Val res = term;
    while ((*p_str) && ((*p_str) == '+' || (*p_str) == '-')) {
        char op = *(p_str++);
        term = Term();
        printf("%c ", op);
        disp(&res); putchar(' ');
        disp(&term);
        res = ValRes(SAVE);
        putchar('\n');
    }

    return res;
}

Val Term(){
    if (!(*p_str)) WF;

    Val factor = Factor();
    Val res = factor;
    while ((*p_str) && ((*p_str) == '*' || (*p_str) == '/')) {
        char op = *(p_str++);
        factor = Factor();
        printf("%c ", op);
        disp(&res); putchar(' ');
        disp(&factor);
        res = ValRes(SAVE);
        putchar('\n');
    }

    return res;
}

Val Factor(){
    if (!(*p_str)) WF;
    Val ret;
    if ((*p_str) == '(') {
        p_str++;
        Val expr = Expr();
        if (!(*p_str) || (*p_str) != ')') WF;
        p_str++; // ')'
        ret = expr;
    } else {
        Val name = Name();
        if (*p_str && (*p_str) == '(') {ret = Func(name.val.var, NULL);}
        else ret = name;
    }

    while ((*p_str) && (*p_str) == '.') {
        ret = Method(&ret);
    }
    return ret;
}

Val Func(char name, const Val* self){
    // self has already calculated
    Val *args = malloc(121 * sizeof(Val)); 
    int argc = 0;
    if (!(*p_str) || (*p_str) != '(') WF;
    p_str++; // '('

    if (self != NULL) {
        args[argc++] = *self;
    }
    Val expr = Expr();
    args[argc++] = expr;
    while (*p_str && (*p_str) == ',') {
        p_str++;
        expr = Expr();
        args[argc++] = expr;
    }
    if (!(*p_str) || (*p_str) != ')') WF;
    p_str++;
    printf("%c", name);
    for (int i = 0; i < argc; i++) {
        putchar(' ');
        disp(&args[i]);
    }
    putchar('\n');
    free(args);
    return ValRes(SAVE);
}

Val Method(const Val *self){
    if (!(*p_str) || (*p_str) != '.') WF;
    p_str++;
    Val name = Name();
    return Func(name.val.var, self);
}
Val Name(){
    if (!(*p_str) || (*p_str) < 'a' || (*p_str) > 'z') WF;
    char name = *(p_str++);
    return ValVar(name);
}

Tags: recursive descent parsing expression evaluation grammar rules syntax analysis

Posted on Fri, 07 Aug 2026 16:32:09 +0000 by Valera

Hot Tags

©2026 Freaks City