그래프 구조로서의 문법
컴파일러는 파싱 트리를 구축하여 소스 코드를 변환합니다 — 각 노드가 적용된 문법 규칙을 나타내고, 각 잎이 터미널 기호(변수 이름, 리터럴, 연산자)를 나타내는 루트 트리입니다.
트리의 기하학
n개의 노드 & n−1개의 간선을 가진 트리입니다. 깊이 d: 루트에서 임의의 잎까지의 최대 거리입니다. 깊이 d의 균형 잡힌 이진 트리의 경우: 최대 2^d개의 잎 & 2^(d+1)−1개의 총 노드입니다.
일반적인 식의 파싱 트리는 균형이 맞지 않습니다: 연산자 우선순위는 오른쪽 또는 왼쪽으로 기울어진 트리를 만듭니다. A + B C는 이 +보다 더 깊은 트리를 생성하며, *이 더 강하게 결합함을 인코딩합니다.
BNF & ALGOL
ALGOL을 명시하기 위해 발명된 Backus-Naur Form(BNF)은 문법을 생산 규칙으로 형식화합니다:
``
<expr> ::= <term> | <expr> + <term>
<term> ::= <factor> | <term> * <factor>
<factor> ::= id | (<expr>)
``
각 생산 규칙은 트리의 한 수준을 정의합니다. 문법은 비터미널 기호의 방향성 그래프입니다; 문장 파싱은 시작 기호에서 잎까지 그 그래프를 통한 경로를 따릅니다.
파싱 트리의 깊이 & 표현 복잡도
표현 (A + B) * (C + D)의 경우, 파싱 트리는 표준 연산자 우선순위에서 특정 구조를 가집니다.
파싱 트리의 깊이는 컴파일러 성능에 영향을 미칩니다: 더 깊은 트리는 재귀 하강 파싱 중에 더 많은 스택 프레임이 필요합니다.
Shannon 엔트로피 & 중복성
Hamming은 음성 언어가 ~60% 중복이고 서면 언어가 ~40% 중복임을 언급했습니다. 이것은 정확한 정보이론적 의미를 가집니다.
Shannon 엔트로피
확률 {p₁, p₂, ..., pₙ}을 가진 알파벳 A에서 기호를 생성하는 소스의 경우:
H = −Σ pᵢ log₂(pᵢ) (기호당 비트)
최대 엔트로피: 균등 분포(모든 기호가 동일하게 가능함). H_max = n개 기호에 대해 log₂(n)입니다.
중복성 R: 정보를 전달하지 않는 비트의 분수(내용을 잃지 않고 제거될 수 있음):
R = 1 − H / H_max
R = 0.4(40% 중복)인 경우: 비트의 40%는 컨텍스트에서 예측할 수 있습니다. 영어 텍스트를 문자당 8비트로 전달하는 채널은 정보에 대해 용량의 60%만 사용합니다; 40%는 수신자가 이미 알고 있는 구조입니다.
오류 감지는 중복성을 사용합니다: 비트의 40%가 예측 가능한 경우, 전송 오류는 중복성 구조를 위반하는 시퀀스를 생성할 수 있습니다 — 오류 정정 코드 없이도 감지 가능합니다.
APL의 거의 영 중복성: 단일 문자 변경은 컨텍스트만으로 거의 감지할 수 없습니다. 영어의 60% 중복성: 문자가 누락되거나 잘못되었어도 주변 컨텍스트에서 단어를 종종 재구성할 수 있습니다.
중복성 계산
영어 문자 빈도(대략): 'e'는 시간의 ~12.7%로 나타납니다; 'z'는 ~0.07%로 나타납니다. 영어의 실제 엔트로피는 약 H ≈ 1.0 비트/문자입니다(단어 수준 컨텍스트를 고려). 26자 알파벳의 최대 엔트로피: H_max = log₂(26) ≈ 4.70 비트/문자입니다.
기하학으로서의 성장 곡선
컴파일러 알고리즘은 크기 n의 프로그램(토큰, 라인 또는 노드)을 처리합니다. 알고리즘의 선택은 컴파일 시간이 프로그램 크기에 따라 어떻게 확장되는지를 결정합니다.
공통 복잡도 클래스
| 클래스 | 런타임 | 예시 |
|---|---|---|
| O(n) | 선형 | 어휘 스캔 |
| O(n log n) | 준선형 | 최적 정렬 |
| O(n²) | 이차 | 순진한 중복 감지 |
| O(n³) | 3차 | 행렬 곱셈, CYK 파싱 |
| O(2ⁿ) | 지수 | 순진한 정리 증명 |
기하학적 그림: 런타임 대 n을 그립니다. O(n)은 직선입니다. O(n²)은 포물선입니다. O(2ⁿ)은 n=0 근처에서 평평해 보이고 n=50 근처에서 거의 수직인 지수 곡선입니다.
일반 문맥 자유 문법 파싱(CYK 알고리즘)은 O(n³)에서 실행됩니다. 대부분의 실제 프로그래밍 언어의 경우, 문법은 LR(1)-파싱 가능하도록 설계되어 O(n) 파싱을 허용합니다. ALGOL의 문법은 FORTRAN의 문법보다 더 복잡했으며, 더 느린 컴파일러에 기여했습니다 — 1958년 컴파일이 몇 시간이 걸릴 때 중요했던 실제 마찰입니다.
교차점
순진한 기호 테이블 조회는 n개 식별자의 프로그램에 대해 총 O(n²) 연산을 사용합니다(n개 조회 각각에 대해 선형 스캔). 해시 테이블 기호 테이블은 총 O(n) 예상 연산을 사용합니다.
가정: O(n²) 알고리즘은 1958년 하드웨어에서 10⁶ 연산/초로 실행됩니다. O(n) 알고리즘은 동일한 속도로 실행되지만 100n 설정 연산이 필요합니다(해시 테이블 구성).