구문론과 의미론
사람들이 일반적으로 사용하는 언어는 오랜 시간 거쳐 발전해왔고, 이러한 언어를 연구하는 분야 중 대표적으로 "구문론(Syntax)"와 "의미론(Semantics)"이 있다. 구문론은 문장이 구성되는 방식을 연구하는 분야이고, 의미론은 문장이 나타내는 의미에 대해 연구하는 분야이다.
언어마다 특유의 문장 구성 방식이 있고 그에 맞춰 의미를 해석할 수 있다. 즉, 구문론과 의미론을 통하여 각 언어를 엄밀하게 정의할 수 있다. (이를 "언어의 형식적 정의"라고 한다.)
언어의 형식적 정의는 프로그래밍 언어에서도 매우 중요한데, 컴퓨터가 이해할 수 있도록 프로그래밍 언어는 명확한 구문과 의미가 정의되어야 한다. 또한 실제 프로그램을 작성하는 사람이 원하는 바를 잘 전달할 수 있도록 명확한 사용체계를 갖춰야 한다. 그래야만 프로그램 해석의 모호함이 사라지고, 쉽게 프로그램의 동작을 예측할 수 있다.
구문의 표현
프로그래밍 언어에서 구문론이란 "프로그래밍 언어의 표면적인 구조를 정의하는 것"이다. 어떤 프로그래밍 언어의 구문이 정의되어 있다면 그 구문을 통해 정상적인 프로그램을 도출할 수 있고, 또한 작성된 프로그램이 구문에 맞는 프로그램인지 확인할 수 있다. 이러한 작업들을 위하여 구문 자체의 정의는 명확해야 한다.
프로그래밍 언어에서는 "문맥에 영향을 받지 않는 문법"인 문맥 자유 문법(CFG: Context-Free Grammer)을 지원한다. 문맥 자유 문법은 "비단말 기호", "단말 기호", "시작 비단말 기호", "규칙" 이 4가지 구성 요소를 가진다.
- 비단말 기호: 정의될 대상을 의미한다.
- 단말 기호: 언어에서 직접 사용되는 표현들을 의미한다.
- 시작 비단말 기호: 언어에서 독립적으로 사용될 수 있는 단위를 의미한다.
- 규칙: 비단말 기호를 단말 기호와 비단말 기호의 조합으로 구체적으로 정의하는 것을 의미한다.
지금부터 프로그래밍 언어의 구문을 표현하는 방법들에 대해서 알아보도록 하겠다.
BNF (Backus-Naur Form)
Algol 언어의 구문을 정의하기 위하여 Backus와 Naur가 사용한 표현법이 BNF이다. BNF에서 사용되는 메타 기호가 있는데, 다음과 같다.
- ::= : 정의를 표현하며, 규칙을 표현하는 것이다. ::= 을 기준으로 왼쪽 부분을 오른쪽 부분으로 정의한다.
- | : 택일(한 가지만 선택)을 표현한다. 규칙의 오른쪽 부분에 메타 기호 | 가 등장하면 이를 기준으로 왼쪽이나 오른쪽 중 택일을 해야 한다.
- < > : 비단말 기호를 표현한다. 비단말 기호는 메타 기호 < > 로 묶여있다. <letter>, <문장>, <digit>, <if문> 등이 비단말 기호이다.
if문을 정의하는 규칙을 BNF를 통하여 작성해보겠다.
<if문> ::= if <논리식> then <문장> else <문장>
| if <논리식> then <문장>
BNF를 통해 정의한 if문의 규칙 의미는 다음과 같다.
"비단말 기호 <if문>은 'if <논리식> then <문장> else <문장>'이거나 'if <논리식> then <문장>'이다."
BNF를 통하여 식별자(Identifier)를 정의해보도록 하겠다. 식별자는 문자(대문자 알파벳, 소문자 알파벳)와 숫자(0~9)로 구성되며 첫 글자는 문자여야 한다.
<identifier> ::= <letter> | <identifier><letter>
| <identifier><digit>
<letter> ::= A | B | C ... | X | Y | Z | a | b | c | ... | y | z
<digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
EBNF (Extended BNF)
EBNF는 말 그대로 BNF에 추가적인 메타 기호를 사용하여 규칙을 보다 간결하게 표현하도록 하는 "확장된 BNF"이다. EBNF에서 추가로 사용되는 네 가지 메타 기호는 [ ], { }, ( ), ' ' 이다.
- [ ] : 생략 가능을 표현하며, [ ] 로 묶인 부분은 사용할 수 있고 생략할 수도 있다.
- { } : 0번 이상의 반복을 표현하며 { } 로 묶인 부분은 생략할 수도, 1번 2번, 수백 번 사용할 수도 있다.
- ( ) : 메타 기호 | 와 함께 쓰여, 한정된 범위의 택일을 표현한다.
- ' ' : 메타 기호 자체를 단말 기호로 사용함을 표현한다.
EBNF를 통해 BNF로 작성한 if문을 확장시켜 보겠다. [ ] 메타 기호를 통해 "else <문장>" 부분을 생략할 수 있다.
<if문> ::= if <논리식> then <문장> [ else <문장> ]
이번에는 부호 없는 정수를 (unsigned integer) EBNF로 작성해보겠다. { } 메타 기호를 통해 반복되는 <digit>을 축약시킬 수 있다.
<unsigned integer> ::= <digit> { <digit> }
사칙연산 수식을 EBNF로 작성하면 다음과 같다. ( ) 메타 기호를 통해 +, -, *, / 중 하나만 선택하도록 한다.
<수식> ::= <수식> ( + | - | * | / ) <수식>
구문 도표 (Syntax Diagram)
구문 도표는 순서도와 유사하게 그림으로 구문을 표현하는 것이다. 직관적인 표현 방법이기에 구문을 이해하기 쉽다. 구문 도표의 기본 단위로는 "사각형", "원", "화살표"가 사용된다.
- 사각형: 비단말 기호를 표현한다.
- 원: 단말 기호를 표현한다.
- 화살표: 비단말 및 단말 기호들을 연결하여 규칙을 표현하는데 사용된다.
구문 도표에서 화살표는 다양한 형태로 나타나는데, 나누어지거나 합쳐지기도 하고 반대 방향으로 돌아가기도 한다. 이를 통하여 택일, 반복을 표현할 수 있다.
다음은 if문을 구문 도표로 표현한 것이다. 간단하게 이해할 수 있다.
의미의 표현
프로그래밍 언어에서 의미론은 프로그램의 내용적인 효과를 정의하는 것으로, 프로그램 실행 시 어떤 일이 일어나는지 그 의미를 기술한다.구문으로 표현하기 어려운 제약사항을 기술하기도 한다. 의미의 표현은 사람이 이해 가능한 자연어 문장으로 표현하는 것이 일반적이나, 표현의 한계로 인해 의미의 엄밀한 표현을 위하여 다양한 기법이 개발되었다. 이를 형식 의미론이라고 한다.
형식 의미론은 또 정적 의미론과 동적 의미론으로 나뉜다.
- 정적 의미론: 프로그램을 수행하기 전, 프로그램의 의미가 맞는지 파악하는 방법으로, 타입 검사를 수행할 때 주로 활용된다. 대표적으로
"속성 문법"이 있다. - 동적 의미론: 프로그램 수행 시, 나타나게 될 프로그램의 의미를 표현하는 방법으로, 대표적으로
"기능적 의미론", "표기적 의미론", "공리적 의미론"등이 있다.
속성 문법 (Attribute Grammar)
정적 의미론의 표현 방법으로, 각 비단말 기호마다 타입 속성이 있다고 가정하여 이에 대한 규칙을 정의하는 방법이다.
기능적 의미론 (Operational Semantics)
동적 의미론의 표현 방법 중 하나로, 프로그램이 수행되면 컴퓨터의 상태가 바뀌기에 프로그램의 의미를 추상기계의 상태를 바꾸는 것으로 표현하는 방법이다.
표기적 의미론 (Denotational Semantics)
동적 의미론의 표현 방법 중 하나로, 프로그램을 구성하는 각 구문 요소를 수학적 표기에 대응시켜 표현하는 방법이다. 이때 대응시키는 함수를 의미함수라고 한다.
공리적 의미론 (Axiomatic Semantics)
동적 의미론의 표현 방법 중 하나로, 프로그램의 실행 의미를 프로그램의 효과로 해석하는 방법이다. 이때 프로그램의 효과란 프로그램 S가 실행됨으로써 사후조건 P를 사후조건 Q로 변화시키는 것을 의미한다.
