왜 언어의 문법을 “형식적으로” 적어야 하는가

한국어 문법책은 “주어 다음에 목적어가 오고, 그다음 서술어가 온다” 같은 문장으로 규칙을 설명합니다. 하지만 프로그래밍 언어의 문법을 이런 자연어 문장으로만 적으면 애매함이 생깁니다. “괄호는 중첩해서 써도 되는가”, “연산자를 몇 개까지 이어 쓸 수 있는가” 같은 질문에 자연어 설명은 종종 답을 주지 못합니다. 그래서 프로그래밍 언어의 구문(syntax)은 수학적으로 엄밀하게 정의된 표기법으로 기술합니다. 이번 편에서 다루는 BNF·EBNF·구문 도표가 바로 그 표기법입니다.

쉽게 말하면: BNF·EBNF·구문 도표는 언어의 문법을 “애매함 없이” 적기 위한 세 가지 서로 다른 표기 방식입니다.

이 편은 본론 08편(구문과 의미)에서 BNF/EBNF로 실제 언어 구문을 기술하고 해석하는 문제를 풀기 전에, 표기법 자체의 규칙만 먼저 익히는 선행 편입니다. 여기서는 “문법이 왜 이런 모습으로 쓰이는가”와 “기호를 어떻게 읽는가”에만 집중합니다.

1. 문맥 자유 문법이라는 큰 틀

BNF와 EBNF는 모두 문맥 자유 문법(context-free grammar, CFG)이라는 수학적 틀 위에서 작동합니다. 문맥 자유 문법이란 “어떤 기호를 다른 기호(들)로 바꿔 쓸 수 있는가”를 정의한 생성 규칙(production rule)의 모음입니다. “문맥 자유(context-free)“라는 이름은 어떤 기호를 바꿀 수 있는지가 그 기호의 주변 맥락과 무관하게 정해진다는 뜻입니다. 즉 기호 하나를 바꾸는 규칙은 그 기호 앞뒤에 무엇이 있든 상관없이 항상 똑같이 적용됩니다.

문맥 자유 문법은 두 종류의 기호를 구분합니다.

• 단말 기호(terminal symbol): 더 이상 다른 기호로 바뀌지 않는, 실제 문장에 그대로 나타나는 기호입니다. 예를 들어 if, +, ( 같은 키워드나 연산자, 숫자·식별자 자체가 단말 기호입니다.
• 비단말 기호(nonterminal symbol): 생성 규칙을 통해 다른 기호(단말 또는 비단말)의 나열로 바뀔 수 있는 기호입니다. 예를 들어 <식>, <문장> 처럼 “아직 구체화되지 않은 문법 범주”를 나타내는 이름입니다.

쉽게 말하면: 단말 기호는 “최종적으로 코드에 남는 글자”, 비단말 기호는 “아직 더 풀어써야 할 문법 범주의 이름”입니다.

2. BNF(Backus-Naur Form) 기초 표기

BNF는 Backus-Naur Form(배커스-나우어 표기법)의 줄임말로, 존 배커스(John Backus)와 피터 나우어(Peter Naur)가 ALGOL 60이라는 언어의 문법을 기술하기 위해 고안한 표기법입니다. BNF의 생성 규칙은 다음과 같은 형태를 가집니다.

<비단말 기호> ::= 대체 가능한 기호열

여기서 ::=는 “~로 정의된다” 또는 “~로 바뀔 수 있다”는 뜻으로 읽습니다. 왼쪽의 비단말 기호를 오른쪽의 기호열로 대체할 수 있다는 규칙입니다. 여러 개의 대체 가능한 기호열이 있으면 세로 막대 |(또는, or)로 나열합니다.

간단한 예로 “0 이상 9 이하의 한 자리 숫자”를 정의하는 BNF 규칙을 보겠습니다.

<숫자> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

이 규칙은 “비단말 기호 <숫자>는 0, 1, 2, … , 9 중 하나로 바뀔 수 있다”는 뜻입니다. 0부터 9까지는 더 이상 바뀌지 않는 단말 기호입니다.

이번에는 “덧셈식”을 정의해 보겠습니다.

<덧셈식> ::= <숫자> | <숫자> + <덧셈식>

이 규칙은 재귀적(recursive)입니다. <덧셈식>을 정의하는 규칙의 오른쪽에 다시 <덧셈식> 자신이 등장하기 때문입니다. 이 재귀 규칙 덕분에 5, 5 + 3, 5 + 3 + 2처럼 숫자가 몇 개든 이어지는 덧셈식을 하나의 규칙으로 표현할 수 있습니다.

어떻게 문장이 만들어지는지 유도(derivation) 과정으로 확인해 보겠습니다. 5 + 3 + 2가 이 문법에 맞는 문장인지 확인하려면, <덧셈식>에서 출발해 규칙을 하나씩 적용하며 원하는 문자열이 나오는지 따라가면 됩니다.

<덧셈식>
  → <숫자> + <덧셈식>        (두 번째 대체 규칙 적용)
  → 5 + <덧셈식>              (<숫자>를 5로 대체)
  → 5 + <숫자> + <덧셈식>     (다시 두 번째 규칙 적용)
  → 5 + 3 + <덧셈식>          (<숫자>를 3으로 대체)
  → 5 + 3 + <숫자>            (첫 번째 대체 규칙 적용, 더 이상 재귀 안 함)
  → 5 + 3 + 2                 (<숫자>를 2로 대체)

각 화살표 →는 “생성 규칙을 한 번 적용했다”는 뜻입니다. 이렇게 시작 기호(여기서는 <덧셈식>)에서 출발해 단말 기호로만 이루어진 문자열에 도달하는 과정을 유도라 부르고, 유도로 만들어낼 수 있는 모든 문자열의 집합이 그 문법이 정의하는 언어(language)입니다. 이 편에서 사용하는 “언어”라는 말은 01편의 “프로그래밍 언어”와는 다른, “문법이 만들어내는 문자열의 집합”이라는 형식 언어 이론(formal language theory)의 좁은 의미임에 주의해야 합니다.

자주 틀리는 점: ::=를 등호(=)와 똑같이 “같다”로 오해하면 안 됩니다. ::=는 방향성이 있는 “정의·대체” 관계이며, 왼쪽은 반드시 비단말 기호 하나여야 합니다. 오른쪽에 왼쪽과 같은 기호가 다시 등장하는 재귀 규칙은 잘못된 것이 아니라, 반복되는 구조(리스트, 중첩된 식 등)를 표현하는 정상적이고 널리 쓰이는 방법입니다.

3. EBNF(Extended BNF) — 반복과 선택을 더 간결하게

BNF는 표현력은 충분하지만, “0번 이상 반복”, “있어도 되고 없어도 됨” 같은 구조를 표현하려면 재귀 규칙을 여러 겹 써야 해서 문법이 길어지고 읽기 번거로워집니다. 이런 불편을 줄이기 위해 만든 것이 EBNF(Extended BNF, 확장 배커스-나우어 표기법)입니다. EBNF는 BNF와 표현할 수 있는 언어의 범위는 같지만, 몇 가지 편의 기호를 추가해 더 간결하게 씁니다.

쉽게 말하면: EBNF는 BNF에 “반복”, “선택”, “생략 가능”을 짧게 쓰는 기호 몇 개를 추가한 표기법입니다.

예를 들어 “부호가 있을 수도 없을 수도 있는 정수”를 BNF와 EBNF로 각각 표현해 비교하면 다음과 같습니다.

BNF:
<정수> ::= <부호있는숫자열> | <숫자열>
<부호있는숫자열> ::= + <숫자열> | - <숫자열>
<숫자열> ::= <숫자> | <숫자> <숫자열>

EBNF:
<정수> ::= ['+' | '-'] <숫자> {<숫자>}

EBNF 한 줄이 BNF 세 줄을 대신합니다. ['+' | '-']는 “+나 - 중 하나가 있어도 되고 없어도 된다”는 뜻이고, <숫자> {<숫자>}는 “숫자 하나가 반드시 있고, 그 뒤에 숫자가 0번 이상 더 올 수 있다”는 뜻입니다. 즉 “숫자가 최소 1개 이상”이라는 조건을 <숫자> {<숫자>}처럼 “하나 + 반복”의 조합으로 표현하는 것이 EBNF의 흔한 패턴입니다.

표기 하나를 실제 문자열에 대입해 확인해 보겠습니다. -42가 ['+' | '-'] <숫자> {<숫자>} 규칙에 맞는지 판정해 보면, -는 ['+' | '-'] 자리에, 첫 4는 <숫자> 자리에, 마지막 2는 {<숫자>}가 한 번 반복된 자리에 대응하므로 규칙에 맞습니다. 반대로 4-2는 부호가 숫자 사이에 끼어 있어 이 규칙의 순서(부호 → 숫자들)에 맞지 않으므로 규칙 위반입니다.

자주 틀리는 점: [ ](0번 또는 1번)와 { }(0번 이상)를 뒤바꿔 외우는 실수가 잦습니다. 대괄호는 “괄호를 열고 닫는 모양이 한 번만 여닫히는 느낌”으로, 중괄호는 “여러 번 겹쳐 감쌀 수 있는 반복의 느낌”으로 구분해 기억하면 헷갈림을 줄일 수 있습니다. 또한 EBNF는 BNF보다 더 강력한 문법이 아니라, 같은 문맥 자유 문법을 더 짧게 쓰는 표기 방식일 뿐이라는 점도 시험에서 자주 확인하는 포인트입니다. 표현할 수 있는 언어의 범위(표현력)는 BNF와 EBNF가 동일합니다.

4. 구문 도표(syntax diagram) 읽는 법

구문 도표는 BNF/EBNF와 같은 문법 규칙을 글자 대신 그림(순서도 형태)으로 표현한 것입니다. 특히 Pascal 언어의 문법 설명서에서 널리 쓰인 방식입니다.

쉽게 말하면: 구문 도표는 문법 규칙을 화살표를 따라가는 길찾기 그림으로 바꾼 것입니다.

구문 도표를 읽는 규칙은 다음과 같습니다.

• 타원(또는 둥근 상자): 단말 기호(그대로 등장하는 키워드·기호)를 나타냅니다.
• 사각형: 비단말 기호(다른 도표로 더 풀어써야 하는 문법 범주)를 나타냅니다.
• 화살표를 따라가는 경로: 왼쪽에서 오른쪽으로 화살표를 따라가면서 지나치는 기호들이 순서대로 나열된 것이 하나의 유효한 문장이 됩니다.
• 갈라지는 경로: 여러 갈래로 길이 나뉘면 그중 하나의 경로만 선택해서 지나가면 됩니다(선택, BNF의 |에 대응).
• 되돌아가는 경로(고리): 화살표가 앞으로 돌아가는 고리 모양이면 그 구간을 여러 번 반복할 수 있다는 뜻입니다(EBNF의 { }에 대응).

앞서 다룬 “부호가 있을 수도 없을 수도 있는 정수”(EBNF: ['+' | '-'] <숫자> {<숫자>})를 구문 도표로 그리면 다음과 같은 흐름이 됩니다.

이 그림을 왼쪽 시작점에서 오른쪽 종료점까지 따라가면서 지나친 단말 기호들을 순서대로 적으면, 그 문법이 허용하는 문장 하나가 만들어집니다. 예를 들어 시작 → 부호 생략 → 숫자(4) → 숫자 더 있음(2) → 숫자 더 있음 없음 → 종료 경로를 따라가면 42라는 문자열이 만들어지고, 시작 → 부호 - → 숫자(4) → 숫자 더 있음(2) → 종료 경로를 따라가면 -42가 만들어집니다.

자주 틀리는 점: 구문 도표에서 “고리(반복 경로)를 한 번도 지나가지 않는 것”이 허용되는지 아닌지는 도표마다 다릅니다. 위 예시처럼 <숫자> {<숫자>} 구조를 표현한 도표는 첫 숫자 하나는 반드시 지나가야 하고(최소 1개), 반복 고리는 0번 지나가도 됩니다. 도표를 읽을 때는 “어느 지점부터가 생략·반복 가능한 구간인가”를 정확히 구분해야 합니다.

5. BNF·EBNF·구문 도표 비교

세 표기법은 표현할 수 있는 문법의 범위(문맥 자유 문법)가 동일하며, 서로 변환이 가능합니다. 차이는 오직 표기의 형태와 가독성입니다.

자주 틀리는 점: “구문 도표는 BNF/EBNF보다 더 많은 언어를 표현할 수 있다”거나 “EBNF는 BNF로 표현할 수 없는 문법도 표현할 수 있다”는 식의 보기는 옳지 않습니다. 셋 다 문맥 자유 문법이라는 같은 표현력을 가진 서로 다른 표기 방식일 뿐입니다.

핵심 정리

• 문맥 자유 문법은 단말 기호(최종적으로 남는 글자)와 비단말 기호(더 풀어써야 할 문법 범주), 그리고 이들 사이의 생성 규칙으로 구성된다.
• BNF는 <비단말> ::= 대체 기호열의 형태로 규칙을 적고, 재귀 규칙으로 반복·중첩 구조를 표현한다.
• EBNF는 [ ](0 또는 1번), { }(0번 이상 반복), ( )(묶음) 기호를 추가해 BNF와 같은 표현력을 더 간결하게 쓴 것이다.
• 구문 도표는 같은 문법을 타원(단말)·사각형(비단말)·화살표(순서)·갈래(선택)·고리(반복)로 이루어진 그림으로 표현한 것이며, BNF·EBNF와 표현력이 동일하다.

마무리 복습

참고 자료

• 국가평생교육진흥원 독학학위제: https://bdes.nile.or.kr