Grammar/Syntax
문법을 간단히 말하면 문장을 틀리지 않게 쓰는 방법이다. 그러나 이 정의만으로는 충분하지 않다. 이 글에서는 촘스키의 형식 언어학 계열에서 다루는 생성 문법 이론에 따라 문법을 소개하고자 한다.(다른 정의는 추가 바람)
생성 문법에 따르는 문법 정의
- 문법 G = (V, N, P, S)는 다음 조건을 만족하는 4-원소 투플이다.
- V = 문법 G에 지배받는 모든 기호(Symbol) 집합. 여기에서 말하는 기호는, 우리가 상식적으로 사용하는 낱말인 기호와 뜻이 다르다. 상식적으로 기호라고 말하는 대상들은, 생성 문법 상에서는 단말 기호(Terminal Symbol)이며, 생성 문법 상에서는 T라는 약자로 자주 사용한다. 후술할 파스 트리(Parse-Tree)에서 꼭짓점(Vertex)을 맡게 되기에, 줄여서 V라고 쓴다. 학자에 따라서는, 단말 기호 집합 T와 비단말 기호 집합 N을 합집합하면 어차피 V를 유도할 수 있으므로, (V, N, P, S) 대신 (T, N, P, S)를 사용하는 사람도 있다.
- N = 문법 G의 V에 속하는 모든 비단말 기호(Non-Terminal) 집합. 줄여서 N이라고 쓴다. 대표적인 비단말 기호로는 명사, 동사, 주어, 술어 등이 있다. 즉, 촘스키 문법 이론에서는 문법적 대상 역시 기호로 간주한다.
- P = 문법 G를 따르는 문자열을 만들어내는 생성 규칙 집합(Production Set). 줄여서 P라고 쓴다. 생성 규칙이란, V의 원소로 구성된 문자열 e, f가 있다고 가정할 때, e를 f로 치환하는 규칙이다. 이 때, "e를 f로 치환할 수 있다"라는 규칙은 "e → f" 라고 쓴다. P에 속하는 생성 규칙이 가진 특성에 따라 그 문법을 무제한(unrestricted, 또는 구-구조 문법 Phrase-Structure Syntax), 문맥 민감(context-sensitive), 문맥 자유(context-free), 정규(regular) 문법의 4가지로 구분할 수 있다. 자연어는 보통 무제한 문법으로 간주된다.
- S = 문법 G에 따르는 모든 문장(Sentence)을 유도해낼 수 있는 비단말 기호이다. 따라서 V의 원소이고, N의 원소이기도 하다. 모든 문법은 하나의 S를 가진다. 학자에 따라 S 대신 소문자 시그마(σ)를 사용하는 학자도 있다.
위와 같은 네 원소를 가지는 4-원소 투플을 우리는 G라고 하며, G로부터 파생된 모든 단말 문자열의 집합을 우리는 언어(language)라고 부른다.
무제한 문법
무제한 문법을 따르는 생성 규칙 집합의 모든 원소는 어떤 0개 이상의 기호열이 어떤 0개 이상의 기호열로 대체될 수 있다. 계산 이론 상에서의 튜링 머신과 동일한 표현력을 지닌다.
문맥 민감 문법
문맥 민감 문법을 따르는 생성 규칙 집합은 기호열 E가 기호열 F로 대체될 수 있으며, |E|는 |F|보다 작다. 무제한 문법과 같은 점은, 어떤 단말 문자열의 파스 트리가 하나로 정해지지 않을 가능성이 있다.
문맥 자유 문법
현존하는 거의 모든 프로그래밍 언어의 구문 명세 시에 사용하는 문법. 기호열 E는 F로 대체될 수 있으며, |E| = 1이면서 E는 N의 원소이다. 즉, 단말 기호는 대체될 수 없으며, 비단말 기호열을 다른 것으로 대체하는 규칙 또한 세울 수 없다. 따라서 파스 트리는 하나로 정해지며, 컴파일러의 구문 분석기는 이를 통해 효과적으로 프로그램을 파싱할 수 있다. 계산 이론 상에서의 푸시다운 오토마타와 동일한 표현력을 지닌다.
정규 문법
정규 문법은 오른쪽 방향 또는 왼쪽 방향으로만 파싱될 수 있다. 표현력은 가장 좁으나(예컨대, 한 쪽 방향으로만 파싱될 수 있다는 특징 때문에 괄호를 정의할 수 없다), 계산 시 처리가 빠르기 때문에 컴파일러의 토큰 생성기를 만들 때 자주 사용하며, 텍스트 에디터에서 텍스트를 검색할 때도 정규식이라는 이름으로 자주 쓰인다. 텍스트를 자주 만지는 사람이라면, 정규식은 매우 유용하니 한 번쯤 배워 보자. 삶의 질이 달라진다. 계산 이론 상에서의 유한 상태 오토마타와 동일한 표현력을 지닌다.