class Parser {
expr(rbp = 0) {
let left = this.nud()
let token = this.currentToken()
while (left !== null && token !== null && rbp < token.bp) {
left = this.led(left)
token = this.currentToken()
}
// '(2 * 3) + 1' is returned.
return left
}
/**
* Parses and returns a primary expression (or nud, for "null denotation").
*/
nud() {
const token = this.advanceToken()
if (token === null)
return null
// A dispatch table could also be used here, which would look like this:
//
// for (const parser of unaryParsers) {
// if (parser.accepts(token))
// return parser.parse(this)
// }
// return null
//
// Or even:
//
// return unaryParsers[token.kind]?.parse(this) ?? null
//
if (token.kind === NUMBER)
return Expression.number(token.value)
if (token.kind === POS || token.kind === NEG)
return Expression.unary(token.kind, this.nud())
if (token.kind === LPAREN) {
const inner = this.expr(),
current = this.advanceToken()
if (current === null || current.kind !== RPAREN)
return null
else
return inner
}
return null
}
/**
* Parses and returns a binary expression (or led, for "left denotation"),
* given its left operand.
*/
led(left) {
// 'led' is only called when the current token wraps a binary
// operator (e.g. '+', '*'). We retrieve that token and advance
// the stream to the next one.
const token = this.advanceToken()
if ([ADD, SUB, MUL, DIV, POW].includes(token.kind))
return Expression.binary(token.kind, left, this.expr(token.abp))
if (token.kind === QUE) {
// A question mark introduces a ternary expression (i.e. 'cond ? ifTrue : ifFalse').
//
// First we parse the 'ifTrue' expression with a low binding power so
// that '? 2 * 3 : 4 / 5' only returns to us at ':' with the expression '2 * 3'.
const right = this.expr(token.abp)
// We might have reached the end of the input or a right parenthesis.
// That's an error.
if (this.advanceToken().kind !== COL)
return null
// We parse the rest of the expression into 'ifFalse' and return the ternary node.
return Expression.ternary(left, right, this.expr(token.abp))
}
return null
}
// ====================================================================================
// == CONSTRUCTOR ===================================================================
// ====================================================================================
constructor(tokens) {
this.tokens = tokens
// Two ways of processing tokens are shown:
// - The 'array' way, which uses a pre-computed array of tokens
// and keeps track of the current position using an integer.
// - The 'lazy' way, which uses a generator and can ask for
// tokens to be computed on-demand. It is slightly less intuitive
// to use, but here a lazy collection can be very useful.
if (Array.isArray(tokens)) {
this.position = 0
} else {
this.curr = tokens.next()
this.next = tokens.next()
}
console.clear()
if (trace) {
// Some tracing, open your console to find out how expressions
// are parsed behind the scenes!
traceParser(this)
}
}
// ====================================================================================
// == TOKENS HANDLING ===============================================================
// ====================================================================================
/**
* Returns the current token and advances to the next token.
*/
advanceToken() {
// Needlessly complicated logic to handle both iterators and arrays as input.
if (Array.isArray(this.tokens)) {
return this.position >= this.tokens.length ? null : this.tokens[this.position++]
} else {
const curr = this.curr
this.curr = this.next
this.next = this.tokens.next()
return curr.done ? null : curr.value
}
}
/**
* Returns the current token without advancing.
*/
currentToken() {
// Ditto.
if (Array.isArray(this.tokens)) {
return this.position >= this.tokens.length ? null : this.tokens[this.position]
} else {
return this.curr.done ? null : this.curr.value
}
}
}