Build a Pratt Parser with Error Recovery

목표

토큰 목록을 AST(/root/mini/ast_nodes.py 의 노드)로 세우는 파서를 만듭니다. 식은 Pratt 방식으로 우선순위·결합 방향을 표 하나로 다루고, 문장은 재귀 하강으로 읽으며, 오류가 나면 적어 두고 다음 문장부터 다시 읽습니다.

왜 중요한가

우선순위나 결합 방향이 하나라도 어긋나면 프로그램은 오류 없이 다른 값을 계산합니다. 10 - 4 - 3 을 오른쪽부터 묶으면 3 이 아니라 9 가 되고, 아무도 경고하지 않습니다. 그리고 첫 오류에서 멈추는 파서는 사용자에게 고치고 다시 돌리기를 오류 수만큼 시킵니다.

문법과 트리

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 앞이면 멈춘다.

단계

1. /root/mini/parser.py 의 ParseError, Parser(tokens)(속성 tokens·pos·errors)와 peek·previous·at_end·advance(EOF 에서는 제자리)·check·match(*kinds)·expect(kind, message) 를 채웁니다.
2. prefix() 를 채웁니다 — INT·true/false·IDENT·괄호로 묶은 식. -·! 는 prefix_operator() 로 넘기고(4단계), 그 밖의 토큰이면 그 위치로 expected expression.
3. POWER 표와 expression(rbp=0), infix(left) 를 채웁니다 — 두 항 연산의 우선순위와 왼쪽 결합. (·^·= 는 finish_call·right_assoc 으로 넘깁니다.
4. UNARY, prefix_operator(), right_assoc(left) 를 채웁니다 — 앞 연산자, ^·= 의 오른쪽 결합, 대입 대상이 이름이 아니면 invalid assignment target.
5. finish_call(callee) 를 채웁니다 — 인자 없음부터 여러 개까지, f(x)(y) 처럼 이어 부르기.
6. declaration·let_declaration·fn_declaration·statement·if_statement·block·program 과 모듈의 parse_program(src)(→ (Program, 오류 목록), 렉서 오류는 그 하나만 담고 트리는 None)을 채웁니다.
7. STARTERS 와 synchronize() 를 채웁니다. 채점기가 오류 프로그램의 오류 목록과 살려 낸 트리를 기준과 대조합니다.
8. 채점기가 무작위 프로그램 120편의 트리와, 토큰 하나를 망가뜨린 240편의 오류 목록을 기준과 대조합니다.

참고

• python3 /root/mini/mini.py parse 파일.mini 가 여러분의 파서로 S-식이나 오류를 찍습니다. 식만 보려면 print 식; 한 줄짜리 파일을 쓰세요.
• 렉서(lexer.py)와 노드(ast_nodes.py)는 실습을 시작할 때 깔려 있습니다. 앞 모듈에서 만든 여러분의 lexer.py 를 붙여 넣어 써도 됩니다.
• 흔한 실수: 모든 연산자를 오른쪽 결합으로 읽는 것, -a^b 를 (-a)^b 로 묶는 것, 호출을 단항보다 느슨하게 두는 것, 복구에서 한 토큰도 소비하지 않아 제자리를 도는 것.
• 세션은 60분에 시작해 ＋시간으로 늘릴 수 있고, 끝나면 /root/mini 가 사라집니다.

토큰을 보고, 먹고, 기대한다

pos 하나로 토큰 목록을 가리킵니다. advance 는 지금 토큰을 돌려주고, 그것이 EOF 가 아닐 때만 pos 를 올립니다. expect 는 종류가 맞으면 advance, 아니면 지금 토큰(peek)의 위치로 ParseError 를 냅니다 — 방금 지난 토큰이 아닙니다.

식의 첫 조각

토큰 종류로 가릅니다. INT 는 int(text), true/false 는 Bool, IDENT 는 Var 이고 노드 위치는 그 토큰의 줄·칸입니다. 괄호는 안쪽을 expression() 으로 읽고 ')' 를 기대하되, 괄호 노드는 따로 만들지 않고 안쪽 식을 그대로 돌려줍니다.

결합력 표로 우선순위를 푼다

while POWER.get(peek().kind, 0) > rbp: left = infix(left). infix 는 연산자를 먹고 오른쪽을 expression(그 연산자의 결합력) 으로 읽습니다. 같은 층의 연산자는 결합력이 같아 > 를 넘지 못하므로 바깥 반복으로 돌아가 왼쪽 결합이 됩니다.

앞 연산자와 오른쪽 결합

앞 연산자는 피연산자를 expression(UNARY) 로 읽습니다. UNARY 가 * 보다 크고 ^ 보다 작아야 -a*b 는 (-a)*b, -a^b 는 -(a^b) 입니다. ^ 와 = 는 오른쪽을 결합력 - 1 로 읽어 같은 층을 오른쪽이 삼키게 합니다. = 의 왼쪽이 Var 가 아니면 그 = 위치로 오류입니다.

호출 — 가장 단단하게 묶인다

( 도 결합력 10 의 뒤에 붙는 연산자로 봅니다. finish_call 은 여는 괄호를 먹고, ')' 가 아니면 expression() 을 읽고 ',' 가 있는 동안 되풀이한 뒤 ')' 를 기대합니다. Call 노드의 위치는 여는 괄호입니다.

문장과 블록 — 재귀 하강

declaration 은 let·fn 을, statement 는 print·if·while·return·블록·식 문장을 가릅니다. else 뒤에 if 가 오면 if_statement 를 다시 불러 사슬을 만듭니다. declaration 은 ParseError 를 잡아 적고 synchronize 한 뒤 None 을 돌려주며, block·program 은 None 을 버립니다.

오류 뒤에 다시 일어선다

오류 토큰이 '}' 가 아닌 STARTERS 면 소비하지 않고 멈춥니다 — 그 키워드로 시작하는 문장은 키워드부터 먹으므로 제자리를 돌지 않습니다. 아니면 적어도 한 토큰을 먹고, previous() 가 ';' 이거나 peek() 이 STARTERS 이면 멈춥니다.

무작위 프로그램과 망가뜨린 프로그램

새 코드는 없습니다. 망가뜨린 프로그램에서 오류가 기준보다 많으면 복구 뒤 엉뚱한 곳에서 다시 읽고 있는 것(연쇄 오류)이고, 적으면 한 오류 뒤에 너무 멀리 건너뛰는 것입니다.