[프로그래밍 언어론] 구문법

구문법

 구문법이란 '문장을 구성하는 방식'으로 앞선 포스팅에서 알아보았듯이 어휘 분석, 의미론과 함께 프로그래밍 언어 정의를 위해 필수적인 개념이다. 그렇다면, 가능한 문장은 무한히 많을 것인데, 이런 무한한 것들을 유한한 것으로 어떻게 정의할 수 있을까? 우리는 이것을 재귀식을 이용해 해결할 수 있다. 이 포스팅에서 여러 구문의 구문법들을 알아보자.

 

이진수의 구문법

 이진수는 0 혹은 1로 표현된다. 이것을 다음과 같이 표현해보자. 

1. 숫자 D는 '0' 또는 '1'이다.

2. 이진수 N을 구성하는 방법은 다음 두 가지이다. 숫자 D 하나로 표현하는 것과 이진수 N 다음에 숫자 D를 하나 붙여 구성하는 것이다.

 

 위의 두 가지의 이진수 구성 방법을 논리 규칙 형태로 표현해 보자.

1. D는 숫자이다. -> D는 이진수 N이다.

2. N이 이진수이고 D는 숫자이다. -> ND는 이진수이다.

 

이제 이것을 더 간단하게 표현해 보자. (아래 표현식에서 |는 논리 연산의 OR와 같다. 즉, 이진수 N은 D 또는 ND라는 것을 의미한다.)

N -> D | ND

 

계산 규칙은 다음과 같다. 

V('0') = 0, V('1') = 1

V(ND) = V(N) * 2 + V(D)

 

이것을 이진수 101에 적용해 보자.

V('10') = V('1') * 2 + V('0') = 2, V('101') = V('10') * 2 + V('1') = 2 * 2 + 1 = 5로 이진수 101이 5와 같다는 것을 알 수 있다. 

 

이제 이것을 십진수로 확장시켜 보자. 

D -> 0 | 1 | 2 | ... | 9

N -> D | ND 

V('0') = 0, V('1') = 1, ... , V('9') = 9

V(ND) = V(N) * 10 + V(D)

 

이것을 십진수 386에 적용하면, V('386') = V('38') * 10 + V('6'), V('38') = V('3) * 10 + V('8) = 38. V('38') * 10 + V('6') = 380 + 6 = 386인 것을 알 수 있다. 

 

수식(expr) 구문법

먼저 수식(Expression)의 구문법은 아래와 같다.

E -> E * E | E + E | (E) | N

N -> ND | D

D -> 0 | 1 | 2 | ... | 9

 

위 구문법의 값 계산 규칙은 아래와 같다. 

V(E + E) = V(E) + V(E)

V(E * E)  = V(E) * V(E)

V( (E) ) = V(E)

V(N) = N

 

이제 위 구문법과 계산 규칙을 기반으로 4 * 3 + 9의 의미 값을 계산해 보자.

V(4 * 3 + 9) = V(4 * 3) + V(9) = V(4) * V(3) + V(9) = 4 * 3 + 9 = 21

즉, 컴퓨터는 4 * 3 + 9를 위 계산 규칙에 따라 계산해 결국 4 * 3 + 9 식이 21의 값을 가지는 것을 계산한다.

 

프로그래밍 언어의 구문 구조

1. id = E

2. if E then S else S

3. while ( E ) S

 

익숙한 구조로 생각할 수 있는데 정확하다. 1은 변수에 값을 대입하는 대입문, 2는 if - else 구문, 3은 while 반복문의 구문법이다. 위 구문법을 통해 프로그래밍 언어 S의 구문법을 아래와 같의 정의해보겠다.

 

S -> id = E | if E then S else S | while ( E ) S | ...

이러한 문법을 CFG(Context Free Grammar) 문맥 자유 문법이라 하며, 재귀적 구조를 자연스럽게 표현할 수 있다. 다음은 CFG의 구성이다.

 

- T: Terminal 심볼의 집합. 소문자로 표현

- N: Non Terminal 심볼의 집합. 대문자로 표현

- S: 시작 심볼

- 생성 규칙(Production Rule)의 집합

 

유도

 문장 / 프로그램이 문법에 맞는지 검사하는 것을 구문 검사라고 하는데, 입력된 문자열이 문법에 맞는지 검사하려면 해당 문자열이 문법으로부터 유도 가능해야 한다. 즉, 어떤 문자열이 문법으로부터 유도 가능하면 문법에 맞는 문자열이며 그렇지 않으면 문법에 맞지 않는 문자열이다. 

 

유도 과정은 다음과 같다.

1. 시작 심볼 S에서 시작한다.

2. Non Terminal 심볼 X를 X로 시작하는 생성 규칙 X-> Y1 Y2 ... Yn을 적용해 그 오른쪽 부분인 Y1 Y2 ... Yn로 대치한다.

3. 위 과정을 Non Terminal 심볼이 없을 때 까지 반복한다. 

터미널 심볼은 대치할 규칙이 없기 때문에 일단 생성되면 끝으로 터미널 심볼은 그 언어의 토큰이라 한다.

 

말로만 보면은 잘 이해가 되지 않으니 간단한 예시를 이용해 보자.

S -> aS | b 생성 규칙에서 문자열 aaab를 유도해 보자.

S => aS => aaS => aaaS => aaab와 같이 문자열 aaab를 유도할 수 있다. 즉, 유도는 생성 규칙을 이용해 Non Terminal 심볼을 Terminal 심볼로 변환하는 과정이다. 

 

 직접 유도 방식은 생성 규칙을 한 번만 적용하는 것으로 =>로 표현하고, 생성 규칙을 여러 번 적용하는 것은 =>의 우상단에 *를 붙여 표현할 수 있다.

 

ex) 수식 문법에서 3 + 4 * 5 유도하기

E -> E * E | E + E | (E) | N

N -> ND | D

D -> 0 | 1 | 2 | ... | 9

 

E => E + E => N + E => D + E => 3 + E => 3 + E * E => 3 + N * E => 3 + D * E => 3 + 4 * E => 3 + 4 * N => 3 + 4 * D => 3 + 4 * 5

 

좌측 유도, 우측 유도

 위의 예시인 수식 3 + 4 * 5 유도는 제일 왼쪽 논 터미널 심볼을 터미널 심볼로 변환해 나갔다. 즉, 좌측 유도 방식인 각 직접 유도 단계에서 가장 왼쪽 논 터미널 심볼을 선택하여 이것에 생성 규칙을 적용했다.

 이와 반대로 유도하는 것도 가능하다. 가장 오른쪽 논 터미널 심볼을 선택해 이것에 생성 규칙을 적용하면 우측 유도 방식이 된다. 

 

유도 트리

 유도 트리는 유도의 복잡한 과정을 한 눈에 보기 좋게 표현한 것으로 parse tree, syntax tree라고도 부른다. 이 유도 트리가 어떤 스트링에서 2개 이상의 유도 트리를 가지면 해당 문법이 모호하다고 할 수 있는데, 이에 대해서는 다음 포스팅에서 또 알아보겠다.

 

BNF와 구문 다이어그램

BNF는 Non Terminal 심볼을 < ... > 형태로, Terminal 심볼은 <> 없이 표현하는 형식이다. BNF로 수식 문법을 표현해 보자. 

 

수식의 BNF 표현

<expr> -> <expr> + <term> | <term>

<term> -> <term> * <factor> | <factor>

<factor> -> number | ( <expr> )

 

여기서 확장된 BNF인 EBNF를 이용해 다음과 같이 수식 문법을 표현할 수 있다. 위 수식은 덧셈, 곱셈만 표현할 수 있으니 뺄셈, 나눗셈도 표현할 수 있도록 확장해 보자.

EBNF에서 []는 0 또는 1회, {}는 0 또는 여러 번 반복됨을 의미한다.

 

수식의 EBNF 표현

<expr> -> <expr> {+ <term> | - <term>}

<term> -> <term> {* <factor> | / <factor>}

<factor> -> number | ( <expr> )

 

이제 EBNF를 이용해 여러 구문을 표현해보자.

 

문장의 EBNF 표현

<stmt> -> id = <expr> ; | ' { ' {<stmt>} '}' | if ( <expr> ) then <stmt> [else <stmt>] 

             | whie ( <expr> ) <stmt> | read id; | print <expr>;

 

수식의 EBNF 표현

<expr> -> <bexp> {& <bexp> | ' | ' <bexp> } | !<expr> | true | false

<bexp> -> <aexp> [<relop> <aexp>]

<relop> -> == | != | < | > | <= | >=

<aexp> -> <term> {+ <term> | - <term>}

<term> -> <factor> {* <factor>  | / <factor>}

<factor> -> [ - ] ( number | ( <aexp> ) | id)

 

이렇게 표현식만 줄줄 늘어놓아서는 도대체 이게 어떻게 문장, 수식을 표현한다는 것인지 이해할 수 없다. stmt부터 조금 뜯어보자. stmt의 if ( <expr> ) then <stmt> [else <stmt>]는 if 구문을 표현한 것이다. if 구문을 사용할 때, 우리는 if를 쓰고 괄호 () 안에 조건식을 써 놓고, 해당 조건이 만족하는 경우 실행할 문장 <stmt>를 작성한다. 여기서, else 구문은 필수가 아니므로 []를 이용해 0번 혹은 1번 반복됨을 표현하였다. 

 

다음은 수식이다. <bexp>는 비교 연산 구문, <relop>는 비교 연산자, <aexp>와 <term>은 연산을 뜻한다. <bexp>를 예시로 한 번 뜯어보자. <aexp> -> <term> -> <factor> -> number로 유도하고, <relop>를 비교 연산자 <로 유도해보자. 그렇다면 number < number 형태의 비교 연산 구문이 등장하게 된다. 

재귀 하강 파서

이렇게 구문법에 대해 알아보았는데, 구문법에 대한 검사를 어떻게 할 수 있을까? Parser를 구현하여 구문법을 검사할 수 있다. Parsing은 주어진 입력 스트링이 문법에 맞는지 자동적으로 유도하며 분석하는 것을 의미하며, Parser는 파싱하여 분석하는 프로그램이다. 따라서 입력된 스트링의 논 터미널 심볼을 재귀적으로 파싱하는 프로그램을 재귀 하강 파서라고 한다. 이에 대해서는 예전 강의를 들었을 때의 과제를 이용해 하나하나 뜯어보겠다.