파싱 알고리즘과 프랫 파서

파싱이 하는 일

인터프리터는 코드 문자열을 다음 순서로 실행한다. 셸도 셸 스크립트라는 언어의 인터프리터다.

flowchart LR
  n1["입력 문자열<br/>#quot;a + b * c#quot;"] -->|"렉싱"| n2["토큰 배열<br/>[a, +, b, *, c]"]
  n2 -->|"파싱"| n3["추상 구문 트리(AST)<br/>(+ a (* b c))"]
  n3 -->|"평가"| n4["실행"]

렉싱(lexing, 토큰화): 연산자·키워드·식별자처럼 의미를 갖는 최소 단위(token)로 쪼갠다.
파싱(parsing): 토큰을 문법에 맞게 묶어 추상 구문 트리(AST) 로 만든다. 같은 토큰열도 묶는 순서에 따라 뜻이 달라진다. a + b * c를 (a + b) * c로 묶으면 틀린 해석이다.
평가(evaluating): 트리를 순회하며 실행한다.

파서 생성기(yacc/bison, ANTLR)가 문법 파일에서 파서를 만들어 주지만, 연산자 표현식은 손으로 짜는 경우가 많다. 그 대표가 프랫 파서다.

파싱 알고리즘의 계보

방식	핵심	장점	단점
재귀 하향(백트래킹)	문법 규칙마다 함수를 두고 위 규칙부터 차례로 시도	문법을 그대로 코드로 옮김	실패하면 만든 트리를 버리고 다른 규칙 시도 → 최악 지수 시간, 오류 위치 파악 어려움
연산자 우선순위(플로이드)	토큰 종류에 맞는 처리를 하고, 우선순위표로 묶을지 미룰지 결정	백트래킹 없이 O(n), 오류를 그 자리에서 발견	상향식 shift-reduce라 구현이 직관적이지 않음
프랫(하향식 연산자 우선순위)	재귀 하향 구조 + 연산자마다 바인딩 파워	O(n), 함수 몇 개로 구현, 전위·중위·후위 연산자를 쉽게 추가	피연산자끼리 바로 붙는 비정형 문법에 약함

플로이드(Robert W. Floyd)의 아이디어는 완전 탐색을 그리디로 바꾼 것이다. 우선순위를 미리 알면 시도해 보고 되돌릴 필요 없이 처음부터 맞게 묶을 수 있다. shift-reduce 파서는 토큰을 스택에 쌓다가(shift), 스택 위 연산자의 우선순위가 새 연산자보다 높으면 스택의 노드를 묶는다(reduce).

프랫(Vaughan Pratt)은 1973년 이 우선순위 개념을 하향식 재귀 구조에 합쳤다. 재귀 하향 파서의 간결함과 연산자 우선순위 파서의 효율을 함께 얻는다.

재귀 하향 파서: 문법을 함수로 옮기기

백트래킹이 없는 재귀 하향 파서는 지금도 가장 흔한 손 파서다. 다음 토큰 하나만 보고 어느 규칙인지 결정할 수 있는 문법(LL(1))이면 되돌아갈 일이 없다. JSON이 대표적이다. 문법을 BNF(Backus-Naur Form)로 적으면 규칙 하나가 함수 하나가 된다.

<json>   ::= <object> | <array>
<object> ::= '{' [ <member> *( ',' <member> ) ] '}'
<member> ::= <string> ':' <value>
<array>  ::= '[' [ <value> *( ',' <value> ) ] ']'
<value>  ::= <string> | <number> | <object> | <array> | true | false | null

BNF 표기	코드
`A \| B` (선택)	다음 글자를 보고 분기: `{`면 객체, `[`면 배열, `"`면 문자열
`[ X ]` (생략 가능)	닫는 괄호가 바로 오면 건너뛴다
`*( ',' X )` (0회 이상 반복)	쉼표가 나오는 동안 반복
규칙 안의 다른 규칙	그 함수를 호출. `value` ↔ `object`·`array`가 서로를 부르는 상호 재귀

def parse_value(s, i):
    i = skip_ws(s, i)
    if s[i] == '{': return parse_object(s, i)
    if s[i] == '[': return parse_array(s, i)
    if s[i] == '"': return parse_string(s, i)
    return parse_literal(s, i)                 # 숫자, true, false, null
 
def parse_array(s, i):                         # 각 함수는 (값, 다음 위치)를 돌려준다
    i, items = skip_ws(s, i + 1), []
    if s[i] == ']':
        return items, i + 1                    # 빈 배열 [ ]
    while True:
        v, i = parse_value(s, i)
        items.append(v)
        i = skip_ws(s, i)
        if s[i] == ']': return items, i + 1
        if s[i] != ',': raise SyntaxError(f"',' 또는 ']'가 필요함: {i}")
        i += 1                                 # 쉼표 뒤에는 반드시 값 → 끝 쉼표는 오류

반복 구조 X *( ',' X ) 덕분에 "마지막 원소 뒤에는 쉼표가 없다"는 규칙이 저절로 지켜진다. 파싱 결과는 타입 태그와 값(문자열·배열·키-값 목록)을 담는 트리 노드로 표현한다. 연산자 우선순위가 여러 단계인 수식에서는 단계마다 함수를 하나씩 두어야 해 함수가 늘어나는데, 이 부분을 바인딩 파워 표 하나로 압축한 것이 프랫 파서다.

바인딩 파워

바인딩 파워(binding power)는 연산자가 양옆의 피연산자를 끌어당기는 힘이다. 우선순위가 높을수록 세다.

왼쪽 바인딩 파워(lbp): 연산자가 왼쪽 피연산자를 당기는 힘
오른쪽 바인딩 파워(rbp): 연산자가 오른쪽 피연산자를 당기는 힘
피연산자 하나를 사이에 둔 두 연산자는 왼쪽 연산자의 rbp와 오른쪽 연산자의 lbp가 경쟁한다. 이긴 쪽이 피연산자를 가져간다.

flowchart TB
  A["a + b * c"] --> B["+ 의 rbp < * 의 lbp"] --> C["b는 *의 왼쪽 자식으로 끌려간다"] --> D["(+ a (* b c))"]

결합 방향도 바인딩 파워로 정한다. 좌결합(a - b - c = (a - b) - c)이면 rbp를 lbp보다 살짝 크게, 우결합(a ^ b ^ c = a ^ (b ^ c))이면 작게 둔다.

구현

프랫 파서의 중심은 함수 하나다. "현재 최소 바인딩 파워보다 센 연산자가 오는 동안 계속 왼쪽 트리를 키운다."

BP = {'+': (1, 2), '-': (1, 2), '*': (3, 4), '/': (3, 4), '^': (6, 5)}  # (lbp, rbp)
 
def parse_expr(tokens, min_bp=0):
    lhs = tokens.pop(0)                        # 전위 위치: 피연산자(또는 괄호·전위 연산자)
    if lhs == '(':
        lhs = parse_expr(tokens, 0)
        tokens.pop(0)                          # ')'
    while tokens and tokens[0] in BP:
        op = tokens[0]
        lbp, rbp = BP[op]
        if lbp < min_bp:                       # 왼쪽 연산자가 더 세다 → 여기서 멈춤
            break
        tokens.pop(0)
        rhs = parse_expr(tokens, rbp)          # 오른쪽은 rbp 이상인 연산자만 가져간다
        lhs = (op, lhs, rhs)
    return lhs
 
print(parse_expr(list("a+b*c-d")))   # ('-', ('+', 'a', ('*', 'b', 'c')), 'd')
print(parse_expr(list("2^3^2")))     # ('^', '2', ('^', '3', '2'))

토큰마다 한 번씩만 소비하므로 O(n)이다. 전위 연산자(-x), 후위 연산자(x!), 괄호, 함수 호출은 "토큰이 맨 앞에 올 때(nud)"와 "중간에 올 때(led)"의 처리를 토큰별로 등록하는 식으로 늘려 간다.

예: 셸 문법에 적용하기

셸의 연산자도 우선순위로 정리할 수 있다. 낮은 것부터

시작(0) < 논리 &&, || < 파이프 | < 리디렉션 <, <<, >, >> < 괄호(서브셸)

cmd1 && cmd2 | cmd3 || cmd4 → 파이프가 더 세게 당기므로 (cmd1 && (cmd2 | cmd3)) || cmd4. bash에서 &&와 ||는 같은 우선순위의 좌결합이다.
괄호는 안쪽 연산자의 바인딩 파워를 바깥보다 높이는 역할을 한다. cmd1 | (cmd2 && cmd3)에서는 &&가 파이프보다 먼저 묶인다.
입력 리디렉션 < file은 전위 연산자처럼, 출력 리디렉션 cmd > file은 중위 연산자처럼 다룰 수 있다.

셸 문법은 일반 수식과 달리 연산자와 피연산자가 번갈아 나오지 않는 경우가 있다. < infile cat -에서는 infile과 cat -이 연산자 없이 붙어 있다. 그래서 전위 리디렉션 노드를 "연산자, 파일 이름, 뒤따르는 명령"의 세 부분으로 만드는 등 별도 처리가 필요하다. bash는 < infile | cat 처럼 파이프 왼쪽에 명령이 없는 구문도 허용하므로, 이런 경계 사례는 실제 bash 동작과 비교해 정한다.

정리

파싱은 토큰열을 문법에 맞는 트리로 묶는 일이고, 묶는 순서가 곧 의미다.
백트래킹 재귀 하향은 단순하지만 느리고, 플로이드의 연산자 우선순위 파서는 그리디로 O(n)을 얻었다.
프랫 파서는 연산자마다 (lbp, rbp)를 두고 "더 센 연산자가 오는 동안 왼쪽을 키우는" 재귀 함수 하나로 O(n) 파싱을 한다.
우선순위와 결합 방향을 숫자 두 개로 표현하므로 새 연산자를 추가하기 쉽다.

버그 제보