프로그래밍언어론 4강 - 구문과 의미의 형식적 표현
프로그래밍 언어를 엄밀하게 정의하는 두 축인 구문론과 의미론을 학습한다. 문맥 자유 문법과 BNF·EBNF·구문 도표로 올바른 프로그램의 형태를 나타내는 방법, 속성 문법과 기능적·표기적·공리적 의미론으로 프로그램의 뜻을 설명하는 방법을 예제와 함께 정리한다.
제1장 프로그래밍 언어의 형식적 정의
1. 구문론과 의미론
언어를 정확히 이해하려면 문장이 어떤 형태로 쓰여야 하는지와 그 문장이 무엇을 뜻하는지를 함께 알아야 한다. 전자를 다루는 분야가 구문론(syntax)이고, 후자를 다루는 분야가 의미론(semantics)이다. 구문론은 문장의 올바른 형태를 정의하며, 의미론은 올바른 형태의 문장이 나타내는 의미를 정의한다. 두 분야를 이용해 언어의 사용 체계를 엄밀하게 정하는 것을 언어의 형식적 정의라고 한다.
자연어에서도 구문과 의미는 구별된다. “나는 너를 사랑한다”는 한국어 문장은 ‘주어+목적어+서술어’의 순서를 따르고, “I love you.”는 ‘주어+동사+목적어’의 순서를 따른다. 두 문장은 표면적인 배열 규칙은 다르지만 화자가 청자를 아끼고 귀중히 여긴다는 의미는 같다. 이처럼 형태와 뜻은 관련되어 있으나 동일한 개념은 아니다.
| 구분 | 정의 대상 | 핵심 질문 |
|---|---|---|
| 구문론 | 프로그램의 표면적인 구조와 올바른 형태 | 어떤 형태로 작성해야 하는가? |
| 의미론 | 프로그램의 내용적인 효과와 실행 결과 | 실행하면 어떤 일이 일어나는가? |
2. 프로그래밍 언어에서 형식적 정의가 필요한 이유
프로그래밍 언어는 컴퓨터가 처리하는 언어이므로 해석의 여지가 남아서는 안 된다. 형식적 정의는 컴퓨터가 프로그램을 해석할 때 생길 수 있는 모호함을 제거하고, 작성자가 프로그램의 동작을 예측할 수 있게 한다. 즉 컴퓨터에는 일관된 해석 기준을, 프로그래머에게는 신뢰할 수 있는 사용 기준을 제공한다.
같은 내용을 출력하더라도 언어마다 구문과 의미의 표현 방식은 다르다. BASIC의 PRINT "GCD is"; A는 문자열과 변수 값을 차례로 출력하라는 형태이고, C의 printf("GCD is %d", a);는 문자열 안의 %d 자리를 변수 값으로 바꾸어 출력한다. 두 문장은 비슷한 결과를 만들 수 있지만, 각 언어에서 허용되는 표면 구조와 그 구조를 해석하는 규칙은 서로 다르다.
핵심: 구문이 맞는지는 프로그램의 형태를 검사하는 문제이고, 의미가 무엇인지는 그 프로그램이 실행될 때 발생하는 효과를 설명하는 문제이다. 올바른 구문이라고 해서 자동으로 의도한 의미가 보장되는 것은 아니다.
3. 문자에서 프로그램까지
프로그램의 표면 구조는 문자, 어휘, 구문의 층으로 조직된다. 문자는 영어 알파벳, 아라비아 숫자, 특수 기호처럼 프로그램을 적는 가장 작은 재료이다. 문자들이 모이면 최소한의 의미를 갖는 단어인 어휘 또는 토큰(token)이 된다. 구문은 이러한 토큰을 어떤 순서와 구조로 결합해 프로그램을 만들 수 있는지 정하는 규칙이다.
예를 들어 int x12;에서 int, x12, ;는 각각 의미 있는 토큰이다. 이어지는 x12 = 1 + 5 * 2;는 수식을 계산해 변수에 대입하는 구조이며, 계산 결과는 연산 순서에 따라 11이 된다. 다음 조건이 x12 > 10이라면 조건이 참이므로 뒤의 문장이 수행된다. 토큰의 올바른 배열은 구문이 설명하고, 변수 생성·계산·대입·조건 수행이라는 현상은 의미가 설명한다.
제2장 문맥 자유 문법과 구문의 표현
1. 구문론의 목적
구문론은 프로그램의 표면적인 구조를 정의한다. 잘 정의된 구문으로부터 언어에 속하는 모든 정상적인 프로그램을 도출할 수 있으며, 반대로 작성된 프로그램이 그 언어의 구문에 맞는지 확인할 수도 있다. 프로그래밍 언어에서는 이러한 규칙을 명확하게 표현하기 위해 일반적으로 문맥 자유 문법(CFG, Context-Free Grammar)을 이용한다.
2. 문맥 자유 문법의 네 구성 요소
문맥 자유 문법은 비단말 기호 집합, 단말 기호 집합, 생성 규칙 집합, 시작 비단말 기호의 네 요소로 구성된다. 비단말 기호는 앞으로 정의해야 할 문법적 대상을 나타내고, 단말 기호는 실제 언어 문장에 직접 나타나는 표현이다. 생성 규칙은 한 비단말 기호를 단말 기호와 비단말 기호의 조합으로 어떻게 바꾸어 쓸 수 있는지 정한다. 시작 비단말 기호는 그 언어에 속한 모든 형태를 만들어 내는 도출의 출발점이다.
| 요소 | 역할 | 예시 |
|---|---|---|
| 비단말 기호 집합 N | 정의될 문법 범주 | {E, D} |
| 단말 기호 집합 T | 문장에 직접 나타나는 기호 | {+, *, 0, 1} |
| 생성 규칙 집합 P | 비단말 기호를 다른 기호 조합으로 바꾸는 규칙 | E → E + E, E → D |
| 시작 비단말 기호 | 전체 문장 도출의 출발점 | E |
강의의 예에서는 E → E + E, E → E * E, E → D, D → 0, D → 1의 규칙을 사용한다. 이때 비단말 기호 집합은 N={E,D}, 단말 기호 집합은 T={+,*,0,1}, 시작 비단말 기호는 E이다. 생성 규칙 전체를 P라고 하면 문법은 G=(N,T,P,E)로 나타낼 수 있다.
‘문맥 자유’라는 말은 생성 규칙의 왼쪽에 있는 하나의 비단말 기호를 그 주변 문맥과 관계없이 바꾸어 쓸 수 있다는 뜻이다. 생성 규칙의 왼쪽과 오른쪽을 단순히 문자열 치환으로만 보지 말고, 언어에 속하는 문장을 단계적으로 만들어 내는 도출 규칙으로 이해해야 한다.
3. BNF
BNF(Backus-Naur Form)는 Algol의 구문을 정의하기 위해 사용된 표현법이다. 핵심 메타 기호는 ::=, |, < >이다. ::=는 왼쪽 비단말 기호를 오른쪽으로 정의한다는 뜻이고, |는 여러 대안 가운데 하나를 고르는 택일을 뜻한다. 꺾쇠괄호 < >는 비단말 기호를 표시한다. 작은따옴표는 단말 기호를 묶거나 메타 기호 자체를 단말 기호로 사용할 때 쓰며, 세미콜론은 규칙 묶음의 끝을 구별한다.
예를 들어 다음 규칙은 if문에 else 절이 있는 형태와 없는 형태를 함께 정의한다.
<if문> ::= if <논리식> then <문장> else <문장> | if <논리식> then <문장> ;
4. EBNF
EBNF(Extended Backus-Naur Form)는 BNF에 메타 기호를 추가해 같은 규칙을 더 간결하게 표현한다. 대괄호 [ ]는 생략 가능한 부분, 중괄호 { }는 0번 이상 반복되는 부분, 소괄호 ( )는 묶음을 뜻한다. 소괄호는 |와 함께 쓰여 택일이 적용되는 범위를 한정할 수 있다.
| EBNF 기호 | 의미 | 예 |
|---|---|---|
| [ X ] | X를 한 번 쓰거나 생략 | [ else <문장> ] |
| { X } | X를 0번 이상 반복 | <digit> { <digit> } |
| ( X | Y ) | 묶인 범위 안에서 X 또는 Y를 택일 | ( + | - | * | / ) |
| ‘ X ’ | 메타 기호를 포함한 X를 단말 기호로 사용 | ‘::=’, ‘;’ |
BNF의 두 if문 대안은 EBNF에서 <if문> ::= if <논리식> then <문장> [ else <문장> ] ;로 줄일 수 있다. 또 부호 없는 정수는 적어도 하나의 숫자가 필요하므로 <unsigned integer> ::= <digit> { <digit> } ;로 쓴다. 첫 번째 숫자는 반드시 나오고, 중괄호 안의 추가 숫자는 0번 이상 반복된다.
수식의 연산자를 한정된 범위에서 택일하려면 <수식> ::= <수식> ( + | - | * | / ) <수식> ;로 나타낸다. BNF로 쓰면 네 연산자에 해당하는 대안을 각각 나열해야 하지만, EBNF에서는 소괄호와 택일 기호를 결합해 한 줄로 압축할 수 있다.
5. 구문 도표
구문 도표(syntax diagram)는 초기 Pascal 사용자 설명서에 사용된 표현법으로, 순서도와 비슷한 그림으로 구문을 나타낸다. 단말 기호와 비단말 기호를 서로 다른 모양으로 표시하고, 이들을 선과 화살표로 연결해 진행 경로를 규칙으로 표현한다. 갈라지는 경로는 택일이나 선택을, 되돌아오는 경로는 반복을 나타낼 수 있다.
if문의 도표에서는 if → 논리식 → then → 문장이 필수 경로이며, 이후 else → 문장 경로는 우회할 수 있다. 부호 없는 정수의 도표에서는 첫 digit을 반드시 통과한 뒤 추가 digit으로 되돌아가는 경로가 있으므로 여러 자리 수를 표현한다. BNF, EBNF, 구문 도표는 표기 방식만 다르며 서로 변환할 수 있다.
시험 포인트: BNF·EBNF·구문 도표는 모두 문맥 자유 문법을 표현하는 방법이다. EBNF의 [ ]는 생략 가능, { }는 0번 이상 반복, ( )는 택일 범위를 묶는 기호라는 차이를 정확히 구별해야 한다.
제3장 의미의 표현과 형식 의미론
1. 의미론의 역할
의미론은 프로그램의 내용적인 효과를 정의하고, 프로그램 실행 시 어떤 일이 일어나는지를 기술한다. 또한 구문만으로 표현하기 어려운 제약 사항을 설명하기도 한다. 의미는 흔히 자연어 문장으로 설명하지만 자연어는 해석이 모호할 수 있으므로, 의미를 엄밀하게 표현하기 위한 여러 형식 의미론이 개발되었다.
2. 정적 의미론과 동적 의미론
정적 의미론은 프로그램을 실행하기 전에 의미가 타당한지 파악하는 방법으로, 주로 타입 검사에 활용된다. 대표적인 표현법은 속성 문법이다. 동적 의미론은 프로그램을 실제로 수행할 때 나타나는 의미를 표현하며, 강의에서는 기능적 의미론, 표기적 의미론, 공리적 의미론을 대표 방법으로 다룬다.
| 분류 | 판단 시점과 목적 | 대표 표현법 |
|---|---|---|
| 정적 의미론 | 실행 전에 의미의 적합성, 특히 타입을 검사 | 속성 문법 |
| 동적 의미론 | 실행 중 일어나는 상태 변화나 프로그램 효과를 표현 | 기능적·표기적·공리적 의미론 |
3. 속성 문법
속성 문법은 정적 의미론의 표현 방법이다. 각 비단말 기호에 타입과 같은 속성이 있다고 가정하고, 구문 규칙에 속성 계산 규칙을 결합한다. 예를 들어 선언 규칙 <D> ::= <T> <id> <L> ‘;’에서 <T>가 정수형이면 첫 식별자와 이어지는 식별자 목록에도 그 타입 속성을 전달한다.
<T> ::= int이면 T.t=정수, <T> ::= char이면 T.t=문자로 계산한다. <D> 규칙에서는 id.t=T.t ∧ L.t=T.t를 적용하고, 식별자 목록 규칙에서는 현재 식별자와 나머지 목록에 같은 타입을 전파한다. 이 방식은 구문 구조만으로는 드러나지 않는 타입 일관성을 검사할 수 있게 한다.
4. 기능적 의미론
기능적 의미론은 추상 기계의 상태가 어떻게 바뀌는지를 이용해 실행 의미를 표현하는 동적 의미론이다. 하나의 상태는 보통 <수행할 명령어, 메모리 상태>의 쌍으로 나타낸다. 프로그램 수행은 남은 명령어가 줄어드는 동시에 메모리에 저장된 값이 변하는 상태 전이의 연속이다.
초기 메모리가 [x→5, y→7, z→0]이고 명령이 z=x; x=y; y=z;라면 첫 대입 후 z는 5가 된다. 두 번째 대입 후 x는 7이 되고, 마지막 대입 후 y는 5가 된다. 최종 상태는 [x→7, y→5, z→5]이다. 각 단계의 상태를 추적하면 문장의 수행 효과가 구체적으로 드러난다.
5. 표기적 의미론
표기적 의미론은 각 구문 요소를 수학적 표기에 대응시켜 수행 의미를 표현하는 동적 의미론이다. 구문 표현을 수학적 대상에 대응시키는 함수를 의미 함수라고 한다. 강의의 이진수 예에서는 의미 함수 Bin이 이진수 구문을 정수 값에 대응시킨다.
Bin[[0]]=0, Bin[[1]]=1이 기본 규칙이다. 이진 문자열 B 뒤에 0이 붙으면 기존 값이 두 배가 되므로 Bin[[B 0]]=2×Bin[[B]]이고, 1이 붙으면 두 배한 값에 1을 더하므로 Bin[[B 1]]=2×Bin[[B]]+1이다. 예를 들어 101은 앞의 10 값 2를 두 배한 뒤 1을 더해 5로 해석된다.
6. 공리적 의미론
공리적 의미론은 프로그램의 효과를 논리식으로 나타내는 동적 의미론이다. 프로그램 S가 실행되어 사전 조건 P를 사후 조건 Q로 변화시키는 관계를 {P} S {Q}로 표현한다. 공리 체계를 이용하면 원하는 사후 조건을 보장하기 위해 실행 전에 어떤 조건이 성립해야 하는지 정확히 구할 수 있다.
대입문에 대한 효과 공리는 {Q[x→E]} x=E; {Q}이다. 사후 조건이 a<10이고 문장이 a=b*2라면, 사후 조건의 a를 대입식 b*2로 바꾼다. 그러면 b*2<10, 즉 b<5가 사전 조건이 된다. 따라서 {b<5} a=b*2; {a<10}으로 쓸 수 있다.
7. 형식 의미론의 효과와 한계
형식 의미론은 언어 구현과 프로그램 분석에 유용하다. 속성 문법은 인터프리터와 컴파일러를 구현할 때 트리 생성, 타입 검사, 코드 생성에 활용된다. 수학적 표기는 언어의 특성을 명확히 정의할 때 도움이 되며, 공리적 의미론은 프로그램이 특정 조건을 만족하는지 확인할 때 유용하다.
그러나 프로그래밍 언어 전체의 의미를 형식적으로 표현하는 일은 지나치게 복잡해질 수 있다. 따라서 실제로는 목적에 따라 필요한 의미 표현법을 선택하고, 언어의 모든 측면을 한 방법으로 완전히 기술하려 하기보다 분석 대상과 검증할 성질에 맞추어 사용한다.
구분 기준: 속성 문법은 실행 전 타입 같은 속성을 계산한다. 기능적 의미론은 상태 전이를, 표기적 의미론은 수학적 대상과의 대응을, 공리적 의미론은 사전 조건과 사후 조건 사이의 프로그램 효과를 중심으로 설명한다.
핵심 개념 정리
프로그래밍 언어의 형식적 정의는 구문론과 의미론으로 나뉜다. 구문론은 문자와 토큰을 조합해 올바른 프로그램을 만드는 표면 규칙이고, 의미론은 프로그램 실행으로 발생하는 내용적인 효과이다.
프로그래밍 언어의 구문은 주로 문맥 자유 문법으로 표현한다. 문맥 자유 문법은 비단말 기호 집합, 단말 기호 집합, 생성 규칙 집합, 시작 비단말 기호로 이루어진다. 이를 표현하는 BNF, EBNF, 구문 도표는 서로 변환할 수 있다.
형식 의미론에는 정적 의미를 다루는 속성 문법과 동적 의미를 다루는 기능적·표기적·공리적 의미론이 있다. 각 방법은 타입 속성 계산, 추상 기계의 상태 전이, 수학적 의미 함수, 사전·사후 조건이라는 서로 다른 관점에서 프로그램의 의미를 엄밀하게 나타낸다.
최종 정리: 구문은 “어떻게 써야 하는가”, 의미는 “실행하면 무엇이 일어나는가”에 답한다. CFG의 네 요소와 EBNF 메타 기호의 의미, 정적·동적 의미론 및 네 가지 형식 의미론의 구분은 반드시 연결하여 기억해야 한다.
예상문제 20선
1. 프로그래밍 언어의 구문론에 대한 설명으로 가장 알맞은 것은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ②
구문론은 프로그램의 표면 구조를 정의하며 어떤 형태로 작성해야 하는지를 기술한다. 실행 시의 내용적 효과는 의미론의 대상이다.
2. 프로그래밍 언어의 형식적 정의가 필요한 이유로 옳지 않은 것은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ④
언어마다 같은 의미를 서로 다른 구문으로 표현할 수 있다. 형식적 정의는 각 언어의 구문과 의미를 명확히 할 뿐 모든 언어의 구문을 같게 만들지 않는다.
3. 프로그램 구조의 단위를 작은 것에서 큰 것으로 바르게 나열한 것은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ①
문자가 모여 최소한의 의미를 갖는 토큰이 되고, 토큰을 구문 규칙에 맞게 결합해 프로그램을 구성한다.
4. 문맥 자유 문법의 구성 요소가 아닌 것은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ③
CFG는 비단말 기호 집합, 단말 기호 집합, 생성 규칙 집합, 시작 비단말 기호로 구성된다. 실행 시간은 문법의 구성 요소가 아니다.
5. 문맥 자유 문법에서 비단말 기호의 역할은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ②
비단말 기호는 식, 문장, 숫자처럼 정의될 문법 범주이다. 실제 결과 문장에 직접 나타나는 표현은 단말 기호이다.
6. 문법 G=(N,T,P,E)에서 E가 나타내는 것은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ①
강의 예제에서 N은 비단말 기호 집합, T는 단말 기호 집합, P는 생성 규칙 집합이며 E는 시작 비단말 기호이다.
7. BNF의 메타 기호와 의미의 연결로 옳지 않은 것은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ④
BNF에서 ::=는 왼쪽을 오른쪽으로 정의한다는 뜻이다. 0번 이상 반복은 EBNF의 중괄호가 나타낸다.
8. EBNF의 [ else <문장> ]이 뜻하는 것은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ③
EBNF의 대괄호는 그 안의 부분을 생략할 수 있음을 나타낸다. 따라서 else 절은 있거나 없을 수 있다.
9. <unsigned integer> ::= <digit> { <digit> }에 대한 해석으로 옳은 것은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ①
중괄호 밖의 digit은 필수이고, 중괄호 안의 digit은 0번 이상 반복된다. 따라서 한 자리 이상의 부호 없는 정수를 만든다.
10. 구문 도표에 대한 설명으로 옳지 않은 것은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ④
구문 도표는 실행 상태가 아니라 문법 규칙을 시각화하는 구문 표현법이다. 초기 Pascal 사용자 설명서에 사용되었다.
11. 정적 의미론에 관한 설명으로 가장 알맞은 것은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ②
정적 의미론은 수행 전에 프로그램의 의미가 맞는지 판단하며, 대표적으로 타입 검사에 사용된다. 속성 문법이 대표 표현법이다.
12. 속성 문법에서 선언문의 타입을 식별자 목록에 전달하는 목적은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ③
속성 문법은 비단말 기호에 타입 같은 속성을 두고 계산 규칙으로 전달한다. 이를 통해 구문만으로 나타내기 어려운 타입 제약을 검사한다.
13. 기능적 의미론이 수행 의미를 표현하는 중심 수단은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ④
기능적 의미론은 상태를 수행할 명령어와 메모리 상태의 쌍으로 나타내고, 명령 수행에 따른 상태 변화를 기술한다.
14. 초기 상태가 [x→5, y→7, z→0]일 때 z=x; x=y; y=z; 실행 후 상태는?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ②
먼저 z가 5가 되고, 다음으로 x가 7이 되며, 마지막에 y가 현재 z의 값 5를 받는다. 따라서 최종 상태는 [x→7, y→5, z→5]이다.
15. 표기적 의미론에 대한 설명으로 옳은 것은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ①
표기적 의미론은 구문을 수학적 대상에 대응시키며, 그 대응을 담당하는 함수를 의미 함수라고 한다.
16. 표기적 의미론의 규칙에 따라 Bin[[B 1]]을 계산하는 식은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ③
이진 표현 B의 뒤에 1이 붙으면 기존 값을 두 배한 뒤 1을 더한다. 0이 붙는 경우에는 두 배만 한다.
17. 공리적 의미론의 {P} S {Q}에서 P와 Q를 바르게 설명한 것은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ②
공리적 의미론은 프로그램 S가 사전 조건 P가 성립하는 상태를 사후 조건 Q가 성립하는 상태로 바꾸는 효과를 표현한다.
18. a=b*2 실행 뒤 a<10을 보장하기 위한 사전 조건은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ④
사후 조건 a<10에서 a를 대입식 b*2로 치환하면 b*2<10이 되고, 이를 정리하면 b<5이다.
19. 형식 의미론의 활용을 바르게 연결한 것은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ③
속성 문법은 인터프리터와 컴파일러 구현에서 트리 생성, 타입 검사, 코드 생성 등에 유용하다. 공리적 의미론은 조건 만족 여부를 확인하는 데 활용된다.
20. 형식 의미론의 한계로 강의에서 제시한 것은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ①
형식 의미론은 구현과 분석에 유용하지만, 언어 전체의 의미를 하나의 엄밀한 체계로 모두 표현하는 일은 매우 복잡하다는 한계가 있다.
댓글
댓글 쓰기