Pratt Parser

This project demonstrates the fundamentals of a Pratt Parser. It is based on this paper by Vaughan Pratt, and also learns from this article and this article.

Additionally, this README file attempts to simplify the concepts so that, when I come back to try to implement this again (at some undetermined point in the future), I will be able to remember how this works.

This README assumes that you already have read the previous two articles as this text merely attempts to simplify some of the concepts, hopefully adding intuition to them.

Concepts

In general, the Pratt Parser solves the following problem: given the string "1 + 2 * 3", does the "2" associate with the "+" or the "*". It also solves "-" being both a prefix and infix operator, as well as elegantly handling right associativity.

The Pratt Parser is based on three computational units:

parser.expr(rbp) // the expression parser
token.nud() // "Null Denotation" (operates on no "left" context)
token.led(left, bp) // "Left Denotation" (operates with "left" context)

The parser.expr(rbp) function looks like:

function expr(rbp) {
	let left = lexer.next().nud() // (1)
	while (rbp < lexer.peek().bp) { // (2)
		const operator = lexer.next() // (3)
		left = operator.led(left, operator.bp) // (4)
	}
	return left
}

Of course, nud and led may recursively call expr.

The expr method can be summarized in english as "The loop (while) builds out the tree to the left, while recursion (led -> expr) builds the tree out to the right; nud handles prefix operators":

function expr(rbp) {
	// (1) handle prefix operator
	// (2) continue until I encounter an operator of lesser precedence than myself
	// (3) "eat" the operator
	// (4) give the operator the left side of the tree, and let it build the right side; this new tree is our new "left"
}

Contributions

The Pratt Parser is a new concept to me, and thus this README would probably benefit from clarification, and the code would probably also benefit from cleanup. Submit a PR if you feel so inclined!

LICENSE

ISC License (ISC) Copyright (c) 2016, Jonathan Apodaca [email protected]

Permission to use, copy, modify, and/or distribute this software for any purpose with or without fee is hereby granted, provided that the above copyright notice and this permission notice appear in all copies.

THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.