[프로그래밍 언어론] 4강 - 구문론과 의미론

📌 개요

🎯 학습 목표

┗  구문론과 의미론 정의, 표현 방법

 

🔑 학습 키워드

┗  프로그래밍 언어 형식적 정의

┗  구문론: 문맥 자유 문법(CFG), BNF, EBNF, 구문 도표

┗  의미론: 정적 의미론(속성 문법), 동적 의미론(기능적, 표기적, 공리적 의미론)

 

💡 1. 구문론과 의미론

[ 언어의 형식적 정의 ]

┗  '구문론'과 '의미론'을 통해 언어를 엄밀하게 정의하는 것을 의미

- 구문론(syntax): 문장의 올바른 '형태'를 정의
- 의미론(semantics): 올바른 형태의 문장이 나타내는 '의미'를 정의

┗  예시: 한국어 -> '나는 너를 사랑한다.'

- 구문: 주어 + 목적어 + 서술어
- 의미: 화자가 청자를 몹시 아끼고 귀중히 여김

┗  예시: 영어 -> 'I love you'

- 구문: 주어 + 동사 + 목적어
- 의미: 화자가 청자를 몹시 아끼고 귀중히 여김

 

[ 프로그래밍 언어의 형식적 정의 ]

┗  프로그래밍 언어의 명확한 사용체계를 제공

- '구문론': 프로그램의 표면적인 구조를 정의.
-> 프로그램을 올바른 형태로 작성할 수 있음.
- '의미론': 프로그램의 내용적인 효과를 정의.
-> 해석의 모호함을 제거하고 동작 예측할 수 있음.

┗  프로그래밍 언어의 형식적 정의 예시:

'BASIC' -> PRINT "GCD is "; A
- 구문: PRINT "출력할 내용"; 변수
- 의미: 출력할 내용과 변수의 값을 순차적으로 출력하라.

'C언어' -> printf("GCD is %d\n", a);
- 구문: printf("출력할 내용", 변수);
- 의미: 출력할 내용의 %d 자리에 변수의 값을 대신 넣어 내용을 출력하라.

┗  프로그램의 구조:

- '문자': 영어 알파벳, 아라비아 숫자, 특수 기호 등
- '어휘(토큰)': 문자의 나열. (최소한의 의미를 갖는 단어)
- '구문': 프로그램을 작성하는 규칙. (토큰을 모아 프로그램을 구성)

┗  프로그램의 의미:

- 프로그램을 통해 발생하는 현상

 

💡 2. 구문의 표현

[ 구문론 ]

- 프로그램의 표면적인 구조를 정의
- 정의된 구문을 통해 모든 정상적인 프로그램을 도출할 수 있음
- 작성된 프로그램이 정의된 구문에 맞는 프로그램인지 확인할 수 있음

[ 구문의 표현 ]

- 명확한 표현을 위해 문법을 활용
- 일반적으로 프로그래밍 언어에서는 '문맥 자유 문법'을 이용

[ 문맥 자유 문법: CFG ]

- 구성: '비단말 기호 집합', '단말 기호 집합', '생성 규칙 집합', '시작 비단말 기호'
- '비단말 기호': 정의될 대상
- '단말 기호': 언어에서 직접 사용되는 표현
- '생성 규칙': 어떤 비단말 기호를 어떻게 바꾸어 쓸 수 있는지 규정
- '시작 비단말 기호': 언어에 속한 모든 형태를 만들 수 있는 비단말 기호

- [생성 규칙]은 [하나의 비단말 기호]를 [단말 기호]와 [비단말 기호]의 조합으로 정의
- '문맥 자유 문법'은 다양한 방법으로 표현이 가능함 -> 'BNF', 'EBNF', '구문 도표'
- 세 가지 표현법은 서로 변환이 가능함. ex) BNF <-> EBNF ... 등

 

[ BNF (Backus-Naur Form) ]

┗  'Algol의 구문'을 정의하기 위해 배커스와 나우어가 사용한 표현법임.

┗  메타 기호:

'::=' -> 정의를 표현
'|' -> 택일(or)을 표헌
'< >' -> 비단말 기호를 표현

┗  문맥 자유 문법의 BNF 표현:

- '비단말 기호': 메타 기호 < > 로 묶인 기호
- '단말 기호': 비단말 기호 및 메타 기호가 아닌 기호
- '규칙': 메타 기호 ::= 를 기준으로 왼쪽 부분을 오른쪽 부분으로 정의

┗  BNF 예제: if 문 정의

<if문> ::= if <논리식> then <문장> else <문장>
        | if <논리식> then <문장>

 

[ EBNF (Extended BNF) ]

┗  추가적인 메타 기호를 사용하여 더 간결한 표현이 가능하도록 확장된 BNF

- '메타 기호 [ ]': 생략 가능을 표현
- '메타 기호 { }': 0번 이상 반복을 표현
- '메타 기호 ( )': 묶음 -> 메타 기호 |(택일)과 함꼐 쓰이며, 한정된 범위의 택일을 표현
- "메타 기호 ' '": 단말 기호 묶음 -> 메타 기호를 단말 기호로 사용 가능하도록 표현
- '메타 기호 ;': 규칙 묶음을 구별하기 위해 각 규칙의 마지막에 사용

┗  EBNF 예제: if 문 정의

<if문> ::= if <논리식> then <문장> [ else <문장> ]
        ;

 

[ 구문 도표 (syntax diagram) ]

┗  초기 'Pascal'의 사용자 설명서에 사용된 표현법

┗  순서도와 유사하게 그림으로 구문을 표현

- '사각형': 비단말 기호 표현
- '원': 단말 기호 표현
- '화살표': 비단말, 단말 기호들을 연결 -> 규칙을 표현하는 데 사용

┗  구문도표 예제: if 문 정의

 

💡 3. 의미의 표현

[ 의미론 ]

- '프로그램의 내용'적인 효과를 정의
- '프로그램 실행 시 어떤 일이 일어나는지' 그 의미를 기술
- '구문으로 표현하기 어려운 제약사항'을 기술하기도 함

 

[ 의미의 표현 ]

- (1) 일반적으로 자연어 문장으로 표현하나 명확성이 부족
- (2) 의미를 엄밀히 표현하기 위해 다양한 기법이 개발됨 (형식 의미론, formal semantics)
- (3) 대표적으로 사용되는 기법: '추상기계 코드를 사용하는 방식', '수학식등을 사용하는 방식'
'** 1~3번 순: 자연어 명확성 부족 -> 형식 의미론 개발 ** '

 

[ 두 가지 의미론 ]

[ '정적 의미론' ]
- '프로그램을 수행하기 전'에 프로그램의 의미가 맞는지 파악하는 방법
- 주로 타입 검사를 수행할 때 활용함
- 대표적인 표현 방법: 속성 문법

[ '동적 의미론' ]
- '프로그램을 수행 시' 나타나게 될 프로그램의 의미를 표현하는 방법
- 프로그램의 수행 측면은 다양하기 때문에 다양한 방법이 사용되고 있음
- 대표적인 표현 방법: '기능적 의미론', '표기적 의미론', '공리적 의미론'

 

[ 속성 문법 ]

- '정적 의미론'의 표현 방법
- 즉, 프로그램을 실행하기 전에 의미적으로 올바른지 검사
- 각 비단말 기호마다 타입 속성이 있다고 가정하여 이에 대한 규칙을 정의하는 방법
'예시': '속성 문법 = 문법 구조 타입' 등의 정보를 붙여서 프로그램이 의미적으로 올바른지 검사하는 방법
'결론': 타입 검사와 같이 정적으로 표현이 가능한 방법을 나타냄.

 

[ 기능적 의미론 ]

- '동적 의미론'의 표현 방법 중 한 가지
- 추상기계의 '상태'를 바꾸는 것으로 프로그램의 수행 의미를 표현하는 방법
-> 프로그램 수행은 결국 컴퓨터의 상태를 바꾸는 것

 

[ 표기적 의미론 ]

- '동적 의미론'의 표현 방법 중 한 가지
- 프로그램을 구성하는 '각 구문 요소'를 '수학적 표기'에 대응시켜 수행 의미를 표현하는 방법
- 대응시키는 함수를 '의미함수'라고 함.

 

[ 공리적 의미론 ]

- '동적 의미론'의 표현 방법 중 한 가지
- 프로그램의 효과로 수행 의미를 표현하는 방법
- '프로그램의 효과': 프로그램 S가 실행됨으로써 사전조건 P를 사후조건 Q로 변환시키는 것을 의미
-> {P} S {Q}
- 공리 체계를 이용함으로써 주변 상황에 대응하는 논리식을 정확히 구할 수 있음.

 

[ 의미론의 한계 및 효과 ]

'의미론의 한계': 프로그래밍 언어 전체에 대한 의미 표현은 너무 복잡함.
- '동적 의미론'에서 추구하는 '수학적 체계'는 일반인이 이해하기에 너무 복잡함.
-> 여전히 프로그램의 의미는 자연어로 기술되는 추세임.

'의미론의 효과': 다양한 방법론은 프로그램 구현 및 분석 등에 유용하게 사용됨.
- '속성 문법': 인터프리터 및 컴파일러 구현 시 트리 생성, 타입 검사, 코드 생성 등에 유용하게 사용됨.
- '수학적 표기': 언어의 특성을 명확하게 정의해야 할 때 언어 설계 방법론의 일부로 사용
- '공리적 의미론': 프로그램의 특정 조건 만족 여부를 기계적으로 확인하고자 할 때 사용