문맥 자유 문법: 중첩 구조를 생성 규칙으로 표현하기
문맥 자유 문법은 비단말 기호 하나를 일정한 문자열로 바꾸는 생성 규칙들로 언어를 정의한다. 각 규칙은 주변 기호가 무엇인지와 무관하게 그 비단말에 적용된다. 괄호 중첩이나 프로그램 표현식처럼 재귀 구조를 표현하는 데 적합하다.
문맥 자유 문법의 재귀 규칙은 중첩과 반복 연결을 구조적으로 표현한다.
기호와 규칙의 역할
문법은 비단말 집합, 실제 문자열에 나타나는 단말 집합, 생성 규칙, 시작 기호로 구성한다. 비단말은 아직 확장할 구조를 나타내고, 단말만 남으면 생성이 끝난다. ε는 아무 문자도 만들지 않는 빈 문자열을 뜻한다.
균형 괄호 언어의 한 문법은 S→(S)S | ε다. 첫 S는 한 쌍 안의 중첩을, 뒤 S는 그 쌍 이후의 나머지 괄호열을 나타낸다. 이 구조는 괄호가 균형인지라는 조건을 생성 과정에 반영한다.
Grammar: S -> (S)S | epsilon
A derivation of ()():
S
=> (S)S
=> ()S
=> ()(S)S
=> ()()S
=> ()()
Each epsilon replacement contributes no literal character.
유도 과정의 어떤 S를 먼저 바꾸는지에 따라 순서는 달라질 수 있다. 파스 트리는 어떤 생성 규칙으로 구조가 만들어졌는지를 나타낸다. 하나의 문자열이 여러 파스 트리를 가지는 문법은 모호하다고 한다.
연산자의 의미와 모호성
E→E+E | EE | number라는 문법은 1+23을 두 구조로 해석할 수 있다. (1+2)3과 1+(23)은 계산 결과가 다르다. 곱셈의 우선순위를 분리한 비단말 계층을 두면 원하는 구조를 강제할 수 있다.
문법의 모호성과 언어 자체의 문제는 구별해야 한다. 같은 언어를 다른 문법으로 표현해 모호성을 없앨 수 있는 경우도 있다. 문법이 명확해도 특정 파서가 그 문법을 그대로 처리할 수 있다는 뜻은 아니다.
왼쪽 재귀 규칙은 순진한 재귀 하향 파서에서 즉시 다시 자신을 호출해 멈추지 않게 만들 수 있다. 그러나 왼쪽 재귀가 문법 이론에서 금지된 것은 아니다. 파싱 방식에 맞는 변환이나 다른 알고리즘을 사용한다.
문맥 자유 언어는 푸시다운 오토마타와 대응하며, 스택이 유한 상태보다 더 많은 중첩 기억을 제공한다. 모든 언어를 표현하는 것은 아니고 일반적인 프로그램의 타입 규칙이나 변수 선언 관계는 추가 의미 분석이 필요하다.
고정된 문법에 대해 일반 파싱을 다항 시간에 처리하는 알고리즘이 있고, 실용적 LL·LR 계열은 제한된 문법 구조로 효율적인 처리를 얻는다. 생성 규칙, 문자열, 파스 트리, 의미를 각각 구분하면 문법이 설명하는 범위와 이후 분석이 필요한 범위가 명확해진다.
문법의 생성 능력과 파서의 오류 복구는 별개다. 파서는 유효하지 않은 입력에서도 오류 위치를 설명하거나 일부 구조를 복원할 수 있지만 그 입력이 문법의 언어에 속하게 되는 것은 아니다. 또한 괄호가 올바르다고 모든 변수 선언이나 연산 타입이 맞는 것은 아니다. 예를 들어 x+1이라는 구조가 문법적으로 가능해도 x가 선언됐는지와 숫자인지는 다른 검사를 요구한다. 구문 분석 결과를 의미 분석에 전달하는 이유가 여기에 있다.