문맥 자유 문법과 파싱

괄호 안에 괄호, 식 안에 식처럼 끝없이 중첩되는 구조를 정의하는 문맥 자유 문법을 배워요. 규칙 두 줄로 짝 맞는 괄호를 모두 만들어 보고, 문법 하나가 곱셈을 먼저 하는 우선순위와 왼쪽부터 묶는 결합 방향을 정하는 법, 모호한 문법 때문에 같은 식이 14가지 나무와 10가지 값으로 갈리는 모습을 확인해요. 정규 표현식으로 토큰을 자르고 재귀 하강 파서로 문법 나무를 만들어 계산한 뒤, 파이썬이 만든 나무와 똑같은지 비교하고, 촘스키 계층으로 문법의 한계까지 짚어요.

고급강의 3 / 5약 14분

지난 강의에서 유한 오토마타는 괄호의 짝조차 맞추지 못했어요. 그런데 프로그래밍 언어, JSON, HTML, 수식은 모두 괄호 안에 괄호, 식 안에 식이 끝없이 들어가요. 이런 구조를 정의하는 도구가 문맥 자유 문법이고, 문법에 따라 글을 읽어 나무 구조로 바꾸는 일이 파싱이에요. 파이썬이 코드를 실행하기 전에, 브라우저가 HTML을 그리기 전에, 이 가이드북이 마크다운을 웹 페이지로 바꾸기 전에 모두 파싱을 해요.

문법: 문장을 만드는 규칙

문맥 자유 문법은 "무엇은 무엇으로 바꿀 수 있다"는 규칙들의 모음이에요. 짝이 맞는 괄호 문자열은 규칙 두 줄로 정의돼요.

S → ( S ) S
S → (빈 문자열)

S에서 시작해서 규칙대로 S를 계속 바꿔 나가다가, S가 하나도 남지 않으면 문장이 완성돼요. S처럼 더 바꿀 수 있는 기호를 비단말 기호, 괄호처럼 실제 글자로 남는 기호를 단말 기호라고 해요. 첫 규칙은 "여는 괄호가 있으면 그와 짝인 닫는 괄호가 있고, 그 안과 뒤에도 각각 짝이 맞는 문자열이 온다"는 뜻이에요. 규칙의 왼쪽이 기호 하나뿐이라 그 기호가 어디에 있든, 즉 주변 문맥과 상관없이 같은 규칙으로 바꿀 수 있어서 "문맥 자유"라고 불러요. 이 규칙으로 만들 수 있는 문자열을 모두 만들어 볼게요.

from functools import cache

@cache
def balanced(n):                                     # 규칙 S → ( S ) S | 빈 문자열 로 만드는 괄호 n쌍짜리 문자열
    if n == 0:
        return ("",)
    result = []
    for k in range(n):                               # 첫 괄호 안에 k쌍, 그 뒤에 나머지 n - 1 - k쌍
        for inside in balanced(k):
            for rest in balanced(n - 1 - k):
                result.append("(" + inside + ")" + rest)
    return tuple(result)

print("3쌍으로 만들 수 있는 것:", " ".join(balanced(3)))
print("괄호 쌍 수별 개수:", [len(balanced(n)) for n in range(1, 8)])
3쌍으로 만들 수 있는 것: ()()() ()(()) (())() (()()) ((()))
괄호 쌍 수별 개수: [1, 2, 5, 14, 42, 132, 429]

괄호 3쌍으로는 다섯 가지가 나오고, 쌍 수가 늘면 1, 2, 5, 14, 42로 늘어나요. 이 수열을 카탈랑 수라고 하는데, 잠시 뒤에 또 나와요. 오토마타는 이 언어를 인식하지 못했지만 문법은 두 줄로 정의했어요. 비결은 규칙 안에 S가 다시 들어가는 재귀예요. 바깥 괄호 안에 짝이 맞는 괄호 문자열이 통째로 다시 들어가요.

문법으로 계산 순서 정하기

사칙연산 식의 문법은 이렇게 쓸 수 있어요. 따옴표 안은 실제 글자, *는 0번 이상 반복, |는 "또는"이에요.

expr   → term (('+' | '-') term)*
term   → factor (('*' | '/') factor)*
factor → 숫자 | '(' expr ')' | '-' factor

이 세 줄에 계산 규칙이 다 들어 있어요.

  • 우선순위: 식(expr)은 항(term)을 더하고 빼서 만들고, 항은 인수(factor)를 곱하고 나눠서 만들어요. 그래서 2 + 3 * 4에서는 3 * 4가 먼저 항 하나로 묶여요. 곱셈이 덧셈보다 아래층에 있으니 먼저 계산돼요.
  • 괄호: 인수 자리에 괄호로 감싼 식 전체가 다시 들어올 수 있어요. 여기서도 재귀가 중첩을 만들어요.
  • 결합 방향: 같은 층의 연산자는 왼쪽부터 차례로 묶어서, 1 - 2 - 3은 (1 - 2) - 3이에요.

문법에 따라 글을 읽으면 문법 나무(파스 트리)가 나와요. 나무의 위쪽일수록 나중에, 아래쪽일수록 먼저 계산해요. 2 + 3 * 4라면 꼭대기에 +가 있고, 그 오른쪽 가지에 3 * 4가 매달려요.

모호한 문법은 답을 여러 개 낸다

문법을 더 짧게 쓰고 싶어서 이렇게 쓰면 어떨까요?

E → E '+' E | E '-' E | E '*' E | 숫자

이 문법도 같은 식들을 만들어요. 그런데 한 식에 나무가 여러 개 생길 수 있어요. 이런 문법을 모호하다고 해요. 만들 수 있는 나무와 그 값을 모두 구해 볼게요.

import operator

OPS = {"+": operator.add, "-": operator.sub, "*": operator.mul, "/": operator.truediv}

def all_values(tokens):                              # 모호한 규칙 E → E 연산자 E | 숫자 로 만들 수 있는 모든 나무의 값
    @cache
    def go(i, j):                                    # tokens[i:j] 구간으로 만들 수 있는 나무들의 값
        if j - i == 1:
            return (tokens[i],)
        values = []
        for k in range(i + 1, j, 2):                 # k번째 연산자를 나무 꼭대기(가장 나중에 계산)에 두면
            for left in go(i, k):
                for right in go(k + 1, j):
                    values.append(OPS[tokens[k]](left, right))
        return tuple(values)
    return go(0, len(tokens))

for text in ["2 + 3 * 4", "1 - 2 - 3", "1 + 2 * 3 - 4 * 5"]:
    tokens = [int(t) if t.isdigit() else t for t in text.split()]
    values = all_values(tokens)
    print(f"{text}: 나무 {len(values)}가지, 나올 수 있는 값 {sorted(set(values))}")
2 + 3 * 4: 나무 2가지, 나올 수 있는 값 [14, 20]
1 - 2 - 3: 나무 2가지, 나올 수 있는 값 [-4, 2]
1 + 2 * 3 - 4 * 5: 나무 14가지, 나올 수 있는 값 [-51, -33, -15, -13, -11, -9, -5, 11, 15, 25]

2 + 3 * 4는 덧셈을 먼저 하는 나무(20)와 곱셈을 먼저 하는 나무(14) 두 가지가 생겨요. 1 - 2 - 3도 어느 쪽부터 묶느냐에 따라 -4와 2로 갈리고요. 연산자가 4개인 식은 나무가 14가지, 값이 10가지예요. 연산자 n개짜리 식의 나무 수도 카탈랑 수라서 괄호 문자열을 셀 때와 같은 수가 나왔어요. 우리가 기대하는 답은 -13 하나뿐인데요. 그래서 프로그래밍 언어의 문법은 앞의 세 줄처럼 우선순위와 결합 방향을 문법 안에 넣거나, 따로 규칙을 정해서 모호함을 없애요.

1단계: 토큰으로 자르기

파서는 보통 두 단계로 일해요. 먼저 글자들을 숫자, 연산자, 이름 같은 토큰으로 자르고(어휘 분석), 그다음 토큰의 나열을 문법에 맞춰 나무로 만들어요(구문 분석). 토큰은 중첩이 없으니 지난 강의의 정규 표현식으로 충분해요.

import re

TOKEN = re.compile(r"(?P<num>\d+(?:\.\d+)?)|(?P<op>[-+*/()])")

def tokenize(text):
    tokens, pos = [], 0
    while pos < len(text):
        if text[pos].isspace():                      # 빈칸은 건너뛰어요
            pos += 1
            continue
        m = TOKEN.match(text, pos)
        if not m:
            raise SyntaxError(f"{pos + 1}번째 글자 {text[pos]!r}는 쓸 수 없어요")
        if m["num"]:
            num = m["num"]
            tokens.append(("NUM", float(num) if "." in num else int(num)))
        else:
            tokens.append(("OP", m["op"]))
        pos = m.end()
    return tokens

print(tokenize("12 * (3.5 + 4)"))
[('NUM', 12), ('OP', '*'), ('OP', '('), ('NUM', 3.5), ('OP', '+'), ('NUM', 4), ('OP', ')')]

"3.5"는 숫자 토큰 하나가 되고 빈칸은 사라졌어요. 이제 파서는 글자가 아니라 토큰만 보면 돼요.

2단계: 재귀 하강 파서

문법을 코드로 옮기는 가장 직관적인 방법이 재귀 하강 파서예요. 문법 규칙 하나를 함수 하나로 만들고, 규칙 안에 다른 기호가 나오면 그 함수를 불러요. factor 안에 괄호가 나오면 다시 expr을 부르는 재귀가 중첩을 처리해요.

class Parser:
    def __init__(self, text):
        self.tokens, self.i = tokenize(text), 0

    def peek(self):
        return self.tokens[self.i] if self.i < len(self.tokens) else ("END", None)

    def take(self):
        token = self.peek()
        self.i += 1
        return token

    def parse(self):
        tree = self.expr()
        if self.peek()[0] != "END":
            raise SyntaxError(f"{self.i + 1}번째 토큰 {self.peek()[1]!r}가 남았어요")
        return tree

    def expr(self):                                  # expr → term (('+' | '-') term)*
        tree = self.term()
        while self.peek() in (("OP", "+"), ("OP", "-")):
            op = self.take()[1]
            tree = (op, tree, self.term())           # 왼쪽부터 묶여요: 1 - 2 - 3 = (1 - 2) - 3
        return tree

    def term(self):                                  # term → factor (('*' | '/') factor)*
        tree = self.factor()
        while self.peek() in (("OP", "*"), ("OP", "/")):
            op = self.take()[1]
            tree = (op, tree, self.factor())
        return tree

    def factor(self):                                # factor → 숫자 | '(' expr ')' | '-' factor
        kind, value = self.take()
        if kind == "NUM":
            return value
        if value == "(":
            tree = self.expr()
            if self.take() != ("OP", ")"):
                raise SyntaxError("닫는 괄호가 없어요")
            return tree
        if value == "-":
            return ("neg", self.factor())
        raise SyntaxError(f"{self.i}번째 토큰 {value!r} 자리에는 숫자나 여는 괄호가 와야 해요")

def evaluate(tree):                                  # 나무를 아래에서부터 계산해요(후위 순회)
    if not isinstance(tree, tuple):
        return tree
    if tree[0] == "neg":
        return -evaluate(tree[1])
    op, left, right = tree
    return OPS[op](evaluate(left), evaluate(right))

for text in ["2 + 3 * 4", "(2 + 3) * 4", "1 - 2 - 3", "-(4 - 6) * 2.5"]:
    tree = Parser(text).parse()
    print(f"{text}  →  {tree}  →  {evaluate(tree):g}")

for bad in ["2 + * 3", "(1 + 2", "3 4", "2 $ 3"]:
    try:
        Parser(bad).parse()
    except SyntaxError as e:
        print(f"{bad!r}: {e}")
2 + 3 * 4  →  ('+', 2, ('*', 3, 4))  →  14
(2 + 3) * 4  →  ('*', ('+', 2, 3), 4)  →  20
1 - 2 - 3  →  ('-', ('-', 1, 2), 3)  →  -4
-(4 - 6) * 2.5  →  ('*', ('neg', ('-', 4, 6)), 2.5)  →  5
'2 + * 3': 3번째 토큰 '*' 자리에는 숫자나 여는 괄호가 와야 해요
'(1 + 2': 닫는 괄호가 없어요
'3 4': 2번째 토큰 4가 남았어요
'2 $ 3': 3번째 글자 '$'는 쓸 수 없어요
  • 2 + 3 * 4의 나무는 꼭대기에 +가 있고 오른쪽 가지에 3 * 4가 있어요. 우선순위가 문법대로 들어갔어요. 괄호를 치면 꼭대기가 *로 바뀌고요.
  • 1 - 2 - 3은 왼쪽부터 묶여 -4가 됐어요. expr의 반복문이 지금까지 만든 나무를 왼쪽 가지로 삼아 새 나무를 만들기 때문이에요.
  • evaluate는 알고리즘 트랙에서 본 후위 순회예요. 자식들을 먼저 계산해야 부모를 계산할 수 있으니까요.
  • 잘못된 식에는 어디서 무엇이 기대와 달랐는지 알려 줘요. 파이썬이 SyntaxError에서 위치를 짚어 주는 것도 이런 원리예요.

이 파서는 토큰을 한 번씩만 보고 되돌아가지 않아서, 입력 길이에 비례하는 시간에 끝나요. 문법 규칙을 그대로 코드로 옮겼을 뿐인데 계산기가 생겼어요.

파이썬도 같은 나무를 만들어요

파이썬은 코드를 실행하기 전에 문법 나무를 만들고, 표준 라이브러리의 ast 모듈로 그 나무를 직접 볼 수 있어요. 우리 파서가 만든 나무와 비교해 볼게요.

import ast

def shape(node):                                     # 파이썬이 만든 문법 나무를 우리 나무 모양으로 옮겨요
    if isinstance(node, ast.Expression):
        return shape(node.body)
    if isinstance(node, ast.Constant):
        return node.value
    if isinstance(node, ast.UnaryOp) and isinstance(node.op, ast.USub):
        return ("neg", shape(node.operand))
    if isinstance(node, ast.BinOp):
        op = {ast.Add: "+", ast.Sub: "-", ast.Mult: "*", ast.Div: "/"}[type(node.op)]
        return (op, shape(node.left), shape(node.right))
    raise ValueError(f"모르는 모양: {type(node).__name__}")

for text in ["2 + 3 * 4", "1 - 2 - 3", "-(4 - 6) * 2.5", "(1 + 2) * (3 - 4) / 5"]:
    same = shape(ast.parse(text, mode="eval")) == Parser(text).parse()
    print(f"{text}: 파이썬이 만든 나무와 같나요? {same}")
2 + 3 * 4: 파이썬이 만든 나무와 같나요? True
1 - 2 - 3: 파이썬이 만든 나무와 같나요? True
-(4 - 6) * 2.5: 파이썬이 만든 나무와 같나요? True
(1 + 2) * (3 - 4) / 5: 파이썬이 만든 나무와 같나요? True

네 식 모두 파이썬과 같은 모양의 나무가 나왔어요. 파이썬의 실제 문법은 훨씬 크지만 원리는 같아요. 코드 포매터와 린터는 이 나무를 읽어서 코드를 검사하고 고치고, pytest는 assert 문의 나무를 들여다보고 실패했을 때 값을 자세히 보여 줘요. 파이썬은 3.9부터 PEG라는 방식의 파서를 쓰고, 많은 언어가 문법 파일에서 파서를 자동으로 만들어 주는 도구(ANTLR, yacc 등)를 써요. 이 가이드북도 마크다운을 문법에 따라 나무로 읽은 뒤 웹 페이지로 바꿔요.

문법의 계층과 한계

언어학자 노엄 촘스키는 문법을 표현력에 따라 층으로 나눴어요. 층마다 그 언어를 인식하는 기계가 짝지어져요.

언어인식하는 기계예
정규 언어유한 오토마타토큰, 우편번호, 정규 표현식
문맥 자유 언어푸시다운 오토마타(유한 오토마타 + 스택)짝 맞는 괄호, 수식, 프로그래밍 언어의 구문
문맥 의존 언어선형 한정 오토마타a, b, c를 똑같이 n개씩 쓴 문자열
재귀 열거 가능 언어튜링 기계프로그램이 "예"를 확인할 수 있는 모든 것(다음 강의)

아래층 언어는 모두 위층에도 들어가요. 문맥 자유 언어를 인식하는 기계가 푸시다운 오토마타, 즉 유한 오토마타에 스택 하나를 더한 기계라는 점이 중요해요. 괄호 짝 맞추기에 스택이 필요했던 이유가 여기서 정확히 드러나요.

문맥 자유 문법에도 한계가 있어요. a, b, c를 똑같이 n개씩 쓴 문자열은 문맥 자유 문법으로 만들 수 없어요. 스택 하나로는 a의 개수를 b와 맞춰 보는 동안 지워 버려서, c와 다시 맞춰 볼 수 없거든요. 프로그래밍 언어에서 "변수는 선언한 뒤에 써야 한다"나 "함수를 부를 때 인자 수가 맞아야 한다" 같은 규칙도 문법만으로는 다루기 어려워요. 그래서 컴파일러는 문법 나무를 만든 뒤 이름과 타입을 따로 검사하는 단계를 둬요. 이건 컴퓨터 과학 심화 트랙의 컴파일러 강의에서 이어져요.

실습

  1. balanced를 고쳐서 소괄호와 대괄호를 함께 쓰는 짝 맞는 문자열을 만들어 보세요. 2쌍이면 몇 가지인가요?
  2. 문법에 거듭제곱 ^를 더해 보세요. 곱셈보다 우선순위가 높고, 2 ^ 3 ^ 2가 2 ^ 9가 되도록 오른쪽부터 묶여야 해요. 어떤 규칙과 함수를 고쳐야 할까요?
  3. tokenize가 x, price 같은 이름도 토큰으로 자르게 하고, evaluate가 변수 값이 담긴 딕셔너리를 받아 계산하게 바꿔 보세요.
  4. all_values로 "1 - 2 - 3 - 4"의 나무 수와 값을 구해 보세요. 왼쪽부터 묶은 값은 그중 무엇인가요?
  5. ast.dump(ast.parse("x = 1 + 2"))를 출력해서 대입문의 나무가 어떻게 생겼는지 살펴보세요.

자주 하는 오해

  • 정규 표현식을 잘 짜면 무엇이든 파싱할 수 있다. 중첩 구조는 문법과 파서가 필요해요. JSON, HTML, 코드에는 전용 파서를 써요.
  • 같은 문자열들을 만들면 같은 문법이다. 만드는 문자열이 같아도 모호한 문법은 나무가 여러 개라 뜻이 갈려요.
  • 우선순위는 계산기 어딘가에 따로 적힌 표다. 문법의 층 구조 자체로 우선순위를 나타낼 수 있어요.
  • 문법에 맞으면 올바른 프로그램이다. 문법에 맞아도 선언하지 않은 변수나 맞지 않는 타입처럼 문법 밖의 규칙을 어길 수 있어요.
  • 파싱은 컴파일러를 만드는 사람만 쓴다. 설정 파일, 검색어, 수식, 마크다운, 로그처럼 구조가 있는 글을 읽는 곳마다 파싱이 있어요.

점검 문제

  1. 문맥 자유 문법의 규칙은 어떻게 생겼고, 왜 "문맥 자유"라고 부르나요?
  2. 규칙 두 줄(S → ( S ) S, S → 빈 문자열)로 짝 맞는 괄호를 모두 만들 수 있는 이유는?
  3. 사칙연산 문법에서 곱셈이 덧셈보다 먼저 계산되도록 만드는 방법은?
  4. 모호한 문법이란 무엇이고, 왜 문제가 되나요?
  5. 파서가 어휘 분석과 구문 분석으로 일을 나누는 이유는?
  6. 재귀 하강 파서는 문법을 어떻게 코드로 옮기나요?
  7. 1 - 2 - 3을 왼쪽부터 묶도록 파서를 만드는 방법은?
  8. 문맥 자유 언어를 인식하는 기계는 무엇이고, 유한 오토마타와 무엇이 다른가요?

정답

  1. 왼쪽에 비단말 기호 하나, 오른쪽에 그것을 바꿀 기호들의 나열이 오는 규칙이에요. 그 기호가 어디에 있든 주변 문맥과 상관없이 같은 규칙으로 바꿀 수 있어서 문맥 자유라고 불러요.
  2. 첫 규칙의 괄호 안과 뒤에 다시 S가 들어가는 재귀 덕분에, 짝 맞는 괄호 문자열을 통째로 다른 괄호 안에 넣거나 뒤에 이어 붙일 수 있기 때문이에요. 빈 문자열 규칙이 재귀를 끝내요.
  3. 문법을 층으로 나눠서, 식은 항을 더하고 빼서 만들고 항은 인수를 곱하고 나눠서 만들게 해요. 곱셈이 아래층에 있으니 먼저 한 덩어리로 묶여요.
  4. 한 문장에 문법 나무가 여러 개 생기는 문법이에요. 나무마다 계산 순서가 달라서 같은 식이 여러 값을 가질 수 있어요.
  5. 토큰은 중첩이 없어서 정규 표현식으로 빠르게 자를 수 있고, 구문 분석은 글자 대신 토큰만 보면 되니 문법이 단순해지기 때문이에요.
  6. 문법 규칙 하나를 함수 하나로 만들고, 규칙 안에 다른 기호가 나오면 그 함수를 불러요. 규칙의 재귀가 함수의 재귀가 돼서 중첩을 처리해요.
  7. 반복문으로 같은 층의 연산자를 하나씩 읽으면서, 지금까지 만든 나무를 왼쪽 가지로 삼아 새 나무를 만들어요.
  8. 푸시다운 오토마타예요. 유한 오토마타에 끝없이 쌓을 수 있는 스택을 하나 더한 기계라, 아직 짝을 찾지 못한 여는 괄호 같은 것들을 기억할 수 있어요.

다음 강의

유한 오토마타에 스택을 더하니 괄호를 셀 수 있었어요. 그럼 기억을 더 자유롭게 하면 어디까지 갈 수 있을까요? 다음 강의에서는 마음대로 읽고 쓸 수 있는 끝없는 테이프를 가진 튜링 기계를 만나요. 지금의 모든 컴퓨터가 할 수 있는 일을 튜링 기계도 할 수 있다는 것, 그리고 그런 기계로도 절대 풀 수 없는 문제가 있다는 놀라운 사실을 직접 확인해 봐요.