Precedence with Two Numbers — Pratt Parsing

In one line

A parser builds a line of tokens into a tree. If you read statements with recursive descent, which has one function per grammar rule, and expressions with Pratt parsing, which gives each operator a binding power (a single number) and grows the tree by comparing those numbers, precedence and associativity gather on a single table, and even when an error occurs you can resume reading from the next statement.

Why this was needed

1 - 2 - 3 is (1 - 2) - 3, so it is -4, and 2 ^ 3 ^ 2 is 2 ^ (3 ^ 2), so it is 512. They have the same shape, but the grouping direction is opposite. -2 ^ 2 is -4 but -2 * 2 is (-2) * 2. If these rules go wrong, the program computes a different value without a syntax error — the hardest kind of bug to find.

You can also read expressions with recursive descent that has one function per grammar rule (as in 덧셈 := 곱셈 (('+'|'-') 곱셈)*), but one function is created per precedence level, so ten levels means ten functions, and to insert one level you have to fix the chain of functions. Pratt parsing reduces this to a single table. A level is a number, and associativity is whether you use that number as it is or one lower when reading the right side.

And a parser must not stop at the first error. Users do not want to repeat fixing one error and rerunning to see the next. Only if it writes down the error, skips to a place where the next statement is likely to start, and then keeps reading can it report several errors at once.

How it works

The heart of a Pratt parser is a single loop.

expression(rbp):
    left = prefix()                      # 숫자·이름·괄호·앞에 붙는 - !
    while 다음 연산자의 결합력 > rbp:
        left = infix(left)               # 그 연산자로 left 를 왼쪽 자식 삼아 한 층 위 노드를 만든다
    return left

infix reads the right operand with expression(그 연산자의 결합력) (the placeholder is that operator's binding power). Then the right expression swallows only operators stronger than itself and stops before an operator of the same level, handing it to the outer loop — that is left associativity. For right associativity (^, =), the right side is read with 결합력 - 1 (the binding power minus 1), so the right side swallows even the same level. This is how the tree grows in 1 - 2 * 3 - 4 (- is 6, * is 7).

읽은 것            left 의 모양               다음 연산자  비교
1                  1                          -  6 > 0     → infix: 오른쪽을 expression(6) 으로
  2 * 3            (* 2 3)                    -  6 > 6 ?   → 아니오, 오른쪽은 여기서 멈춤
1 - (2*3)          (- 1 (* 2 3))              -  6 > 0     → infix 한 번 더, 방금 트리가 왼쪽 자식으로
  4                4                          끝
최종               (- (- 1 (* 2 3)) 4)

This is the course's binding power table. A prefix - or ! reads its operand at 8, so it cannot swallow * (7) but does swallow ^ (9) — that is why -a*b is (-a)*b and -a^b is -(a^b).

Binding power	Operator	Associativity
1	=	Right
2 · 3	|| · &&	Left
4 · 5	== != · < <= > >=	Left
6 · 7	+ - · * / %	Left
8	Prefix - !	—
9 · 10	^ · call f(…)	Right · —

Assignment is right-associative, and its left side must be a name. a = b = c is a = (b = c), and a + b = c is read as (a + b) = c and then rejected with "the assignment target is not a name." If you leave this check out, the parser quietly builds a strange tree.

Statements are read with recursive descent. When it sees if, it expects the order ( expression ) block [else (if statement | block)], and if the token is not the expected one, it raises an error such as "expected ';'" at the position of that token. The place that catches errors is a single declaration (declaration). When it catches one, it writes down the error and recovers (synchronize) — it skips tokens until right after a ; or just before let, fn, if, while, print, return, {, or }. There is one thing to keep in mind here. It must advance at least one token. If an error occurs at a token that cannot start any statement, such as an outermost }, and it stops right there, the next declaration raises the same error at the same token and loops forever.

What it looks like in the field

• Hand-written parsers in GCC and Clang. Both compilers use hand-written recursive descent parsers instead of parser generators (yacc, bison). This is because people can polish error messages and recovery in fine detail. For the expression part, the approach of reading with a precedence table (operator precedence parsing) has the same idea as Pratt.
• Several errors at once. If a compiler shows twenty errors and the later ones look absurd, recovery is lacking. It is a "cascading error," where after the first error it began reading again at the wrong place and read perfectly good code as errors. That is why most compilers tell you to "fix from the first error."
• The editor's forgiving parser. An editor's language server always receives code with broken syntax while you type. Only a parser with good recovery makes autocomplete and underlines work properly even in the code beneath a half-written function.

What you will do in the next lab

You build the parser in parser.py in seven pieces — tools to look at, consume, and expect tokens; literals, names, and parentheses; the Pratt loop and binary operations; prefix operators and right associativity (^ and =) with the assignment target check; calls; statements and blocks; and error recovery. The tree shape is fixed by the nodes and S-expressions of ast_nodes.py (provided by the course), so the grader compares the trees and node positions of hundreds of random expressions against the reference parser down to the character.