A simple recursive descent parser

Andrea Griffini — Mon, 09 Oct 2023 07:09:22 +0000

I am going to show you the code for a very simple recursive descent parser that will be able to handle the four operations (+, -, * and /), parenthesis, numbers and variables.

I will use Javascript, but without any of the higher level stuff (e.g. regular expressions or eval), so the code could indeed be implemented almost identical in many other languages like C++, Python, Java or Go.

Function signature

The function will accept a string and will return either an error or a function: this resulting function will evaluate the result of the expression given a dictionary with current values for the variables.

An example use will be:

// parse a string into an expression
let ee = parse("x*x + y*y");

// Compute the expression value
console.log(ee({x: 12, y: 3}));

The output will be in this case 12*12 + 3*3 = 144 + 9 = 153

Character reading

First of all I’ll need a variable to keep current position in the input string s; I will use i.

I am also creating an utility function to call in case of an error, throwing an exception with the error message and the position in which the error happened during the parsing.

function parse(s) {
    let i = 0,
        err = (msg) => {
            let e = Error("Error: " + msg);
            e.source = s; e.pos = i;
            throw e;
        };

Whitespace skipping

The parser will ignore whitespace in most positions, so a utility function that will skip over all whitespace (if there is any) will be needed in a few places:

let skipsp = () => {
        while (" \r\t\n".indexOf(s[i]) >= 0) i++;
    };

Numeric and alphabetic characters

Another few utilities to keep the code cleaner are about digits and alphabetic characters needed for numbers and identifiers:

let num = (c) => c >= "0" && c <= "9",
    alpha = (c) => ((c >= "a" && c <= "z") ||
                    (c >= "A" && c <= "Z") ||
                    c === "_"),
    alphanum = (c) => alpha(c) || num(c);

The recursive parser

Now that all needed utility functions have been defined we can move to the main part of the parser. Parsing is a naturally recursive problem once you allow parenthesis… more specifically there are “level-0” expressions that are just numbers or variables, “level-1” that are multiplications or divisions and “level-2” that are additions and subtractions. Recursion is present because at “level-0” you can also add a parenthesized expression, like in x + y*(4 + z).

Instead of making different functions for each level I will write just a single function accepting a “level” parameter, being 0 for numbers, 1 for mu/div, 2 for add/sub.

Indeed it’s even simpler if all the binary operators are placed in a table, with the priority level and the math function to compute the result, this way adding new operators won’t need more code:

let binops = {
        "*": { level: 1, f: (x, y) => x * y},
        "/": { level: 1, f: (x, y) => x / y},
        "+": { level: 2, f: (x, y) => x + y},
        "-": { level: 2, f: (x, y) => x - y},
    };

The main structure of the parser is:

if (level === 0) {
    skipsp(); // skip over spaces
    // check for numbers, variables,
    // unary minus or parenthesized sub-expressions
} else {
    let x = parse(level-1);
    while (/*... there is a proper level operand ...*/) {
        let y = parse(level - 1);
        // combine x and y in (x op y)
        // and place the combination in x
    }
    return x;
}

Checking for numbers

Here I will just store where the number starts and keep skipping over characters until the number ends; to get the numeric value I’ll just Javascript unary + operator on the substring. In C++ for example I could use atof to compute the numeric value.

if (num(s[i])) {
    let i0 = i; // mark where the number starts
    while (num(s[i])) i++; // skip over all digits
    if (s[i] === ".") { // decimal point?
        i++; // skip over it
        while (num(s[i])) i++; // skip over all digits
    }
    if (s[i] === "e" || s[i] === "E") { // exponent?
        i++; // skip over E char
        // skip over optional sign
        if (s[i] === "+" || s[i] === "-") i++;
        if (!num(s[i])) err("Exponent digits expected");
        while (num(s[i])) i++; // skip over all digits
    }
    // The number is over; get the numeric value
    let value = +s.slice(i0, i);
    // Return the resulting function
    return (vars) => value; // vars ignored in this case!
}

Checking for variables

Here I will collect the variable name and return a lookup function

if (alpha(s[i])) {
    let i0 = i; // mark where the name starts
    // skip over all alphanumeric
    while (alphanum(s[i])) i++;
    let varname = s.slice(i0, i);
    // value looked up in passed vars object
    return (vars) => vars[varname];
}

Unary minus

The unary minus is simple; we just skip and wrap the sub-expr result in a sign-changed function

if (s[i] === "-") {
    i++; // skip over the minus sign
    // Note: we parse at level 0!
    // For example "-x+y" means "(-x)+y" not "-(x+y)"
    let v = parse(0);
    return (vars) => -v(vars);
}

Parenthesized sub-expression

if (s[i] === "(") {
    i++; // skip over the open parenthesis
    // Note: we parse at level 2 here
    let v = parse(2);
    skipsp();
    if (s[i] !== ")") err("')' expected");
    i++; // skip over closed parenthesis
    return v;
}

That’s all Folks! (for level 0)

In case we’re at level 0 and none of the previous cases was found then we’ve an error!
This can happen for example parsing "x + 2*" as after the * an expression is expected but none is present and the string just ends. Another possibility for this error to be found is for example "1 + 2*/7" because after the * there is an operator instead of an expression.

err("Expression expected");

Parsing intermediate levels

For the intermediate levels (1/2) of the parser the code is

let x = parse(level - 1);
for(;;) { // endless loop - we'll quit with `break`
    skipsp();
    let op = binops[s[i]];
    // check if it's an operator and if the level is ok
    if (op === undefined || op.level !== level) break;
    i++; // skip over the operator
    let a = x, // left hand
        b = parse(level - 1), // right hand
        f = op.f; // result computation function
    // Combine the two sub-expressions in the result
    x = (vars) => f(a(vars), b(vars));
}
return x;

Main function

The recursive “core” of the parser is complete, we just need to call it and check that no junk is present at end of the expression:

let r = parse(2);
skipsp();
if (i < s.length) err("Extra characters at end of expression");
return r;

Full code

That’s all that is needed; here is the full code for easier copy-n-paste if you want to hack on it:

function parse(s) {
    let i = 0,
        err = (msg) => {
            let e = Error("Error: " + msg);
            e.source = s; e.pos = i;
            throw e;
        },
        skipsp = () => { while (" \r\t\n".indexOf(s[i]) >= 0) i++; },
        num = (c) => c >= "0" && c <= "9",
        alpha = (c) => (c >= "a" && c <= "z") || (c >= "A" && c <= "Z") || c === "_",
        alphanum = (c) => alpha(c) || num(c),
        binops = {
            "*": { level: 1, f: (x, y) => x * y},
            "/": { level: 1, f: (x, y) => x / y},
            "+": { level: 2, f: (x, y) => x + y},
            "-": { level: 2, f: (x, y) => x - y},
        },
        parse = (level) => {
            if (level === 0) {
                skipsp(); // skip over spaces
                if (num(s[i])) {
                    let i0 = i; // mark where the number starts
                    while (num(s[i])) i++; // skip over all digits
                    if (s[i] === ".") { // decimal point?
                        i++; // skip over it
                        while (num(s[i])) i++; // skip over all digits
                    }
                    if (s[i] === "e" || s[i] === "E") { // exponent?
                        i++; // skip over E char
                        if (s[i] === "+" || s[i] === "-") i++; // skip over optional sign
                        if (!num(s[i])) err("Exponent digits expected");
                        while (num(s[i])) i++; // skip over all digits
                    }
                    // The number is over; get the numeric value of this part of the input
                    let value = +s.slice(i0, i);
                    // Return the result: a function accepting variables and returning expr value
                    return (vars) => value; // vars ignored in this case
                }
                if (alpha(s[i])) {
                    let i0 = i; // mark where the name starts
                    while (alphanum(s[i])) i++; // skip over all alphanumeric
                    let varname = s.slice(i0, i);
                    return (vars) => vars[varname]; // value looked up in passed vars object
                }
                if (s[i] === "-") {
                    i++; // skip over the minus sign
                    let v = parse(0); // Note: we parse at level 0: -x+y means (-x)+y
                    return (vars) => -v(vars);
                }
                if (s[i] === "(") {
                    i++; // skip over the open parenthesis
                    let v = parse(2); // Note: we parse at level 2 here
                    skipsp();
                    if (s[i] !== ")") err("')' expected");
                    i++; // skip over closed parenthesis
                    return v;
                }
                err("Expression expected");
            } else {
                let x = parse(level - 1);
                for(;;) { // endless loop - we'll quit with a break statement
                    skipsp();
                    let op = binops[s[i]];
                    // check if it's an operator and if the level is the correct one
                    if (op === undefined || op.level !== level) break;
                    // There is an operator and the precedence level is correct
                    i++; // skip over the operator
                    let a = x, // left hand
                        b = parse(level - 1), // right hand
                        f = op.f; // result computation function
                    // Combine the two sub-expressions in the result
                    x = (vars) => f(a(vars), b(vars));
                }
                return x;
            }
        };

    let r = parse(2);
    skipsp();
    if (i < s.length) err("Extra characters at end of expression");
    return r;
}

let ee = parse("x*x + y*y");
console.log(ee({x: 12, y: 3}));

Some more serious test

Ok... 153 tests fine, but the code is far from trivial, so probably more testing is needed. In the following testing code I wrote an expression, the vars to be passed and the expected result, including some error cases (in which I check the expected error position).

The result has been computed by hand, and not using the function result itself (that wouldn't have been a serious functional test, at most a non-regression test) and indeed helped me finding an error... an error in my manual computation of the expected result! :-D

// Testing
let test = (src, vars, res) => {
    let v = undefined;
    try {
        let expr = parse(src);
        return res === expr(vars);
    } catch(err) {
        return typeof res === "string" && res.indexOf("!") === err.pos;
    }
}

[
    {src: "1", vars:{}, res: 1},
    {src: "2+3", vars:{}, res: 5},
    {src: "2-3", vars:{}, res: -1},
    {src: "2*3", vars:{}, res: 6},
    {src: "5/2", vars:{}, res: 2.5},
    {src: "2 +3", vars:{}, res: 5},
    {src: "2- 3", vars:{}, res: -1},
    {src: " 2 * 3", vars:{}, res: 6},
    {src: "5/2 ", vars:{}, res: 2.5},
    {src: "1+2*3", vars:{}, res: 7},
    {src: "1+5/2", vars:{}, res: 3.5},
    {src: "7-3-1", vars:{}, res: 3},
    {src: "8/2/2", vars:{}, res: 2},
    {src: "8/-2/2", vars:{}, res: -2},
    {src: "-8/-2/2", vars:{}, res: 2},
    {src: "--------1", vars:{}, res: 1},
    {src: "1+2*(3+4)", vars:{}, res: 15},
    {src: "1+2*(3+4)", vars:{}, res: 15},
    {src: "x", vars:{x:2}, res: 2},
    {src: "x+1", vars:{x:2}, res: 3},
    {src: "x*x", vars:{x:2}, res: 4},
    {src: "x * (x+1)", vars:{x:2}, res: 6},
    {src: "x * x + 1", vars:{x:2}, res: 5},
    {src: "(x-1) * (x+1)", vars:{x:2}, res: 3},
    {src: "(x-1) * (x+1)", vars:{x:3}, res: 8},
    {src: "(x-1) * (x2+1)", vars:{x:3, x2:9}, res: 20},
    {src: "(x-1) * (x 2+1)", vars:{x:3, x2:9}, res: "(x-1) * (x !"},
    {src: "(x-1) * ", vars:{x:3, x2:9}, res: "(x-1) * !"},
    {src: " * (x-1)", vars:{x:3}, res: " !"},
    {src: "(x-1", vars:{x:3}, res: "(x-1!"},
].forEach(t => {
    console.log(JSON.stringify(t.src), " ==> ", test(t.src, t.vars, t.res) ? "ok" : "** FAIL **");
});

Conclusion

Parsers are often considered a "difficult" topic, but they don't have to be. For simple languages, the implementation is indeed straightforward.

For complex and irregular languages, things become more complicated. However, it's worth considering whether you really want to work with such complex and irregular languages. They are not only harder for computers to parse but, more importantly, also challenging for humans to use. Is it truly a good idea to venture into that territory?

Take C++, for example; its extremely complex grammar is something you may not want to deal with, both as a parser implementer and as a user.

While this code is just a toy example, it's less than 100 lines long and doesn't rely on any libraries or high-level functions.

Adding more features such as tabled unary operators, right-associativity support, postfix operators, or constructs like array item access x[y] or function calls x(y, z) isn't very difficult to do. Even incorporating constructs like if-then-else or while doesn't require much more complexity.

In my opinion, an interesting programming exercise would be to read and study this code and then attempt to write your own version from scratch, possibly in another language (e.g., Python).

DEV Community: Andrea Griffini