ariya.io About Talks Articles

parsing: imperative vs declarative

1 min read

Syntactic analyzer, often referred as parser, is either written by hand or generated from the syntax declaration (grammar). While working on a certain parser project, I realize that sometimes the difference between these two strategies becomes rather blurry. For example, consider a typical math expression which has this fragment in its grammar:

Multiplicative ::= Unary |
                   Multiplicative '*' Unary |
                   Multiplicative '/' Unary |
                   Multiplicative '%' Unary |

Additive ::= Multiplicative |
             Additive '+' Multiplicative |
             Additive '-' Multiplicative

The hand-constructed JavaScript code for each of the rules above may look like this:

function parseMultiplicativeExpression() {
    var expr = parseUnaryExpression();
 
    if (match('*') || match('/') || match('%')) {
        expr = {
            type: Syntax.BinaryExpression,
            operator: lexer.next().value,
            left: expr,
            right: parseMultiplicativeExpression()
        };
    }
 
    return expr;
}
 
function parseAdditiveExpression() {
    var expr = parseMultiplicativeExpression();
 
    if (match('+') || match('-')) {
        expr = {
            type: Syntax.BinaryExpression,
            operator: lexer.next().value,
            left: expr,
            right: parseAdditiveExpression()
        };
    }
 
    return expr;
}

Thus, although the manually crafted functions are essentially imperative, its closeness to the grammar declaration makes the implementation really easy to understand. A parser generator certainly has some advantages with respect to optimization. For educational and analysis purposes however, nothing beats debugging a chain of functions which you have written with your own bare hands!

Related posts:

♡ this article? Explore more articles and follow me Twitter.

Share this on Twitter Facebook