문법 변환

2026.09.02 10:51

문법 변환은 같은 언어를 생성하면서 구문분석하기 좋은 형태로 문법을 고치는 작업이다. 사람이 읽기 좋게 쓴 문법과 파서가 처리하기 좋은 문법이 다르기 때문에 필요하다.

무엇이 문제인지는 산술식 문법 하나로 다 드러난다.

E → E + E | E - E | E * E | E / E | 0 | 1 | 2 | 3 | 4 | 5

읽기에는 이보다 자연스러울 수 없다. 그런데 3+4*5를 좌단유도해 보면 유도트리가 두 개 나온다.

(a) E ⇒ E+E ⇒ 3+E ⇒ 3+E*E ⇒ 3+4*E ⇒ 3+4*5      →  3+(4*5) = 23
(b) E ⇒ E*E ⇒ E+E*E ⇒ 3+E*E ⇒ 3+4*E ⇒ 3+4*5    →  (3+4)*5 = 35

같은 문장인데 계산 결과가 다르다. 한 문장에 유도트리가 둘 이상이면 그 문법은 모호하다(ambiguous)고 한다. 파서가 어느 쪽을 고를지 결정할 근거가 문법 안에 없다는 뜻이다.

아래에서 다루는 변환은 네 가지인데, 앞의 둘은 모호성을 없애고 뒤의 둘은 하향식 파싱을 가능하게 한다.

우선순위와 결합법칙

모호성의 원인은 연산자 간의 우선순위와 같은 우선순위끼리의 결합 방향, 두 가지다.

우선순위만 정해서는 부족하다. 3-4-5는 연산자가 하나뿐인데도 유도트리가 둘 나온다. (3-4)-5 = -6과 3-(4-5) = 4다. 왼쪽부터 계산할지 오른쪽부터 계산할지가 정해져 있지 않기 때문이다.

둘 다 문법의 계층으로 표현한다.

E → E + T | E - T | T        낮은 우선순위, 좌재귀 → 좌결합
T → T * F | T / F | F        높은 우선순위, 좌재귀 → 좌결합
F → ( E ) | id               가장 높다

우선순위는 계층의 깊이로 나타낸다. 나중에 묶여야 하는 연산자를 위에 둔다. +가 *보다 위에 있으므로 *가 먼저 묶인다.
결합 방향은 재귀의 방향으로 나타낸다. E → E + T는 왼쪽이 재귀이므로 좌결합이고, 오른쪽을 재귀로 쓰면(E → T + E) 우결합이 된다.

이제 3+4*5도 3-4-5도 유도트리가 하나씩만 나온다.

이 대응은 Pratt 파싱의 결합력 쌍과 정확히 같은 것을 다르게 적은 것이다. Pratt은 (왼쪽, 오른쪽) 두 숫자의 대소로 결합 방향을 정하고, 여기서는 재귀가 어느 쪽에 오는지로 정한다. CPython의 PEG 문법이 sum: sum '+' term(좌재귀 → 좌결합)과 power: await_primary '**' factor(우재귀 → 우결합)를 나란히 쓰는 것이 이 방식이다.

모든 모호한 문법을 모호하지 않게 고칠 수 있는 것은 아니다. 그 언어를 생성하는 모든 문법이 모호하면 그 언어를 본질적으로 모호하다(inherently ambiguous)고 하고, 이런 언어가 실제로 존재한다.

left-factoring

모호성을 없애도 하향식 파싱에는 또 다른 장애물이 있다.

S → c A d
A → a | a b

cabd를 파싱한다고 하자. S → cAd를 적용한 뒤 A를 펼쳐야 하는데, 지금 보이는 것은 a뿐이고 그다음이 b인지 아닌지 모른다. A → a를 먼저 고르면 cad가 되어 틀리고, 되돌아가 A → ab를 다시 시도해야 한다.

S ⇒ cAd ⇒ cad      ← 실패, 되돌아감 (backtracking)
       ⇒ cabd

이 되돌아가기가 backtracking이고, 파서 효율을 크게 떨어뜨린다. 원인은 A → a | ab의 두 대안이 같은 접두사 a로 시작한다는 것이다.

해법은 공통 접두사를 인수분해하는 것이다. 이를 left-factoring이라고 한다.

A → a A′
A′ → ε | b

a를 읽는 결정을 먼저 하고, b가 있는지는 그 뒤에 판단한다. 결정을 미룬 셈이다.

일반형은 이렇다. A → αβ₁ | αβ₂ | … | αβₙ | γ에서 가장 긴 공통 접두사 α를 찾아 이렇게 바꾼다.

A  → α A′ | γ
A′ → β₁ | β₂ | … | βₙ

실제 언어에서 이게 필요한 대표적인 곳이 dangling else다.

S → i E t S | i E t S e S | a      (i=if, t=then, e=else)

iEtS가 공통 접두사이므로 이렇게 바뀐다.

S  → i E t S S′ | a
S′ → e S | ε

else 절이 있는지 없는지를 S′에서 결정한다.

좌재귀 제거

하향식 파싱의 더 근본적인 장애물은 좌재귀다.

E → E + T | T

하향식 파서가 E를 파싱하려면 첫 대안인 E + T를 시도하고, 그러려면 E를 파싱해야 하고, 다시 첫 대안을 시도한다. 입력을 하나도 소비하지 않은 채 같은 규칙으로 돌아오므로 무한 재귀다. 앞 절에서 좌결합을 만들려고 일부러 넣은 좌재귀가 여기서는 치명적이다.

해법은 우재귀로 바꾸는 것이다. 좌재귀 규칙이 실제로 만드는 문자열의 모양을 펼쳐 보면 답이 나온다.

E ⇒ E+T ⇒ E+T+T ⇒ … ⇒ E+T+T+…+T ⇒ T+T+T+…+T

결국 맨 앞에 T가 하나 오고 +T가 0번 이상 반복되는 형태다. 이걸 그대로 규칙으로 적으면 된다.

E  → T E′
E′ → + T E′ | ε

일반형은 A → Aα₁ | … | Aαₘ | β₁ | … | βₙ (모든 βᵢ는 A로 시작하지 않는다)을 이렇게 바꾸는 것이다.

A  → β₁A′ | β₂A′ | … | βₙA′
A′ → α₁A′ | α₂A′ | … | αₘA′ | ε

앞의 산술식 문법에 적용하면 이렇게 된다.

E  → T E′
E′ → + T E′ | ε
T  → F T′
T′ → * F T′ | ε
F  → ( E ) | id

두 문법이 같은 언어를 생성하는지 확인해 보면 길이 9 이하 문자열에서 양쪽 모두 257개로 일치한다. 언어는 보존되고 유도트리의 모양만 바뀐다.

대신 결합 방향이 문법에서 사라진다. 좌결합을 표현하려고 넣은 좌재귀를 제거하면 좌결합이라는 정보가 문법이 아니라 의미 동작(액션) 쪽으로 옮겨간다. E′ → +TE′를 그대로 트리로 만들면 우결합 트리가 나오므로, 좌결합 트리를 얻으려면 파싱 중에 누적하는 코드를 따로 써야 한다. 변환된 문법만 보고 E′, T′가 무엇을 뜻하는지 읽어내기 어려워지는 것도 같은 이유다.

간접 좌재귀

A → Aα 형태가 눈에 보이지 않아도 여러 규칙을 거쳐 돌아오면 마찬가지다.

S → A a | b
A → A c | S d | e

A → Sd이고 S → Aa이므로 A ⇒ Sd ⇒ Aad가 된다. 이것이 간접 좌재귀다.

방법은 대입해서 직접 좌재귀로 만든 뒤 앞의 규칙을 적용하는 것이다. S의 규칙을 A → Sd에 대입하면

A → A c | A a d | b d | e

이제 직접 좌재귀이므로 변환할 수 있다.

S  → A a | b
A  → b d A′ | e A′
A′ → c A′ | a d A′ | ε

이 변환도 길이 10 이하에서 양쪽 143개로 언어가 일치한다.

일반 알고리즘은 논터미널에 A₁, …, Aₙ 순서를 매기고, i를 1부터 올리면서 Aᵢ → Ajγ (j < i) 형태를 전부 Aj의 규칙으로 대입해 없앤 뒤, Aᵢ의 직접 좌재귀를 제거하는 것이다. 순서를 매기는 이유는 대입 방향을 한쪽으로 고정해 순환을 끊기 위해서다.

부수적인 정리

파싱을 가능하게 하는 변환은 아니지만, 문법을 다루기 쉽게 만드는 정리 작업이 셋 더 있다.

불필요한 생성규칙 제거는 터미널 문자열을 결코 생성할 수 없는 논터미널이나 시작기호에서 도달할 수 없는 기호를 쓰는 규칙을 없애는 것이다. S → AB | a, A → a에서 B는 아무것도 생성하지 못하므로 S → AB를 지운다. 두 조건을 모두 검사해야 완전히 제거된다.

ε-생성규칙 제거는 A → ε 형태를 없앤다. 방법은 A가 나타나는 모든 자리에 A가 있는 경우와 없는 경우를 전부 만들어 주는 것이다.

S → aSbS | bSaS | ε
⇒ S → aSbS | abS | aSb | ab | bSaS | baS | bSa | ba

빈 문자열이 언어에 속하면 완전히 제거할 수는 없고, 새 시작기호를 두어 S′ → S | ε로 그 자리만 남긴다.

단일 생성규칙 제거는 A → B처럼 논터미널 하나만 오른쪽에 있는 규칙을 없앤다. B의 규칙들을 A에 직접 복사하면 된다. 유도트리의 높이가 줄어 파싱 단계가 짧아진다.

어떤 파서가 무엇을 요구하는가

지금까지의 변환이 전부 필요한 것은 아니다. 파싱 방식에 따라 요구가 다르다.

	모호성 제거	left-factoring	좌재귀 제거
재귀 하강 / predictive (LL)	필요	필요	필요
LR 계열	필요	불필요	불필요
Pratt	우선순위 표로 대체	불필요	해당 없음
PEG	ordered choice로 대체	불필요	생성기가 지원

좌재귀 제거는 하향식만의 문제다. 상향식은 규칙 전체를 다 읽은 뒤에 무엇이었는지 결정하므로 좌재귀를 그대로 받는다. 오히려 좌재귀 쪽이 스택을 덜 쓴다.

Pratt 파싱은 우선순위 계층 자체를 정수 비교로 대체하므로 이 변환들이 애초에 등장하지 않는다. 좌결합을 만들려고 좌재귀를 쓰고, 그 좌재귀 때문에 다시 변환하는 순환이 없다.

PEG는 대안을 순서대로 시도하고 처음 성공한 것을 택하므로(ordered choice) 공통 접두사가 있어도 모호하지 않다. left-factoring이 필요 없는 이유다. 좌재귀는 본래 지원하지 않지만, CPython의 생성기는 메모이제이션으로 좌재귀 규칙을 지원하도록 확장되어 있어서 문법을 사람이 읽기 좋은 좌재귀 형태 그대로 쓸 수 있다.

참고

컴파일러 opcode 컴파일러 Pratt 파싱 컴파일러 객체 표현과 GC 컴파일러 오토마타 계층 컴파일러 인라인 캐싱과 특수화 컴파일러 중간언어