Recent Posts

How Desmos uses Pratt Parsers

What is Parsing?

When you read an expression, like 1/2+3.4, you can immediately understand some of its meaning. You recognize that there are three numbers, and that the numbers are combined with operators. You may also recall that division has higher precedence than addition, so you would divide 1/2 before adding +3.4 when evaluating the expression.

Compare this to how you perceive 2H3SGKHJD. At first glance it appears to be a nonsense sequence of characters. If I told you that letters should be grouped in pairs with G being a separator, your mental model might look closer to 2H 3S ; KH JD, which takes us a step towards understanding that this string represents hands in a card game.

Parsing is the process of taking a string of characters and converting them into an Abstract Syntax Tree (or, AST). This is a representation of the structure of the expression, for example:

OperatorNode(
    operator: "+",
    left: OperatorNode(
        operator: "/",
        left: 1,
        right: 2
    ),
    right: 3.4
)

or, as a diagram,

         "+"
       /     \
    "/"        3.4
  /     \
1         2

Such a tree is a first step towards computing the value of the expression, or rendering it beautifully.

a Desmos expression list entry showing a formatted layout of 1 / 2 + 3.4 here

So, how does one create an AST? At Desmos we use the approach described by Vaughan Pratt. This article will begin with what is hopefully a clear and concise explanation of how Pratt Parsing works. We will then explain our motivations for adopting this technique at Desmos and compare it to the jison parser generator, our previous approach.

Finally, we provide a sample implementation of the parser (and a lexer) in Typescript, integrated with CodeMirror. We hope this will be a useful reference and starting point for anyone interested in doing parsing in the browser.

How does it work?

Our parse function will operate over a tokens object. This is a sequence of tokens, like [1, "/", 2, "+", 3.4] that is generated from our input through a process called lexing. We will not go into the details of lexing here, other than to point you at our sample implementation.

The tokens object is a token stream, which allows us to consume a token, returning the next token and advancing the stream. We can also peek a token, which gives us the next token without advancing the stream.

[1, "/", 2, "+", 3.4].consume() -> 1, ["/", 2, "+", 3.4]
[1, "/", 2, "+", 3.4].peek() -> 1, [1, "/", 2, "+", 3.4]

[].consume() -> empty token, []
[].peek() -> empty token, []

Let’s start with a recursive call and fill things out as we go along. We will present our approach in pseudocode, but you are welcome to reference the Typescript implementation as we go along.

function parse(tokens):
    firstToken = tokens.consume()

    if firstToken is a number
        leftNode = NumberNode(firstToken)
    otherwise
        Error("Expected a number")

    nextToken = tokens.consume()

    if nextToken is an operator token
        rightNode = parse(tokens)

        return OperatorNode(
            operator: nextToken,
            leftNode,
            rightNode
        )

    otherwise
        return leftNode

We expect a number token followed by an optional operator. We then perform a recursive call to find the sub-expression to the right. So far so good – we start getting an idea of how parsing an expression like 3 * 2 + 1 might work:

parse [3, "*", 2, "+", 1]
1 consume 3 as a NumberNode into leftNode
1 consume "*" to be nextToken
1 rightNode = parse [2, "+", 1]
    2 consume 2 as a NumberNode into leftNode
    2 consume "+" to be nextToken
    2 rightNode = parse [1]
        3 consume 1    as a NumberNode into leftNode
        3 no next token
        3 return:
            1
    2 combine 2, "+" and 1 into an OperatorNode
    2 return:
            "+"
          /     \
        2         1

1 combine 3, "*" and rightNode into an OperatorNode
1 return:
    "*"
  /     \
3        "+"
       /     \
     2         1

more

More Intuitive Calculator Arithmetic

Early last week, Desmos released a change to the way that basic arithmetic is evaluated in our calculators. The goal of this change is to make the calculators’ answers match people’s intuitions more often by computing numerical answers exactly instead of approximately in more cases where a human would.

more

Pressing a Key in the Calculator

In his wildly popular 2015 Bloomberg article about programming, Paul Ford included a short section about what happens inside your computer between pressing the “a” key and getting an a printed to the screen. His point was that even the most straightfoward human instructions can become surprisingly delicate and complex when filtered through wire and silicon, and that programmers are basically just humans with the right constitution to brook the journey.

more