프로그래밍 언어론 - 구문구조와 문법(1)

◆구문 구조란?(syntax)

▷문법적으로 올바른 프로그램을 정확하게 기술한 것

▷Algol60 정의에서 구문구조가 최초 등장

▷현재, 대부분의 언어에서 사용

●세 단계로 나누어 정의

▷어휘 구문 구조

┗언어를 구성하는 기본 기호(이름,값,연산자 등)를 정의

▷구체적인 구문 구조

┗계산식, 문장, 프로그램을 작성하는 규칙

▷추상적인 구문 구조

┗구두점이나 괄호와 같은 구문인식 전용 구조를 제외한 핵심적인 구문 정보만으로 구성된 구문

 

◆2.1 문법

●메타언어(metalanguage)

▷언어를 기술하는데 사용하는 언어

●문법(grammar)

▷언어의 문법구조를 메타언어를 사용하여 정의

●목적

▷프로그래밍 언어의 구문 구조를 정의

 

●백커스/나우어 형식(BNF: Backus Naur From)

▷촘스키 계층의 문맥 자유문법(CFG)(=type2)을 실용적으로 사용할 수 있도록 만든 것

▷Algol60 의 구문 구조를 정의하는데 처음 사용

▷현재, 대부분의 언어 구문 구조 정의에서 사용

 

◆BNF 문법

●다음의 집합으로 구성

▷생성 규칙(Productions): P

▷단말자 기호(Terminal symbols): T

▷비단말자 기호(Nonterminal symbols): N

▷시작 기호(Start symbol): S , S∈N

＠ G={N,T,S,P}

●생성 규칙은 다음과 같이 작성

▷여기서 A → ω 이고, A ∈ N , ω ∈(N ∪T ) * 이다.

●3개의 메타 심볼 사용

▷<> 비단말 기호

▷-> 생성하다

▷| 또는

┗ex) binaryDigit → 0 | 1

 

◆유도

●⇒ 유도하다(derive)

▷

 

●352와 같은 부호가 붙지 않은 정수를 이 문법으로 유도해낼 수 있다.

▷

 

◆오른쪽 우선 유도

●Integer ⇒ Integer Digit

⇒ Integer 2

⇒ Integer Digit 2

⇒ Integer 5 2

⇒ Digit 5 2

⇒ 3 5 2

▷단계마다 가장 오른쪽 비단말자가 대치되는 유도 방식을 ‘오른쪽 우선 유도’라고 한다.

 

◆왼쪽 우선 유도

●Integer ⇒ Integer Digit

⇒ Integer Digit Digit

⇒ Digit Digit Digit

⇒ 3 Digit Digit

⇒ 3 5 Digit

⇒ 3 5 2

▷단계마다 가장 왼쪽 비단말자가 대치되는 유도 방식을 ‘왼쪽 우선 유도’라고 한다.

 

●Integer ⇒ * 352

▷Integer 문법규칙을 사용하여 유한 번의 단계를 거쳐 352가 유도될 수 있음을 뜻한다.

 

●352 ∈ L(G)

▷352는 문법 G로 정의된 언어에 포함됨을 뜻한다.

 

●L(G) = { ω ∈ T* | Integer ⇒* ω }

▷문법 G로 정의된 언어는 문법규칙 Integer로 유도할 수 있는 모두 기호 문자열 ω 의 집합임을 뜻한다.