문맥 자유 문법

문맥 자유 문법은 어떤 글이 올바른 모양인지를 규칙 몇 줄로 정해 줍니다. 큰 덩어리를 작은 조각으로 풀어 적는 규칙을 모아 둔 것입니다. 프로그래밍 언어와 데이터 형식 대부분이 이 방법으로 적힙니다. 파서는 이 규칙에 입력을 비춰 보고 맞는지 가립니다.

상세

국어 시간에 문장을 뜯어 본 적이 있을 겁니다. 문장은 주어부와 서술부로 나뉩니다. 주어부는 다시 꾸미는 말과 명사로 나뉩니다. 이렇게 큰 덩어리를 작은 덩어리로 쪼개 내려가다 보면 낱말 하나하나에 닿습니다.

문맥 자유 문법은 이 쪼개는 방법을 규칙으로 적어 둔 것입니다. 영어로는 context-free grammar, 줄여서 CFG(Context-Free Grammar)라고 부릅니다. 이 규칙들이 정하는 대상을 언어라고 부릅니다. 여기서 언어는 「이 문법에 맞는 글 전부의 모음」을 뜻합니다.

규칙이 따로 적혀 있어야 파서가 맞는 입력과 틀린 입력을 가를 수 있습니다. 사람마다 머릿속으로만 「이런 모양이면 맞다」고 알고 있으면 프로그램 둘이 같은 입력을 두고 다르게 판정합니다.

규칙과 두 종류의 기호

이 절은 덧셈과 곱셈과 괄호가 들어가는 계산식을 들고 규칙 한 줄이 어떻게 생겼는지 봅니다. 여섯 줄이면 계산식 전부를 적을 수 있습니다.

식 → 식 + 항      // 규칙 1
식 → 항           // 규칙 2
항 → 항 * 인수    // 규칙 3
항 → 인수         // 규칙 4
인수 → ( 식 )     // 규칙 5
인수 → 수         // 규칙 6

한 줄이 규칙 하나입니다. 화살표 왼쪽의 이름은 오른쪽 모양으로 풀 수 있다는 뜻입니다. 이런 규칙을 생성 규칙이라고 부릅니다. 같은 이름에 규칙이 둘 있으면 둘 중 아무거나 골라 풀 수 있습니다.

규칙 안의 기호는 두 종류로 갈립니다. 식·항·인수처럼 더 풀 수 있는 이름을 비단말 기호라고 합니다. 입력에 드러나지 않고 모양을 설명하려고만 있는 이름입니다.

+ · * · ( · ) · 수처럼 더는 안 풀리는 기호를 단말 기호라고 합니다. 입력에 글자로 나오는 것들입니다. 여기서 수는 1 이나 42 같은 숫자 토큰 하나를 가리킵니다.

풀기 시작하는 이름도 하나 정해 둡니다. 이것을 시작 기호라고 합니다. 이 문법에서는 식이 시작 기호입니다.

규칙을 따라 풀어 나가는 유도

이 절은 1 + 2 를 들고, 위 규칙들이 이 입력을 어떻게 만들어 내는지 따라갑니다. 시작 기호에서 출발해 이름을 하나씩 바꿔 넣습니다.

식
식 + 항        // 규칙 1
항 + 항        // 규칙 2
인수 + 항      // 규칙 4
1 + 항         // 규칙 6
1 + 인수       // 규칙 4
1 + 2          // 규칙 6

한 줄 내려갈 때마다 비단말 기호 하나를 골라 규칙의 오른쪽으로 바꿉니다. 오른쪽 주석이 그때 쓴 규칙입니다. 마지막 줄에는 단말 기호만 남았습니다. 그 줄이 입력과 같습니다.

이 과정을 유도라고 부릅니다. 시작 기호에서 입력까지 유도가 하나라도 있으면 그 입력은 이 문법의 언어에 속합니다. 어떤 규칙을 어떤 순서로 써도 입력에 닿지 못하면 그 입력은 문법에 어긋난 것입니다.

유도를 그린 구문 트리

이 절은 1 + 2 * 3 의 유도를 트리로 그립니다. 줄줄이 적은 유도보다 트리가 어떤 조각이 먼저 묶였는지를 잘 보여 줍니다.

규칙을 쓸 때마다 왼쪽 이름을 부모로, 오른쪽 기호들을 자식으로 매답니다. 이렇게 얻은 트리를 구문 트리라고 합니다. 뿌리에는 시작 기호가 섭니다. 잎에는 입력의 토큰이 왼쪽부터 차례로 붙습니다.

flowchart TD
    E1["식"] --> E2["식"]
    E1 --> P["+"]
    E1 --> T1["항"]
    E2 --> T2["항"] --> F1["인수"] --> N1["1"]
    T1 --> T3["항"]
    T1 --> M["*"]
    T1 --> F3["인수"] --> N3["3"]
    T3 --> F2["인수"] --> N2["2"]

그림에서 2 * 3 은 오른쪽 항 하나 아래에 통으로 매달려 있습니다. 트리를 두고 값을 계산할 때는 자식의 값부터 구해 부모에서 합칩니다. 그래서 2 * 3 이 먼저 6 이 됩니다. 그 6 이 뿌리에서 1 과 더해집니다.

곱셈을 먼저 하라는 규칙은 따로 적지 않았습니다. 규칙을 식·항·인수 세 계층으로 나눈 것만으로 그 순서가 나옵니다.

「문맥 자유」라는 이름

이 절은 이름에 붙은 「문맥」이 무엇을 가리키는지 봅니다. 답은 규칙의 왼쪽에 있습니다.

앞의 규칙은 모두 왼쪽에 이름이 딱 하나입니다. 그래서 그 이름 앞뒤에 무엇이 붙어 있든 같은 규칙으로 풀 수 있습니다. 여기서 문맥은 그 이름의 앞뒤에 놓인 기호들입니다. 문맥을 보지 않고 푼다고 해서 문맥 자유라는 이름이 붙었습니다.

앞뒤를 따지는 규칙까지 허용하면 문맥 의존 문법이 됩니다. 「앞에 a 가 있을 때만 이 이름을 이렇게 푼다」 같은 규칙입니다. 적을 수 있는 언어는 넓어집니다. 대신 입력이 맞는지 가리는 일이 훨씬 무거워집니다.

문맥을 안 보면 얻는 것이 있습니다. 괄호 안의 식은 괄호 밖에 무엇이 있든 똑같이 풀립니다. 조각을 따로 떼어 풀 수 있으니, 입력을 빠르게 읽는 파서를 만들 수 있습니다.

괄호의 겹과 정규 표현식의 한계

이 절은 ((1 + 2) * 3) 처럼 괄호가 겹겹이 들어가는 입력을 들고, 정규 표현식은 못 하고 문맥 자유 문법은 하는 일을 봅니다. 차이는 읽는 동안 기억할 수 있는 양에서 납니다.

정규 표현식은 유한 상태 기계로 돌아갑니다. 유한 상태 기계는 정해진 개수의 상태 가운데 하나에 머물다가, 읽은 글자에 따라 다음 상태로 옮겨 가는 장치입니다. 기억이라고 할 만한 것은 지금 어느 상태에 있느냐뿐입니다.

괄호가 몇 겹 열렸는지를 기억하려면 겹 수마다 상태가 하나씩 있어야 합니다. 겹 수에는 끝이 없으니 정해진 개수의 상태로는 모자랍니다. 그래서 정규 표현식으로는 「괄호의 짝이 맞는 식 전부」를 적을 수 없습니다.

문맥 자유 문법은 규칙 5 하나로 이 일을 합니다. 인수가 다시 식을 부릅니다. 그 식이 또 인수를 부릅니다. 이렇게 규칙이 돌고 돌아 자기 자신을 부르는 것을 재귀라고 합니다. 재귀 덕분에 괄호가 몇 겹이든 같은 규칙이 되풀이해 받아 줍니다.

문법마다 그 문법에 맞는 입력을 알아보는 기계가 짝으로 있습니다. 정규 표현식의 짝은 앞에서 본 유한 상태 기계입니다. 문맥 자유 문법의 짝은 유한 상태 기계에 저장 공간 하나를 더 붙인 기계입니다.

그 저장 공간은 나중에 넣은 것을 먼저 꺼내는 스택입니다. 여는 괄호를 만나면 하나 쌓습니다. 닫는 괄호를 만나면 하나 꺼냅니다. 쌓는 수에 끝이 없으니 괄호가 몇 겹이든 짝을 맞출 수 있습니다.

유한 상태 기계에 스택을 붙인 이 기계를 푸시다운 오토마타라고 부릅니다. 문맥 자유 문법이 적는 언어는 모두 이 기계가 알아볼 수 있습니다.

문법으로 못 적는 규칙

이 절은 문맥 자유 문법에도 끝이 있다는 것을 변수 선언을 들고 봅니다. 프로그래밍 언어의 규칙 가운데 이 문법으로 적히지 않는 것이 꽤 있습니다.

「변수는 쓰기 전에 선언해야 한다」가 대표입니다. 이 규칙을 지키려면 앞에서 본 이름을 뒤에서 다시 알아봐야 합니다.

괄호 짝과 견주면 차이가 보입니다. 괄호 짝은 여는 것과 닫는 것이 안팎으로 포개지기만 하면 됩니다. 가장 나중에 연 괄호를 가장 먼저 닫으니 스택 하나로 맞출 수 있습니다.

선언 검사는 이름이 글자까지 같은지를 봐야 합니다. 여는 괄호는 모양이 하나뿐입니다. 이름은 개발자가 마음대로 짓습니다.

게다가 이름끼리 엇갈려 놓이기도 합니다. 아래 네 줄이 그렇습니다.

int a;    // a 선언
int b;    // b 선언
a = 1;    // a 사용
b = 2;    // b 사용

스택에 a·b 를 차례로 쌓으면 맨 위의 b 가 먼저 나옵니다. 그런데 먼저 확인할 이름은 a 입니다. 안팎으로 포개지지 않으니 스택으로 짝을 맞추는 방식이 통하지 않습니다. 그래서 이 조건은 문맥을 안 보는 규칙으로 적을 수 없습니다.

이 때문에 컴파일러는 일을 둘로 나눕니다. 먼저 파서가 문맥 자유 문법으로 모양만 확인해 트리를 만듭니다. 선언 여부와 타입이 맞는지는 그 트리를 다시 훑는 의미 분석 단계가 따로 검사합니다.

모호한 문법과 연산자 우선순위

이 절은 규칙을 셋으로 줄인 계산식 문법을 들고, 한 입력이 두 트리로 풀릴 때 무슨 일이 나는지 봅니다.

식 → 식 + 식
식 → 식 * 식
식 → 수

이 문법으로 1 + 2 * 3 을 풀면 트리가 둘 나옵니다. 덧셈을 먼저 묶는 트리와 곱셈을 먼저 묶는 트리입니다. 두 트리를 괄호로 옮겨 적으면 값이 갈립니다.

(1 + 2) * 3    // 9
1 + (2 * 3)    // 7

한 입력에 구문 트리가 둘 이상 나오는 문법을 모호한 문법이라고 합니다. 파서가 어느 트리를 고르느냐에 따라 같은 코드가 다른 값을 내므로, 언어를 정할 때는 이런 문법을 피합니다.

앞 절의 여섯 줄 문법이 식·항·인수 세 계층을 둔 까닭이 여기 있습니다. 곱셈을 항 안에 가둬 두면 곱셈이 늘 덧셈보다 안쪽에서 묶여 트리가 하나로 정해집니다. 연산마다 묶이는 순서를 정한 이 규칙을 연산자 우선순위라고 부릅니다.

문법을 적는 표기 BNF

이 절은 언어 문서에서 문법을 실제로 어떤 꼴로 적는지 봅니다. 화살표 대신 쓰는 표기가 정해져 있습니다.

BNF(Backus-Naur Form, 배커스-나우르 형식)는 문맥 자유 문법을 글자로 적는 표기입니다. 비단말 기호는 꺾쇠로, 단말 기호는 따옴표로 감쌉니다. ::= 은 화살표를 대신합니다. | 는 「또는」입니다.

<식>   ::= <식> "+" <항> | <항>
<항>   ::= <항> "*" <인수> | <인수>
<인수> ::= "(" <식> ")" | 수

위 세 줄은 앞의 여섯 줄 규칙과 같은 문법입니다. 이름이 같은 규칙을 | 로 한 줄에 모았을 뿐입니다. 수만 따옴표 없이 적었습니다. 글자 하나가 아니라 1·42 같은 숫자 토큰 전부를 가리키는 단말 기호라서입니다.

여기에 되풀이·생략을 적는 기호를 더한 것이 EBNF(Extended BNF, 확장 BNF)입니다. 아래 예에는 되풀이를 뜻하는 중괄호만 나옵니다. 중괄호로 감싼 부분은 0번 이상 되풀이됩니다.

적는 꼴도 BNF 와 조금 다릅니다. ::= 자리에 = 를 씁니다. 규칙 끝에는 ; 를 붙입니다. 이름에는 꺾쇠를 씌우지 않습니다.

식   = 항 { "+" 항 } ;
항   = 인수 { "*" 인수 } ;
인수 = "(" 식 ")" | 수 ;

같은 문법인데 규칙이 자기 자신을 왼쪽 끝에서 부르는 모양이 사라졌습니다. 「항이 + 로 여러 개 이어진다」고 바로 적었기 때문입니다. 다음 절에서 보듯 이 차이가 파서를 짤 때 중요해집니다.

문법을 읽는 프로그램 파서

이 절은 문법이 정해진 뒤 입력을 실제로 읽는 쪽을 봅니다. 문법은 무엇이 맞는지만 정합니다. 어떻게 읽을지는 정하지 않습니다.

파서는 입력을 받아 시작 기호에서 그 입력까지 가는 유도를 찾아냅니다. 찾으면 구문 트리를 내놓습니다. 못 찾으면 어긋난 곳을 알립니다. 찾는 방향은 크게 둘입니다.

위에서 내려가는 방식은 시작 기호에서 출발해 입력 쪽으로 규칙을 펼칩니다. 비단말 기호마다 함수를 하나씩 두고 서로 부르게 짜는 재귀 하강 파서가 대표입니다. 앞의 EBNF 첫 줄을 코드로 옮기면 이렇게 됩니다.

def expr():            # 식 = 항 { "+" 항 }
    value = term()
    while peek() == "+":
        next_token()
        value += term()
    return value

peek() 는 다음 토큰을 들여다보기만 합니다. next_token() 은 그 토큰을 읽고 넘어갑니다.

term() 도 같은 꼴입니다. 인수를 맡는 함수는 여는 괄호를 만나면 expr() 을 다시 부릅니다. 문법의 재귀가 함수의 재귀가 됩니다.

이 코드는 트리를 만들지 않습니다. 토큰을 읽는 즉시 값을 더하도록 줄인 모양입니다. 트리를 만들려면 value += term() 대목에서 + 노드를 만들어 양쪽 결과를 자식으로 매답니다.

이 방식은 식 → 식 + 항 처럼 규칙이 왼쪽 끝에서 자기 자신을 부르면 멈추지 않습니다. expr() 이 토큰을 하나도 읽기 전에 expr() 을 또 부르기 때문입니다. 이런 규칙을 좌재귀라고 합니다. 앞 절처럼 되풀이 꼴로 고쳐 적어 피합니다.

아래에서 올라가는 방식은 반대로 갑니다. 토큰을 읽어 쌓아 두다가, 쌓인 것이 어떤 규칙의 오른쪽 모양과 같아지면 왼쪽 이름 하나로 줄입니다. 끝까지 줄여 시작 기호 하나만 남으면 입력이 맞은 것입니다. 문법 파일을 받아 이런 파서 코드를 만들어 주는 파서 생성기도 있습니다.

촘스키 위계 속 위치

이 절은 문맥 자유 문법을 다른 문법들과 나란히 놓고 봅니다. 문법은 규칙에 거는 제약에 따라 네 계층으로 나뉩니다. 이 계층 구분을 촘스키 위계라고 부릅니다.

아래 줄로 갈수록 제약이 풀려 적을 수 있는 언어가 넓어집니다. 위 줄 문법이 적는 언어는 아래 줄 문법으로도 모두 적힙니다. 대신 입력이 맞는지 가리는 기계도 무거워집니다.

위 두 줄에는 짝이 되는 기계가 있습니다. 정규 문법은 유한 상태 기계와, 문맥 자유 문법은 푸시다운 오토마타와 짝입니다. 개발할 때 문법을 직접 다루는 일은 대개 이 두 줄 안에서 끝납니다.

문법을 꺼낼 때와 정규 표현식으로 충분할 때

이 절은 백엔드 개발에서 이 문법을 언제 꺼내는지를 JSON(JavaScript Object Notation, 자바스크립트 객체 표기법)을 들고 봅니다. 가르는 기준은 입력에 겹침이 있느냐입니다.

JSON 에서는 값 안에 배열이 들어갑니다. 그 배열 안에 다시 값이 들어갑니다. 문맥 자유 문법으로 적으면 이 겹침이 규칙 한 쌍으로 드러납니다.

값   → 객체 | 배열 | 문자열 | 수 | true | false | null
배열 → [ ] | [ 값목록 ]
값목록 → 값 | 값 , 값목록

값이 배열을 부릅니다. 배열은 값목록을 거쳐 다시 값을 부릅니다. 이 재귀가 있어서 배열을 몇 겹이든 넣을 수 있습니다. 같은 까닭으로 겹침이 있는 입력을 정규 표현식으로 잘라 읽으면 깊이가 달라지는 순간 깨집니다.

겹침이 있는 입력을 받는다면 문법을 먼저 적고 파서를 둡니다. SQL(Structured Query Language, 구조화 질의 언어) 의 WHERE 조건식이나 검색창에 넣는 (a OR b) AND c 같은 질의처럼 괄호와 중첩이 들어가는 작은 언어가 그렇습니다. 문법을 적어 두면 무엇이 맞는 입력인지가 코드보다 먼저 문서로 남습니다.

겹침이 없는 입력에는 이 문법이 과합니다. 날짜, 로그 한 줄, 주문 번호처럼 모양이 평평한 입력은 정규 표현식 하나로 충분합니다. 문법과 파서를 따로 두면 그만큼 짤 코드와 고칠 곳이 늘어납니다.

관련 항목

문맥 자유 문법을 이루는 구성 요소

생성 규칙 · 비단말 기호 · 단말 기호 · 시작 기호 · 유도 · 토큰

문맥 자유 문법이 속하는 형식 언어 이론

형식 문법 · 형식 언어 · 촘스키 위계 · 정규 문법 · 문맥 의존 문법 · 무제한 문법 · 정규 표현식 · 오토마타 이론

문법의 계층마다 짝이 되는 계산 모형

유한 상태 기계 · 상태 기계 · 푸시다운 오토마타 · 선형 한정 오토마타 · 튜링 기계 · 스택

문맥 자유 문법을 적는 표기법

BNF · EBNF · ABNF · 철도 다이어그램

문맥 자유 문법을 읽어 트리를 만드는 파서

파서 · 재귀 하강 파서 · LL 파서 · LR 파서 · LALR 파서 · 파서 생성기 · 파서 결합자 · CYK 알고리즘 · 얼리 파서

파서가 문법에서 얻어 내는 트리

구문 트리 · 추상 구문 트리 · 파스 포레스트

문법을 짤 때 걸리는 함정

모호한 문법 · 좌재귀 · 연산자 우선순위 · 결합 방향 · 매달린 else 문제

문맥 자유 문법으로 모양을 정하는 언어

JSON · SQL · XML · 프로그래밍 언어 · 도메인 특화 언어

문법 검사 앞뒤에 서는 컴파일 단계

컴파일러 · 렉서 · 의미 분석 · 타입 검사 · 인터프리터