用两个数字解决优先级 — Pratt 解析

한 줄 요약

파서는 토큰의 줄을 트리로 세웁니다. 문장은 문법 규칙 하나에 함수 하나를 두는 재귀 하강으로, 식은 연산자마다 결합력(숫자 하나)을 두고 그 숫자를 비교해 트리를 키우는 Pratt 파싱으로 읽으면, 우선순위와 결합 방향이 표 한 장에 모이고 오류가 나도 다음 문장부터 다시 읽을 수 있습니다.

왜 이게 필요했나

1 - 2 - 3 은 (1 - 2) - 3 이어서 -4 이고, 2 ^ 3 ^ 2 는 2 ^ (3 ^ 2) 여서 512 입니다. 같은 모양인데 묶는 방향이 반대입니다. -2 ^ 2 는 -4 이지만 -2 * 2 는 (-2) * 2 입니다. 이 규칙이 어긋나면 프로그램은 문법 오류 없이 다른 값을 계산합니다 — 가장 찾기 어려운 종류의 버그입니다.

문법 규칙마다 함수를 하나씩 두는 재귀 하강(덧셈 := 곱셈 (('+'|'-') 곱셈)* 처럼)으로도 식을 읽을 수 있지만, 우선순위 층마다 함수가 하나씩 생겨 층이 열 개면 함수도 열 개가 되고, 층을 하나 끼우려면 함수 사슬을 고쳐야 합니다. Pratt 파싱은 이것을 표 한 장으로 줄입니다. 층은 숫자이고, 결합 방향은 오른쪽을 읽을 때 그 숫자를 그대로 쓰느냐 하나 낮추느냐입니다.

그리고 파서는 첫 오류에서 멈추면 안 됩니다. 사용자는 오류 하나를 고치고 다시 돌려 다음 오류를 보는 일을 반복하고 싶지 않습니다. 오류를 적어 두고 다음 문장이 시작될 만한 곳까지 건너뛴 뒤 계속 읽어야 한 번에 여러 오류를 알려 줄 수 있습니다.

어떻게 동작하나

Pratt 파서의 심장은 반복문 하나입니다.

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

infix 는 오른쪽 피연산자를 expression(그 연산자의 결합력) 으로 읽습니다. 그러면 오른쪽 식은 자기보다 강한 연산자만 삼키고, 같은 층의 연산자 앞에서 멈춰 바깥 반복문에 넘깁니다 — 그것이 왼쪽 결합입니다. 오른쪽 결합(^, =)은 오른쪽을 결합력 - 1 로 읽어 같은 층까지 오른쪽이 삼키게 합니다. 1 - 2 * 3 - 4 에서 트리가 자라는 모습은 이렇습니다(- 는 6, * 는 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)

이 코스의 결합력 표입니다. 앞에 붙는 -·! 는 피연산자를 8 로 읽으므로 *(7)는 삼키지 못하고 ^(9)는 삼킵니다 — 그래서 -a*b 는 (-a)*b, -a^b 는 -(a^b) 입니다.

결합력	연산자	결합
1	=	오른쪽
2 · 3	|| · &&	왼쪽
4 · 5	== != · < <= > >=	왼쪽
6 · 7	+ - · * / %	왼쪽
8	앞에 붙는 - !	—
9 · 10	^ · 호출 f(…)	오른쪽 · —

대입은 오른쪽 결합이면서 왼쪽이 이름이어야 합니다. a = b = c 는 a = (b = c) 이고, a + b = c 는 (a + b) = c 로 읽힌 뒤 "대입 대상이 이름이 아니다" 로 거절됩니다. 이 검사를 빼면 파서는 조용히 이상한 트리를 만듭니다.

문장은 재귀 하강으로 읽습니다. if 를 보면 ( 식 ) 블록 [else (if 문 | 블록)] 순서로 기대하고, 기대한 토큰이 아니면 그 토큰의 위치로 "expected ';'" 같은 오류를 냅니다. 오류를 잡는 곳은 선언 하나(declaration)입니다. 잡으면 오류를 적고 복구(synchronize)합니다 — ; 바로 뒤나 let·fn·if·while·print·return·{·} 앞까지 토큰을 건너뜁니다. 이때 지켜야 할 것이 하나 있습니다. 적어도 한 토큰은 전진해야 합니다. 맨 바깥의 } 처럼 어떤 문장도 시작할 수 없는 토큰에서 오류가 났는데 그 자리에서 멈추면, 다음 선언이 같은 토큰에서 같은 오류를 내며 영원히 돕니다.

현장에서 만나는 모습

• GCC 와 Clang 의 손으로 쓴 파서. 두 컴파일러 모두 파서 생성기(yacc·bison) 대신 손으로 쓴 재귀 하강 파서를 씁니다. 오류 메시지와 복구를 사람이 세밀하게 다듬을 수 있어서입니다. 식 부분은 우선순위 표로 읽는 방식(연산자 우선순위 파싱)이 Pratt 과 같은 생각입니다.
• 한 번에 여러 오류. 컴파일러가 오류를 스무 개씩 보여 주는데 뒤쪽 것이 엉뚱하다면 복구가 모자란 것입니다. 첫 오류 뒤에 잘못된 곳에서 다시 읽기 시작해 멀쩡한 코드를 오류로 읽은 '연쇄 오류' 입니다. 그래서 대부분의 컴파일러가 "첫 오류부터 고치라" 고 말합니다.
• 편집기의 관대한 파서. 편집기의 언어 서버는 입력하는 동안 늘 문법이 틀린 코드를 받습니다. 복구가 좋은 파서라야 반쯤 쓴 함수 아래의 코드에서도 자동 완성과 밑줄이 제대로 동작합니다.

다음 실습에서 할 것

parser.py 에 파서를 일곱 조각으로 만듭니다 — 토큰을 보고·소비하고·기대하는 도구, 리터럴·이름·괄호, Pratt 반복문과 두 항 연산, 앞 연산자와 오른쪽 결합(^·=)과 대입 대상 검사, 호출, 문장과 블록, 그리고 오류 복구. 트리 모양은 ast_nodes.py(코스가 내어 줌)의 노드와 S-식으로 정해져 있어, 채점기가 무작위 식 수백 개의 트리와 노드 위치를 기준 파서와 글자까지 대조합니다.