구문론과 의미론 , 프로그래밍 언어

구문론과 의미론과 프로그램

언어를 연구하는 다양한 분야 중 대표적인 것으로 구문론과 의미론이 있다.

구문론은 문장이 구성되는 방식에 대해서, 의미론은 문장 나타내는 의미에 대해서 연구하는 분야이다.

나는 너를 사랑한다. , I LOVE YOU

주어 + 목적어 +서술어, 주어 + 동사 + 서술어 등을 위의 예로 형식을 나눌 수 있으며 의미는 같은 의미로 나는 너를 몹시 아끼고 귀중히 여긴다라는 의미를 갖는다. 각 언어는 그 언어만의 문자 \구성 방식이 있고 그에 따라 의미를 해석한다. 구문론과 의미론을 통해 언어를 정의할 수 있는데 이를 언어의 형식적 정의라 부른다.

 프로그래밍 언어에서는 형식적 정의가 더욱 중요해진다. 왜냐면 컴퓨터가 프로그램을 정확히 이해할 수 있도록 해야 하기 때문이다.

int x;
x= 3 + 4;
if x>10 then...

위의 예를 통해 알아보자 위 내용의 형식적 정의는 다음과 같다고 생각할 수 있다.

• 문자 : 기본적으로 알파벳 숫자 기호 등의 단위를 말한다 예) 1,2,3, a, A,*,#등
• 어휘(토큰) : 문자들이 어울려서 최소한의 의미를 갖는 것, 의미가 부여된 게 중요해 보인다. 예) int, them, if, 3,2,=등
• 구문 : 이러한 어휘, 토큰들로 프로그램을 작성하는 규칙 예) (int)+변수(x)+; , 변수(x) = + 수식(3+4) + ;

위예시에서 int x;의 의미는 x라는 이름의 정수현 변수를 선언을 의미하고 두 번째 문장은 3+4를 계산하여 x에 대입한다는 것을 의미한다. 그리고 마지막엔 x의 값이 10보다 크다면 어떻게 하겠다는 의미를 말한다. 이와 같이 프로그래밍 언어의 형식적 정의는 구문론과 의미론으로 나누어지며, 구문론은 프로그램의 표면적인 구조를 정의하는 것으로 어떻게 작성해야 하는지를 기술한다. 의미론은 프로그램의 내용을 효과적으로 정의하는 것으로 실행 시 어떤 일이 일어나는지 그 의미를 말한다.

 

구문의 표현

프로그래밍에서 구문의 표현은 결국 컴퓨터가 알아야 하니 명확한 표현을 위해 문법을 활용한다. 일반적으로 프로그래밍 언어는 문맥 자유 문법으로 표현한다.

문맥자유문법

문맥자유문법이란 문맥에 영향을 받지 않는 문법이란 의미로 변수를 예로 들어보면 변수는 어떤 문장에 등장하든 구조가 항상 동일하다.

문맥자유문법은 4가지 구성요소를 갖는다. 

• 비단말 기호 : 정의될 대상
• 단말 기호 : 언어에서 직접 사용되는 표현들
• 시작 비단말 기호 : 언어에서 독립적으로 사용될 수 있는 단위
• 규칙 : 비단말 기호를 구체적으로 정의
• 시작 바단말기호는 어떤 문장에서든 사용되든 상관없이 자신의 규칙되로 정의가 된다. 각규칙은 하나의 비단말 기호를 단말 기호와 비단말 기호의 조합으로 정의한다.
• 표현하는 세 가지 방법인 BNF, EBNF, 구문 도표가 있다. 그리고 세 가지 표현법은 서로 변환이 가능하다.

BNF(backus-Nair Form)

BNF의 메타기호는 다음과 같다.

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

문맥 자유 문법의 BNF표현

• 비단말 기호 : 메타기호 < >로 묶인 기호 예) <letter>, <digit>
• 단말 기호 : 비단말 기호 및 메타기호가 아닌 기호 예) A, b, d, if,0등
• 규칙 메타기호 : := 를 기준으로 왼쪽 부분을 오른쪽 부분으로 정의, 즉  : := 의 왼쪽 부분에는 하나의 비단말 기호만 나와야 하고 오른쪽 부분에는 단말 기호, 비단말 기호, 메타기호 |를 활용하여 왼쪽 부분의 비단말 기호를 정의하는 내 요잉 나와야 한다.

<identifier> : := <abc> | <def> | <ghi>
<vaseline> : := A|B|C|D|<id>

 : := 기호 왼쪽에 있는 각각의 <identifier>, <vaseline> 비단말 기호는 |의 기호로 값 중 하나의 택일을 한다는 것으로 <identifier>는 <abc> , <def>, <ghi> 중 하나로 정의가 된다는 것이다.

EBNF(Extended BNF)

기존 BNF에서 추가적인 메타 기호를 사용하여 간결하게 표현할 수 있도록 확장된 BNF이다. 추가된 메타기호는 다음과 같다.

• [  ] : 생량가능한 표현
• { } : 0번 이상 반복을 표현
• ( ) : 메타기호 |과 함께 쓰여 한정된 범위의 택일을 표현
• ' ' : 메타기호를 단말 기호로 사용함을 표현

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

정의 메타기호 왼쪽의 비단말기호 <if문>을 다음과 같이 정의한다. 메타기호 [  ]에 묶인 else <문장>을 사용하여 if <논리식> then <문장> else <문장>  될 수도 있고 if <논리식> then <문장> 일 수도 있다.

<interger> : := <digit> { <digit> }

왼쪽 비단말 기호 <interger>는 매타기호 { }에 묵인 <digit> 0번 사용하여 한 자릿수 <digit>이 될 수도 있고 여러 번 사용하여 <digit><digit><digit>이 될 수도 있다.

<수식> : := <수식> ( + | - | * | / ) <수식>

메타기호 ( )로 묵인 기호 ( ) 안쪽만 고려하여 +,-,*,/ 중 하나의 기호만 사용한다. <수식> +<수식>을 왼쪽 비단말기호로 정의한다.

<BNF규칙> : := <왼쪽 부분> ': :=' <오른쪽 부분>

' ' 메타기호는 메타기호 자체를  단말기호로 사용하는 것을 표현한다. 즉 규칙정위를 위한 것이 아닌 단말기호로 사용하게 된다.

앞서 EBNF는 BNF로 서로 변환이 가능했다 이를 증명해 보자
위예시 중
<interger> : := <digit> { <digit> }를 BNF로 표현해 보자면
<interger> : := <digit> | <interger><digit> , 메타기호 |의 오른쪽을 선택하면 <interger>가 유지되면서 <digit>가 하나 더 붙는 것이 된다 필요한 반복수만큼 기호 | 반복해서 선택하면 된다.

구문 도표(syntax diagram)

 

구문 도표는 순서도와 유사한 그림으로 표현하는 것이다. 이는 초기 Pascal사용자 설명서에서 사용되었고 직관적인 표현을 이용해 초보자들도 쉽게 이해할 수 있다. 아래의 BNF표현을 구문도표와 비교해 보자

ㅁ = 비단말기호
O = 단말기호
→ = 비단말 기호 및 단말 기호들을 연결, 규

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

 

위의 BNF예시를 구문도표로 옮기면 위의 그림과 같다.

<interger> : := <digit> { <digit> }

구문도표 예시

위 두 예시는 BNF와 구문도표를 상호 변환한 것이다. 다음으로 한 가지 예시로 세 가지를 모두 표현해 보자

BNF
<ident> : :=<letter> | <ident><letter> | <ident><digit>
ident는 letter 이거나 letterletter 또는 letterdigit이다.
EBNF
<ident> : :=<letter> {<ident><letter> | <ident><digit}

위의 세 가지는 동일한 내용이 된다.

 

의미의 표현

프로그래밍 언어에서 의미론은 프로그램의 내용적인 효과를 정의하는 것으로 실행 시 어떤 일이 일어나는지 그 의미를 기술하는 것이다. 또한 구문으로 표현하기 어려운 제약사항을 기술하기도 한다. 이런 의미론의 표현은 사람이 이해할 수 있는 자연어로 표현하는 것이 일반적이지만 자연어는 명확함에 한계가 있어 다양한 기법이 개발되었다. 대표적으로 추상기계 코드를 사용하거나 수학식을 사용하는 방식을 예로 들 수 있다.

형식의미론

• 정적의미론 : 프로그램을 수행하기 전에 의미가 맞는지 파악하는 방법으로 주로 타입검사를 수행할 때 정적의미론을 활용한다 대표적인 표현방법은 속성문법
• 동적의미론 : 프로그램 수행 시 나타나게 될 프로그램의 의미를 표현함, 수행 측면은 다양해 여러 방법이 있고 대표적인 방법으로 기능적 의미론 표기적 의미론 공리적 의미론이 있다.

속성문법

정적의미론을 표현하는 방법으로. 각 비단말 기호마다 타입 속성이 있다고 가정하여 이에 대한 규칙을 정의하는 방법. 예를 들어 즉, 타입 자료형 등에 대한 정의의 규칙을 검사한다.

<D> : : = < T> <id > <L> ;
<T> : : = int | char
<L> : : = <id><L> 3(3 거꾸로 쓰는 거 empty를 뜻한다. 어떻게 쓰는지 못 찾겠다.)
이렇게 정의하면 <T>는 타입을 정의하는 것을 알 수 있다. 그타입은 <id> 변수를 말하고 <L>는 변수가 하나가 아닐 수 있으기에 <L>을 정의한다.

기능적 의미론

• 동적 의미론의 표현 방법 중 한 가지
• 프로그램이 수행되면 컴퓨터의 상태가 바뀌므로 프로그램의 의미를 추상기계의 상태를 바꾸는 것으로 표현하는 방법이다.
• 상태 : 수행할 명령어, 메모리상태

x나 y를 정의하고 프로그램을 시작하면서 그 값을 바꾸는 식이 있다면 x나 y의 값은 바뀌고 이러한 상태를 쫓아가서 의미를 표현하는 방법

표기적 의미론

• 동적 의미론의 표현방법 중 한 가지이며
• 프로그램을 구성하는 각 구문 요소를 수학적 표기에 대응시켜 표현하는 방법 대응시켜 표현하는 방법이다. 이를 의미함수라고 부름

<B> : := 0 |1|<B>0|<B>1 
이라면 이걸 수학적으로 푸는 것으로으로 아래와 같다.
Bin[[0]] = 0
Bin[[1]] = 1
Bin[[B0] = 2*Bin[[B]]
Bin[[B1]] = 2*Bin[[B]] +1

공리적 의미론

• 동적의미론의 표현 방법 중한가지
• 프로그램의 실행의미를 프로그램의 효과로 해석하는 방법이다
• 프로그램의 효과 프로그램 S가 실행됨으로써 사전조건 P를 사후 조건 Q로 변화시키는 것으로 다음과 같이 표기한다. {P} S {Q}
• 주번 상황에 대응하는 논리식은 공리 체계로 정확히 구할 수 있다.

의미론의 한계 및 효과

의미론은 프로그래밍 언어의 전체에 대한 의미 표현은 훨씬 복장히지며, 특히 동적 의미론에서 추구하는 수학적 체계는 이해하기에는 너무 복잡하다. 그렇기에 자연어로 기술되는 추세이다. 정적 의미론에서 사용되는 속성문법은 인터프리터 및 컴파일러를 구현할 때 트리생성, 검사타입, 코드 생성등에 유용하게 사용되며, 동적 의미론에서 사용되는 수학적 표기는 언어의 특성을 명확하게 정의할 때 언어 설계 방법론의 일부로 사용된다. 특히 공적 의미론은 프로그램의 특정 조건 만족 여부를 기계적으로 확인하고자 할 때 사용되기도 한다.