Beautiful Code [140]
d A e B f
does operand e bind to A or to B? In other words, are we talking about:
(d A e) B f
or:
d A (e B f)
Ultimately, the complexity in the process of parsing comes down to the resolution of this ambiguity. The technique we will develop here uses token objects whose members include binding powers (or precedence levels), and simple methods called nud (null denotation) and led (left denotation). A nud does not care about the tokens to the left. A led does. A nud method is used by values (such as variables and literals) and by prefix operators. A led method is used by infix operators and suffix operators. A token may have both a nud and a led. For example, -might be both a prefix operator (negation) and an infix operator (subtraction), so it would have both nud and led methods.
Top Down Operator Precedence > Expressions
9.5. Expressions
The heart of Pratt's technique is the expression function. It takes a right binding power that controls the aggressiveness of its consumption of tokens that it sees to the right. It returns the result of calling methods on the tokens it acts upon:
var expression = function (rbp) {
var left;
var t = token;
advance( );
left = t.nud( );
while (rbp < token.lbp) {
t = token;
advance( );
left = t.led(left);
}
return left;
}
expression calls the nud method of the token. The nud is used to process literals, variables, and prefix operators. After that, as long as the right binding power is less than the left binding power of the next token, the led methods are invoked. The led is used to process infix and suffix operators. This process can be recursive because the nud and led methods can call expression.
Top Down Operator Precedence > Infix Operators
9.6. Infix Operators
The + operator is an infix operator, so it will have a led method that makes the token object into a tree, where the two branches are the operand to the left of the + and the operand to the right. The left operand is passed into the led, and the right is obtained by calling the expression method.
The number 60 is the binding power of +. Operators that bind tighter or have higher precedence have greater binding powers. In the course of mutating the stream of tokens into a parse tree, we will use the operator tokens as containers of operand nodes:
symbol("+", 60).led = function (left) {
this.first = left;
this.second = expression(60);
this.arity = "binary";
return this;
};
When we define the symbol for [], we see that only the id and binding powers are different. It has a higher binding power because it binds more tightly:
[] Pratt's paper is available at http://portal.acm.org/citation.cfm?id=512931; more information about Pratt himself can be found at http://boole.stanford.edu/pratt.html.
symbol("*", 70).led = function (left) {
this.first = left;
this.second = expression(70);
this.arity = "binary";
return this;
};
Not all infix operators will be this similar, but many will, so we can make our work easier by defining an infix function that will help us specify infix operators. The infix function will take an id and a binding power, and optionally a led function. If a led function is not provided, it will supply a default led that is useful in most cases:
var infix = function (id, bp, led) {
var s = symbol(id, bp);
s.led = led || function (left) {
this.first = left;
this.second = expression(bp);
this.arity = "binary";
return this;
};
return s;
}
This allows a more declarative style for specifying operators:
infix("+", 60);
infix("-", 60);
infix("*", 70);
infix("/", 70);
The string === is JavaScript's exact-equality comparison operator:
infix("===", 50);
infix("!==", 50);
infix("<", 50);
infix("<=", 50);
infix(">", 50);
infix(">=", 50);
The ternary operator takes three expressions,