파서

파서는 글자로 적힌 입력을 읽어 프로그램이 다룰 수 있는 구조로 바꿉니다. 사람이 쓴 코드나 설정 파일은 파서를 거쳐야 프로그램이 쓸 수 있는 값이 됩니다. 규칙을 어긴 입력은 파서를 통과하지 못합니다. 파서는 그 입력에서 틀린 곳을 알려 줍니다.

상세

국어 시간에 문장 하나를 받으면 주어와 서술어를 찾아 밑줄을 긋습니다. 낱말을 하나씩 읽는 것만으로는 뜻이 잡히지 않습니다. 어느 낱말이 어느 낱말에 걸리는지를 가려야 문장이 읽힙니다.

파서는 입력을 정해진 규칙에 비춰 읽습니다. 그리고 입력이 어떤 부분으로 이루어졌는지를 밝혀 값으로 내놓습니다. 요청 본문으로 {"id": 7} 이라는 글자가 왔다고 해 봅시다. 파서를 지나면 이 글자는 키가 id 이고 값이 숫자 7 인 항목 하나를 가진 맵이 됩니다.

이 절은 먼저 파서가 어디서 쓰이고 왜 따로 두는지를 봅니다. 그다음 계산식 1 + 2 * 3 한 줄을 들고 글자가 트리가 되기까지를 따라갑니다. 끝으로 결과를 넘기는 방식과 틀린 입력을 다루는 법을 봅니다.

파서를 품은 프로그램

파서는 글자를 받아들이는 프로그램이라면 거의 어디에나 들어 있습니다. 읽는 입력은 달라도 하는 일은 같습니다.

실무에서는 날짜 문자열이나 로그 한 줄처럼 규칙이 단순한 입력을 읽는 코드도 파서라고 부릅니다.

파서를 따로 두는 까닭

파서가 없으면 글자를 받은 코드가 읽으면서 바로 일을 합니다. 쉼표를 만나면 값을 끊고, 따옴표를 만나면 문자열이 시작된 것으로 봅니다. 이러면 읽는 규칙이 코드 곳곳에 흩어집니다. 입력이 중간에서 틀렸다는 것도 일을 절반쯤 해 놓은 뒤에야 알게 됩니다.

파서를 두면 입력을 읽는 코드와, 읽은 값으로 일하는 코드가 갈립니다. 파서가 입력 전체를 규칙에 비춰 보고, 통과한 것만 구조로 넘깁니다. 뒤의 코드는 쉼표나 따옴표를 볼 일 없이 키와 값만 다룹니다.

규칙이 단순해 보이는 입력에서 이 차이가 드러납니다. 값을 쉼표로 나눠 적는 CSV(Comma-Separated Values, 쉼표로 나눈 값) 한 줄을 봅시다. 값 안에 쉼표가 들어가면 그 값을 따옴표로 감쌉니다.

import csv

s = 'a,"b,c",d'
s.split(",")  # ['a', '"b', 'c"', 'd']
next(csv.reader([s]))  # ['a', 'b,c', 'd']

split 은 쉼표만 보고 자르므로 따옴표 안의 쉼표에서도 잘라 조각이 넷이 됩니다. CSV 의 규칙을 아는 파서는 따옴표 안을 한 값으로 읽어 셋을 돌려줍니다.

글자에서 트리로

파서가 내놓는 구조는 대개 트리입니다. 입력 안에서 무엇이 무엇을 품는지를 트리의 부모와 자식으로 적습니다.

계산식 1 + 2 * 3 을 보겠습니다. 글자를 늘어놓기만 해서는 어느 연산을 먼저 할지가 드러나지 않습니다. 파서는 곱셈이 덧셈보다 먼저 묶인다는 규칙에 따라 아래 트리를 세웁니다.

flowchart TD
    P["+"] --> A["1"]
    P --> M["*"]
    M --> B["2"]
    M --> C["3"]

2 * 3 이 한 덩어리로 묶여 + 의 오른쪽 자식이 됐습니다. 이 트리를 아래에서부터 계산하면 7 이 나옵니다. 어느 연산이 먼저 묶이는지를 연산자 우선순위라고 부릅니다. 파서는 그것을 트리 모양으로 굳혀 둡니다.

렉서와 토큰

파서는 대개 글자를 곧바로 읽지 않습니다. 앞 단계에서 글자를 뜻이 있는 가장 작은 낱말로 먼저 쪼갭니다. 이 낱말 하나가 토큰입니다. 글자를 토큰으로 쪼개는 쪽은 렉서입니다.

1 + 2 * 3 은 렉서를 지나 토큰 다섯 개가 됩니다. 사이의 빈칸은 이 단계에서 버려집니다. 파서는 이 토큰 열을 받아 트리를 세웁니다.

flowchart TD
    A["글자 · 1 + 2 * 3"] --> L["렉서"]
    L --> T["토큰 열 · 「1」「+」「2」「*」「3」"]
    T --> P["파서"]
    P --> R["트리"]

쪼개는 일을 앞으로 떼어 내면 파서는 빈칸이나 줄바꿈을 신경 쓰지 않아도 됩니다. 숫자가 몇 자리인지도 렉서가 이미 가려 두었으므로 파서는 「수 하나」로 받습니다.

파서가 따르는 문법

파서가 입력을 비춰 보는 규칙을 문법이라고 부릅니다. 문법은 어떤 토큰 다음에 무엇이 올 수 있는지를 적은 규칙 묶음입니다. 문법이 따로 적혀 있어야 파서가 맞는 입력과 틀린 입력을 가를 수 있습니다.

문법 규칙은 큰 것을 작은 것으로 풀어 적는 꼴입니다. 계산식이라면 이렇게 적을 수 있습니다.

식 → 항, 그 뒤에 「+ 항」이 0번 이상
항 → 수, 그 뒤에 「* 수」가 0번 이상

첫 줄은 식이 항들을 덧셈으로 이은 것이라는 뜻입니다. 둘째 줄은 항이 수들을 곱셈으로 이은 것이라는 뜻입니다.

이 규칙을 1 + 2 * 3 에 대 보면 식은 먼저 + 에서 잘려 1 과 2 * 3 두 항이 됩니다. 둘째 항은 다시 * 에서 풀려 수 2 와 3 이 됩니다. 곱셈은 항 안에서만 일어나므로, 2 * 3 은 덧셈에 쓰이기 전에 이미 한 항으로 묶여 있습니다.

괄호를 받으려면 규칙을 하나 더 둡니다. 곱셈으로 이어지는 낱낱의 조각을 인수라고 합니다. 인수분해의 그 인수입니다. 인수에는 수 말고 괄호로 감싼 식도 올 수 있게 적습니다.

식 → 항, 그 뒤에 「+ 항」이 0번 이상
항 → 인수, 그 뒤에 「* 인수」가 0번 이상
인수 → 수, 또는 「( 식 )」

셋째 줄의 인수가 다시 식을 부릅니다. 규칙이 돌고 돌아 자기 자신을 부르므로, 식 안에 식이 몇 겹이든 들어갈 수 있습니다.

이렇게 규칙마다 왼쪽에 이름 하나를 두고 오른쪽으로 풀어 적는 문법을 문맥 자유 문법이라고 합니다. 「문맥 자유」는 그 이름이 앞뒤에 무엇이 붙어 있든 똑같이 풀린다는 뜻입니다. 프로그래밍 언어와 데이터 형식 대부분이 이 꼴로 적힙니다.

괄호의 겹을 세는 스택

이 절은 괄호가 몇 겹이든 짝을 맞춰야 하는 ((1 + 2) * 3) 을 들고, 렉서는 못 읽고 파서는 읽는 까닭을 봅니다. 차이는 읽는 동안 기억해야 할 양에서 납니다.

렉서는 글자를 앞에서부터 읽으며 지금 숫자를 읽는 중인지, 이름을 읽는 중인지만 알면 됩니다. 기억할 것이 정해진 몇 가지뿐입니다. 이렇게 정해진 몇 가지 상태 가운데 하나에 머물다가, 읽은 글자에 따라 다음 상태로 옮겨 가는 장치를 상태 기계라고 부릅니다.

파서는 사정이 다릅니다. ((1 + 2) * 3) 처럼 괄호는 몇 겹이든 들어갈 수 있습니다. 여는 괄호마다 닫는 괄호가 짝을 맞춰야 합니다. 몇 겹이 열려 있는지는 끝이 정해져 있지 않아서, 정해진 개수의 상태로는 셀 수 없습니다.

그래서 파서는 스택을 하나 더 씁니다. 스택은 나중에 넣은 것을 먼저 꺼내는 자료 구조입니다. 여는 괄호를 만나면 스택에 쌓고, 닫는 괄호를 만나면 하나를 뺍니다. 입력이 끝났을 때 스택이 비어 있으면 짝이 맞은 것입니다.

flowchart TD
    A["첫 ( 읽음 · 스택 ("] --> B["둘째 ( 읽음 · 스택 ( ("]
    B --> C["첫 ) 읽음 · 스택 ("]
    C --> D["둘째 ) 읽음 · 빈 스택 → 짝 맞음"]

그림은 괄호 사이의 토큰을 빼고 괄호만 따라갔습니다. 스택의 높이가 곧 지금 열려 있는 괄호의 겹 수입니다.

구문 트리와 추상 구문 트리

이 절은 (1 + 2) * 3 한 식을 두 가지 트리로 그려 봅니다. 두 트리는 괄호 같은 토큰을 남기느냐 버리느냐로 갈립니다.

입력의 토큰을 하나도 빼지 않고 문법 규칙을 따라 세운 트리를 구문 트리라고 부릅니다. 안쪽 마디에는 식·항·인수 같은 규칙 이름이 서고, 잎에는 토큰이 붙습니다. 괄호처럼 묶음을 나타내려고만 있던 토큰도 잎으로 남습니다.

flowchart TD
    E0["식"] --> T0["항"]
    T0 --> F0["인수"]
    T0 --> MUL["*"]
    T0 --> F1["인수"]
    F0 --> LP["("]
    F0 --> E1["식"]
    F0 --> RP[")"]
    F1 --> N3["3"]
    E1 --> T1["항"]
    E1 --> PLUS["+"]
    E1 --> T2["항"]
    T1 --> F2["인수"]
    T2 --> F3["인수"]
    F2 --> N1["1"]
    F3 --> N2["2"]

1 하나에 닿기까지 규칙 이름 마디를 여럿 지납니다. 괄호 잎 둘은 트리 모양이 이미 말해 주는 묶음을 한 번 더 적고 있습니다.

뒤 단계에 필요한 것은 대개 연산과 값뿐입니다. 그래서 규칙 이름과 묶음 표시용 토큰을 걷어 낸 트리를 따로 만듭니다. 이 트리가 추상 구문 트리입니다.

flowchart TD
    MUL["*"] --> PLUS["+"]
    MUL --> N3["3"]
    PLUS --> N1["1"]
    PLUS --> N2["2"]

괄호가 빠졌어도 + 가 * 아래에 달려 있어 「덧셈이 먼저」가 트리 모양으로 남습니다. 앞에서 본 1 + 2 * 3 의 그림도 추상 구문 트리입니다. 구문 트리로 그렸다면 식·항·인수 마디가 그 사이에 더 끼어 있습니다.

결과를 넘기는 두 방식

파서가 결과를 넘기는 방식은 둘로 갈립니다. 하나는 입력을 끝까지 읽어 트리를 다 만든 뒤 한꺼번에 넘기는 방식입니다. 받는 쪽은 트리 어디든 오가며 볼 수 있습니다. 대신 입력이 크면 트리도 그만큼 메모리를 차지합니다.

웹 문서를 적는 HTML(HyperText Markup Language, 하이퍼텍스트 표시 언어)이 이렇게 읽힙니다. 데이터를 태그로 감싸 적는 XML(Extensible Markup Language, 확장 가능 표시 언어)도 마찬가지입니다. 이 두 형식을 읽어 만든 트리를 DOM(Document Object Model, 문서 객체 모델)이라고 부릅니다.

다른 하나는 읽는 대로 사건을 알려 주는 방식입니다. 「여는 태그 <name> 을 만났다」, 「글자를 만났다」, 「닫는 태그를 만났다」를 차례로 받는 쪽에 넘깁니다. 트리는 만들지 않습니다.

이 방식은 메모리를 적게 쓰는 대신 이미 지나간 부분으로 되돌아갈 수 없습니다. XML 에서는 이 방식의 대표를 SAX(Simple API for XML, API 는 Application Programming Interface 의 줄임말)라고 부릅니다.

위에서 내려가는 파서와 아래에서 올라가는 파서

트리를 세우는 순서로도 파서가 갈립니다. 위에서 내려가는 파서는 「이 입력은 식이다」에서 출발해 규칙을 펼치며 토큰까지 내려갑니다. 아래에서 올라가는 파서는 토큰을 모아 작은 묶음을 만듭니다. 그 묶음을 다시 묶어 맨 위까지 올라갑니다.

위에서 내려가는 쪽의 대표가 재귀 하강 파서입니다. 문법 규칙 하나를 함수 하나로 옮깁니다. 규칙이 다른 규칙을 부르면 함수가 다른 함수를 부릅니다. 손으로 짜기 쉬워서 직접 만든 파서는 대개 이 꼴입니다.

함수가 다른 함수를 부를 때마다 호출 스택에 한 칸이 쌓입니다. 호출 스택은 아직 안 끝난 함수 호출을 적어 두는 스택입니다. 괄호 한 겹을 열 때마다 인수의 함수가 식의 함수를 다시 부르므로 한 칸이 더 쌓입니다. 재귀 하강 파서에서는 이 호출 스택이 앞에서 본 괄호 스택 노릇을 합니다.

아래에서 올라가는 쪽은 미리 만든 표를 보며 움직입니다. 지금까지 쌓아 둔 묶음과 다음 토큰을 보고, 더 쌓을지 여기서 묶을지를 적어 둔 표입니다. 문법이 조금만 커져도 따질 경우가 많아져서 이 표는 손으로 채우기 어렵습니다. 그래서 문법을 읽고 파서 코드를 만들어 주는 파서 생성기에 맡기는 것이 보통입니다.

문법을 어긴 입력

파서는 입력이 문법을 어기는 첫 지점에서 멈춥니다. 뒤의 코드는 틀린 입력을 아예 받지 않습니다. 파서를 입력의 첫 관문으로 쓰는 까닭입니다.

데이터를 중괄호와 대괄호로 적는 JSON(JavaScript Object Notation, 자바스크립트 객체 표기법)을 파이썬 표준 파서에 넣어 봅니다.

import json

json.loads('{"id": 7}')  # {'id': 7}
json.loads('{"id": 7')  # JSONDecodeError

첫 줄은 맵을 돌려줍니다. 둘째 줄은 닫는 중괄호가 없어서 오류를 냅니다. 오류에는 대개 몇째 줄 몇째 글자에서 멈췄는지가 함께 실립니다.

컴파일러의 파서는 한 곳이 틀려도 곧바로 그만두지 않는 경우가 많습니다. 틀린 곳을 건너뛰고 다음 문장부터 다시 읽어서, 한 번 돌릴 때 오류를 여럿 보여 줍니다. 이렇게 틀린 곳을 넘어 계속 읽는 일이 오류 복구입니다.

믿을 수 없는 입력

파서는 바깥에서 온 입력을 가장 먼저 만지는 코드입니다. 그래서 공격하는 쪽이 제일 먼저 노리는 코드이기도 합니다.

괄호를 수만 겹 쌓은 입력을 재귀 하강 파서에 넣으면 괄호 한 겹마다 호출 스택이 한 칸씩 쌓여 결국 넘칩니다. 아주 큰 입력을 트리로 한꺼번에 읽으면 메모리가 바닥납니다. 둘 다 서버를 멈추게 하는 서비스 거부 공격의 재료가 됩니다. 그래서 바깥 입력을 읽는 파서에는 중첩 깊이와 입력 크기에 상한을 둡니다.

같은 입력을 두 파서가 다르게 읽는 것도 문제가 됩니다. {"role": "user", "role": "admin"} 처럼 키가 겹친 맵을 받으면 어느 값을 남기는지가 파서마다 다릅니다. 가령 앞단에서 검사하는 파서는 앞의 user 를 남기고, 뒤에서 처리하는 파서는 뒤의 admin 을 남긴다고 해 봅시다. 요청은 user 로 검사를 통과한 뒤 admin 으로 처리됩니다.

파서를 직접 짤 때와 가져다 쓸 때

이 절은 파서가 필요한지, 필요하면 무엇을 쓸지를 차례로 가립니다. 가장 먼저 볼 것은 입력에 겹침이 있는지입니다.

입력에 겹치는 구조가 없고 구분 글자가 값 안에 나올 일이 없다면 문자열을 자르는 것으로 충분합니다. 앞의 CSV 예처럼 값 안에 구분 글자가 들어갈 수 있게 되는 순간부터 파서가 필요해집니다.

형식이 이미 정해진 입력이라면 파서를 새로 짜지 않고 이미 있는 파서를 씁니다. 따옴표, 이스케이프, 문자 인코딩처럼 세세한 규칙이 많아서 손으로 짜면 빠뜨리기 쉽습니다.

파서를 직접 짜는 것은 입력의 문법을 내가 정할 때입니다. 검색창에 status:open author:kim 처럼 넣는 필터 문법이 그렇습니다. 한 가지 일만 하려고 만든 이런 작은 언어를 도메인 특화 언어라고 합니다.

세 갈래를 한 그림에 모으면 이렇습니다.

flowchart TD
    Q1{"겹치는 구조나 값 안의 구분 글자가 있나"}
    Q1 -->|없다| S["문자열 자르기"]
    Q1 -->|있다| Q2{"형식이 이미 정해져 있나"}
    Q2 -->|그렇다| P["이미 있는 파서"]
    Q2 -->|문법을 내가 정한다| D["직접 짜기 · 도메인 특화 언어"]

관련 항목

파서 앞뒤에 서는 처리 단계

파싱 · 어휘 분석 · 렉서 · 토큰 · 구문 분석 · 의미 분석 · 타입 검사 · 코드 생성

파서가 내놓는 자료 구조

트리 · 구문 트리 · 추상 구문 트리 · DOM · 심볼 테이블

파서가 따르는 문법 이론

형식 문법 · 문맥 자유 문법 · 정규 문법 · BNF · 촘스키 위계 · 모호한 문법 · 연산자 우선순위

파서를 떠받치는 계산 모형

상태 기계 · 푸시다운 오토마타 · 정규 표현식 · 스택 · 재귀

파서의 하위 종류

재귀 하강 파서 · LL 파서 · LR 파서 · LALR 파서 · 파서 콤비네이터 · PEG · 스트리밍 파서 · SAX

파서를 만들어 주는 도구

파서 생성기 · yacc · Bison · ANTLR · tree-sitter

파서가 읽는 데이터 형식

JSON · XML · HTML · YAML · CSV · TOML · 포맷

파서를 품고 도는 프로그램

컴파일러 · 인터프리터 · 브라우저 · 데이터베이스 · 정적 분석 · 린터 · 코드 포매터

파서와 반대 방향으로 도는 연산

직렬화 · 마셜링 · 프리티 프린터 · 인코딩

파서와 이름이나 뜻이 헷갈리는 이웃

역직렬화 · 디코딩 · 입력 검증 · 인터프리터 패턴

파서에서 자주 나는 오류·장애

구문 오류 · 오류 복구 · 스택 오버플로 · 서비스 거부 공격 · XXE · Billion Laughs 공격 · 파서 차이 · 퍼징

파서로 입력을 받는 작은 언어

도메인 특화 언어 · 질의 언어 · 템플릿 엔진 · 설정 언어