Build a Pratt Parser with Error Recovery

Goal

You build a parser that builds a list of tokens into an AST (the nodes of /root/mini/ast_nodes.py). Expressions use the Pratt approach to handle precedence and associativity with a single table, statements are read with recursive descent, and when an error occurs, you write it down and resume reading from the next statement.

Why it matters

If even one precedence or associativity goes wrong, the program computes a different value without an error. If you group 10 - 4 - 3 from the right, it becomes 9 rather than 3, and no one warns you. And a parser that stops at the first error makes the user fix and rerun as many times as there are errors.

The grammar and the tree

program     := declaration* EOF
declaration := "let" IDENT "=" expr ";"  |  "fn" IDENT "(" [IDENT ("," IDENT)*] ")" block  |  statement
statement   := "print" expr ";" | "if" "(" expr ")" block ["else" (if문 | block)]
             | "while" "(" expr ")" block | "return" [expr] ";" | block | expr ";"
block       := "{" declaration* "}"
결합력      = 1(오른쪽) · || 2 · && 3 · == != 4 · < <= > >= 5 · + - 6 · * / % 7
             앞 - ! 는 피연산자를 8 로 · ^ 9(오른쪽) · 호출 ( 10
노드 위치   ast_nodes.py 맨 위 표 — 연산자 토큰, 호출은 여는 괄호, Let·Fn 은 이름 토큰, 문장은 키워드,
             Block 은 여는 중괄호, ExprStmt 는 식의 위치. && 와 || 는 Logical, 나머지 두 항은 Binary
오류 글자   ParseError(토큰, 메시지), str() 은 "줄:칸: 메시지". 위치는 기대한 것을 찾지 못한 그 토큰
             expected expression · expected ';' · expected ')' · expected '(' · expected '{' ·
             expected '}' · expected identifier · expected '=' · invalid assignment target(그 = 의 위치)
복구        declaration 이 ParseError 를 잡아 self.errors 에 글자를 적고 synchronize() 한 뒤 None.
             synchronize: 지금 토큰이 '}' 가 아닌 STARTERS(fn let if while print return { }) 면 그대로
             멈춘다. 아니면 한 토큰을 소비하고, 끝이 아닌 동안 ';' 바로 뒤이거나 STARTERS 앞이면 멈춘다.

Steps

1. Fill in ParseError, Parser(tokens) (attributes tokens, pos, and errors), and peek, previous, at_end, advance (stays put at EOF), check, match(*kinds), and expect(kind, message) in /root/mini/parser.py.
2. Fill in prefix() — INT, true/false, IDENT, and an expression in parentheses. Hand - and ! over to prefix_operator() (step 4), and for any other token, expected expression at its position.
3. Fill in the POWER table, expression(rbp=0), and infix(left) — precedence and left associativity of binary operations. Hand (, ^, and = over to finish_call and right_assoc.
4. Fill in UNARY, prefix_operator(), and right_assoc(left) — prefix operators, the right associativity of ^ and =, and invalid assignment target if the assignment target is not a name.
5. Fill in finish_call(callee) — from no arguments to many, and chained calls such as f(x)(y).
6. Fill in declaration, let_declaration, fn_declaration, statement, if_statement, block, program, and the module's parse_program(src) (→ (Program, 오류 목록), the error list; for a lexer error, it holds only that one and the tree is None).
7. Fill in STARTERS and synchronize(). The grader compares the error list and the recovered tree of the error programs against the reference.
8. The grader compares the trees of 120 random programs and the error lists of 240 programs with one token broken against the reference.

Notes

• python3 /root/mini/mini.py parse 파일.mini prints the S-expression or the errors with your parser (the placeholder is the file). To look at just an expression, use a one-line file print 식; (the placeholder is the expression).
• The lexer (lexer.py) and the nodes (ast_nodes.py) are laid out when you start the lab. You may also paste in and use your own lexer.py from the previous module.
• Common mistakes: reading every operator as right-associative, grouping -a^b as (-a)^b, making calls looser than unary operators, and spinning in place because recovery consumes no token.
• The session starts at 60 minutes and you can extend it with the +time button, and when it ends /root/mini disappears.

Look at, eat, and expect tokens

A single pos points into the token list. advance returns the current token and raises pos only if it is not EOF. expect advances if the kind matches, and otherwise raises a ParseError at the position of the current token (peek) — not the token just passed.

The first piece of an expression

Dispatch on the token kind. INT is int(text), true/false is Bool, IDENT is Var, and the node position is that token's line and column. For parentheses, read the inside with expression() and expect ')', but do not create a separate parenthesis node; return the inner expression as it is.

Resolve precedence with the binding power table

while POWER.get(peek().kind, 0) > rbp: left = infix(left). infix eats the operator and reads the right side with expression(that operator's binding power). An operator of the same level has the same binding power and cannot get past >, so it returns to the outer loop and becomes left-associative.

Prefix operators and right associativity

A prefix operator reads its operand with expression(UNARY). UNARY must be greater than * and less than ^ for -a*b to be (-a)*b and -a^b to be -(a^b). ^ and = read the right side with binding power - 1 so the right side swallows the same level. If the left of = is not a Var, it is an error at the position of that =.

Calls — the tightest binding

Treat ( also as a postfix operator with binding power 10. finish_call eats the opening parenthesis, and if the next is not ')', it reads expression(), repeats while there is a ',', and then expects ')'. The position of the Call node is the opening parenthesis.

Statements and blocks — recursive descent

declaration dispatches let and fn, and statement dispatches print, if, while, return, a block, and an expression statement. If an if follows else, call if_statement again to build the chain. declaration catches a ParseError, writes it down, runs synchronize, and returns None, and block and program discard the None.

Get back on your feet after an error

If the error token is a STARTERS that is not '}', stop without consuming it — a statement that starts with that keyword eats the keyword first, so it does not spin in place. Otherwise eat at least one token, and stop if previous() is ';' or peek() is in STARTERS.

Random programs and broken programs

There is no new code. If a broken program gives more errors than the reference, it is reading again at the wrong place after recovery (a cascading error), and if fewer, it is skipping too far after one error.