URL: https://kellett.im/a/inverse-parentheses

Title: Inverse parentheses

Inverse parentheses

← 홈페이지

역(逆) 괄호 2025-12-20

많은 프로그래밍 언어에서 괄호를 써서 피연산자를 묶을 수는 있는데, 그 반대로 묶임을 풀 수 있게 해 주는 언어는 없다는 걸 알아차린 적이 있나요? 없다고요? 그럼 이게 흔히 떠올릴 법한 정상적인 생각이라고 치고, 우리가 뭘 할 수 있는지 한번 봅시다.

괄호를 이용한 그룹핑(묶기)은 언어 문법에 추가하기가 비교적 쉽습니다. 37 같은 원자적(atomic) 요소를 받아들이는 규칙이 여는 괄호도 받아들이도록만 하면 되거든요.1 그러면 그 시점에서 재귀적으로 전체 표현식을 파싱한 뒤, 닫는 괄호를 소비하면 됩니다.

python
def parse_atom(lex):
    r = next(lex)
    if r[0] == 'integer':
        return int(r[1])
    elif r[0] == '(':
        expr = parse_expr(lex)
        s = next(lex)
        if s[0] != ')':
            raise ParseError("missing close paren")
        return expr
    else:
        raise ParseError(f"unexpected {r[0]}")

반(反)그룹핑(anti-grouping)은 그렇게 간단하지 않습니다. 파서가 괄호의 구조를 그대로 따라가면 안 되는데, 그렇게 하면 표현식의 구조를 따라가게 되기 때문입니다. 핵심은, 이 둘이 서로 다르다는 점이거든요.

이걸 순수한(pure) 파서만으로 구현할 수 있는지는 잘 모르겠습니다. 하지만 순수성은 어차피 과대평가된 가치죠. 그래서 저는 이상한 그룹핑 체계를 가진 다른 언어에서 영감을 얻기로 했습니다.

Python¶

파이썬 문법에 중괄호가 있다는 사실을 알고 있었나요? 다만 직접 입력하지 않을 뿐입니다. 토크나이저(tokeniser)3가 들여쓰기 수준을 추적해서, 수준이 바뀔 때 특수 토큰을 삽입합니다. 파서 자체는 공백 개수를 세는 것에 신경 쓸 필요가 없습니다. 그저 INDENT와 DEDENT4로 둘러싸인 문장 블록을 보기만 하면 되고, 이건 파싱하기가 쉽습니다.

재미있게도 파이썬의 토크나이저는 지금이 괄호로 둘러싸인 표현식 내부인지도 알고 있습니다. 괄호 안에서의 들여쓰기는 중요하지 않은데, 이는 괄호 중첩 깊이를 추적하고 그 값이 0이 아닌 동안에는 INDENT와 DEDENT를 억제하는 방식으로 구현되어 있습니다.

그렇다면 같은 요령을 써보면 어떨까요? 파서에서 어떻게든 처리하려고 애쓰기보다, 토크나이저가 중첩 깊이를 추적하면서 각 토큰에 대해 “친화도(friendliness)” 점수를 내보내게 하는 겁니다. 그러면 우리는 단지 친화도가 낮은 것부터 높은 것 순(즉, 친화도 오름차순)으로 연산자를 파싱하면 됩니다.

이 모델에서 1 + (2 * 3)는 아래와 같은 토큰 스트림을 만들어 냅니다:

1
+ (0)
(
2
* (-1)
3
)

괄호는 토큰 스트림 안에 그대로 남겨 두되, 파서가 괄호에 대해 해야 할 일은 “잘못된 위치에서 발견되면 문법 오류를 낸다” 정도뿐입니다. 그룹핑은 토큰 스트림 안에 내장된 우선순위 레벨이 전부 처리합니다.5

무한하지는 않은 등반¶

토크나이저 해킹으로 파싱 문제는 해결되지만, 다른 문제가 생깁니다. 이제 우리 언어에는 우선순위 레벨이 무한히 많아졌습니다. 손으로 짠 재귀 하강 파서로 이걸 처리해 볼 마음은 없지만, 교과서 좀 뒤적여 보니 우리가 원하는 건 우선순위 등반(precendence climbing) 파서인 듯합니다. 이 방식은 만나는 순서대로 연산자를 처리하니, 가능한 우선순위가 무한히 많더라도 크게 방해가 되지 않습니다.

저는 이걸 대충 해킹해서 붙여 봤고, 결과는 그럴듯하게(?) 어이없습니다:

> (1 + 2) * 3
1 + 2 * 3
> 1 + (2 * 3)
(1 + 2) * 3

제가 도달한 구현에서 특히 마음에 드는 점은, 친화도를 낮추는 대신 높이는 방식으로 바꾸면 겉보기에는 평범한6 파서가 된다는 것입니다. 또한 이건 다른 수상한 문법 혁신을 위한 좋은 발판이 되기도 합니다. 예를 들면 괄호가 아예 없는 언어를 만들고, 공백으로 결합을 약화시키는 방식 같은 것 말이죠.

향후 과제¶

오늘 우리는 많은 것을 이뤘지만,7 동시에 중요한 새 질문들도 던져 버렸습니다. 예컨대 더 복잡한 경우에도 항상 표현식을 이중으로 괄호 쳐야 할까요?

> ((1 * 2)) + (3 * 4)
1 * ((2 + 3) * 4)

그리고 평범한 프린터(printer)와 연결했을 때, 결과가 ‘자기 자신으로 되돌아오는(involution)’ 반그룹핑 파서를 만드는 것이 가능할까요?

이런 주제들은 더 깊은 연구를 위한 유망한 길처럼 보이고, 누군가가 이 일을 맡아 준다면 소식을 듣고 싶습니다.

---

1. “parentheses”(둥근 괄호를 의미)가 만족스러운2 단수형을 갖고 있지 않다는 점이 저만 거슬리나요?↩

2. 제게 “parenthesis”는 괄호 한 개라기보다 괄호 한 쌍, 그리고 어쩌면 그 괄호가 둘러싼 텍스트까지 포함하는 말처럼 들립니다.↩

3. lexer라고도 하고, 가끔은 scanner라고도 합니다. 저는 “tokeniser”가 실제 단어에 가장 가까운 느낌이라서 이 표현을 계속 쓰겠습니다.↩

4. 안타깝게도 이건 철자(spelling)가 아니라 내부 이름이라서, 이것들로 신나는 원라이너를 작성하는 건 불가능합니다.↩

5. 이 글에서는 단순화를 위해 연산자 우선순위 규칙(order of operations)을 무시했지만, 제 구현은 이를 처리합니다. 연산자는 테이블에서 조회되고, “자연(natural)” 우선순위가 친화도와 짝지어집니다. 따라서 예시의 +와 * 우선순위는 실제로 각각 (0,0)과 (-1,1)이 됩니다.↩

6. 겉보기로는.↩

7. 사실은 2024년 초였는데, 오늘에서야 정리해서 쓰게 됐습니다.↩

↑ 맨 위로