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!