[컴파일러] 컴파일러: 원리, 기법, 도구 - 구문 정의와 파스 트리

구문 정의 (syntax definition)

문맥 자유 문법은 언어의 구문을 기술하기 위해 사용되며 컴파일러의 전반부를 표현하는 방법이다.

그렇다면 문맥 자유 문법(줄여서 자유 문법)은 어떻게 표현될까? 익숙한 if-else 문을 통해 자유 문법을 알아보자.

if (expression) {
    statement
} else {
    statement
}

이 C 코드를 자유 문법으로 나타내면 다음과 같이 표현된다.

- statement -> if (expression) {statement} else {statement}

화살표의 뜻은 왼쪽 문법 기호가 오른쪽 문자열을 생성한다는 뜻이다. (오른쪽 문자열로 왼쪽 문자열로) 이러한 형식을 생성 규칙(production) 이라고 한다. 문맥 자유 문법을 통해서는 의미 규칙 이란 것도 표현할 수 있는데 이것은 파스트리 이후에 알아보도록 하자.

문맥 자유 문법은 다음의 4가지로 구성된다.

• 토큰, 즉 말단(terminal) 기호들: 더 이상 분해 불가능하고 생성 규칙의 오른쪽에만 위치한다.
• 비말단(nonterminal) 기호들: 생성 규칙의 왼쪽에 위치하며 생성 규칙의 왼쪽에도 위치할 수 있다.
• 생성 규칙들: 비말단을 토큰열이나 좀더 말단에 가까운 비말단으로 분해하는데 사용한다.
• 출발 기호: 문장 전체를 가리키는 최상위 비말단이다.

문맥 자유 문법은 출발 기호로 시작해 비단말을 생성 규칙을 이용해 오른쪽으로 치환하는것을 반복하면서 말단인 토큰열을 만들어 나간다. 이때 만들어진 토큰열들을 자유 문법으로 정의된 언어라고 한다.

우리가 만들 infix to postfix 컴파일러에서 사용할 문맥 자유 문법을 통해 그 예시를 알아보자. 먼저 9-5, 2-1, 8+1-4 같이 간단히 더하기 빼기로 이루어진 중위식을 다루게 되는데 이 식을 설명해 보자면 "덧셈이나 뺄셈 연산자로 분리한 숫자의 나열"이라고 할 수 있고 이는 다음의 생성 규칙으로 표현되고 있다.

- list -> list + digit
- list -> list - digit
- list -> digit
- digit -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

위 생성 규칙에서 +, - 기호와 0~9 까지의 십진수는 말단이고 분해 가능한 list와 digit는 비말단이다. 또한 list는 최상위 생성 규칙의 왼쪽에 위치하는 비말단이기 때문에 출발 기호이기도 하다.

파스 트리 (parse tree)

파스 트리는 문법의 생성 규칙을 가지고 시작기호가 어떻게 토큰열을 만들어 가는지를 표현한다.

예를 들자면 생성 규칙 list -> list + digit이 있으면 이에 대한 파스 트리는 list란 노드가 list, +, digit을 자식 노드로 가지는 트리로 표현된다.

[그림 1]

문법이 주어졌을 때 그에 대한 파스 트리의 특성은 다음과 같다.

1. root 노드는 출발 기호이다.
2. leaf 노드는 토큰이다.
3. root와 leaf 사이에 있는 노드들은 비말단이다.

4. 한 노드에 대해 자식 노드들은 한 노드를 왼쪽으로 삼는 생성 규칙의 오른쪽이다.

문법으로 만들어진 언어는 이러한 파스 트리를 이용해서도 정의할 수 있기 때문에 언어란 파스 트리에 의해 시작 기호로부터 만들어진 문자열이라고 할 수 있다.

이때 주어진 토큰열에 대해 생성 규칙을 가지고 적절한 파스 트리를 구성하는 것을 파싱이라고 한다.

아까전 예시로 돌아가 파스 트리를 가지고 9-5+2 라는 식을 분석하는 파스 트리를 구성해보자.

1. • 9는 digit이고 생성 규칙 list -> digit을 이용해 list이다.
   • 9를 자식으로 가지는 digit 노드를 생성하고 그 digit을 자식으로 가지는 list 노드를 생성한다.
2. • 9는 list이고, 5는 digit이기 때문에 9-5는 생성 규칙 list -> list - digit을 이용해 list 가 된다.
   • list 노드와 - 노드 그리고 5를 자식으로 가지는 digit노드를 자식으로 가지는 list 노드를 생성한다.
3. • 9-5는 list이고 2는 digit 이기 때문에 9-5+2는 생성 규칙 list -> list + digit을 이용해 list가 된다.
   • list 노드와 + 노드 그리고 2를 자식으로 가지는 digit 노드를 자식으로 가지는 list 노드를 생성한다.

위의 과정을 파스 트리로 나타내면 다음과 같다.

[그림 2]

모호성(Ambiguity)

이제까지는 어떤 토큰열이 주어졌을 때 이를 가지고 파스 트리를 구성하는것을 알아보았다. 그러나 여기에서 주의할 점이 있는데 하나의 파스 트리는 하나의 토큰열만을 만들지만 하나의 토큰열이 하나의 파스 트리만을 만들지 않는다는 것이다. 이렇게 한 토큰열로부터 여러가지 파스 트리를 만들수 있는 문법을 모호하다 라고 하는데 이 경우 토큰열이 여러 의미를 가지게 되어 컴파일러의 해석이 어렵게 되기 때문에 실제로 컴파일러를 만들 때에는 모호성을 없애야 한다.

다음은 이전 예제에 있던 문법을 고쳐 만든 모호성을 가진 문법의 예시이다.

- string -> string + string 
- string -> string - string
- string -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

9-5+2 같은 식에 이 문법을 사용할 경우 이전과는 달리 다음과 같이 여러가지 파스 트리를 가지게 된다.

[그림 3]

연산자의 연관성

우리는 9-5+2 와 같은 식을 계산을 할때 자연스럽게 왼쪽에 있는 9-5를 우선으로 계산하고 + 2 를 나중에 계산하며 왼쪽에서 오른쪽으로 계산한 것이다. 이처럼 여러개의 연산자가 한 식에서 나타날 때 어떤 순서로 처리하는지 나타내는 규칙을 연산자의 연관성이라고 하며 왼쪽 연관성과 오른쪽 연관성이 있다.

왼쪽 연관성

• 1+2+3: 2 양쪽에 + 연산자가 있는데 + 연산자는 왼쪽 연관성을 가지기 때문에 (1+2)+3 처럼 왼쪽 먼저 계산된다.

다음은 왼쪽 연관성을 나타내는 문법의 예시이다.

- expr -> expr + digit | expr - digit
- digit -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

이를 트리로 나타내면 왼쪽 연관성은 왼쪽으로 깊어지는 트리를 가지게 된다.

[그림 4]

오른쪽 연관성

• a=b=c: b 양쪽에 = 연산자가 있지만 = 연산자는 오른쪽 연관성을 가지기 때문에 a=(b=c) 처럼 오른쪽 먼저 계산된다.

다음은 오른쪽 연관성을 나타내는 문법의 예시이다.

- right -> letter = right 
- letter -> a | b | ... | z

이를 트리로 나타내면 오른쪽 연관성은 오른쪽으로 깊어지는 트리를 가지게 된다.

[그림 5]

연산자들의 우선 순위

이제까지는 더하기와 빼기만 있는 식으로만 예를 들어 보았다. 그런데 곱하기나 나누기가 들어가면 연산자의 연관성만으로는 파스 트리가 여러가지 생기는걸 막을 수 없다.

[그림 6]

그런데 우리는 자연스럽게 연산자의 연관성을 아는것처럼 곱하기나 나누기를 먼저 계산해야 한다는 것을 알고 있다. 이처럼 어떤 연산자를 먼저 계산할지를 정하는 것을 연산자의 우선 순위라고 한다.

수식을 위한 구문

이제 앞에서 알아본 자유 문법과 파스 트리, 그리고 연산자의 연관성과 우선 순위를 통해 곱하기, 나누기, 더하기, 빼기로 이루어진 중위식을 후위식으로 바꾸는 컴파일러의 문법을 작성해보자.

먼저 우리가 다룰 4개의 연산자간의 연관성과 우선 순위를 정의해보자. 다음 표에서는 아래에 있을수록 우선 순위가 높아진다.

우선 순위	연관성
낮음	왼쪽	+	-
높음	왼쪽	*	/

앞서 정의된 표를 문법으로 나타내기 위해 두개의 비단말 expr과 term을 사용하고 기본 단위를 위해 비말단 factor를 사용한다. 제일 말단에 가까운(우선순위가 가장 높은) factor 부터 정의해보자. factor는 기본 단위이기 때문에 한자리의 숫자나 가로로 둘러싸인 수식을 뜻한다. 이를 생성 규칙으로 쓰면 다음과 같다.

factor -> digit | ( expr )

다음은 factor 다음으로 높은 우선 순위를 가지고 계산되는 곱셈과 나눗셈에 대한 생성 규칙이다.)

- term -> term * factor | term / factor | term

마지막으로 계산되는 덧셈 뺄셈을 담당하는 expr을 통한 최종 문법은 다음과 같다.

- expr -> expr + term | expr - term | term
- term -> term * factor | term / factor | factor
- factor -> **digit** | ( expr )

이 문법은 연산식은 +와 - 연산자로 묶인 여러개의 term 들로 이루어지고 그 term 들이 *와 / 로 묶인 여러개의 factor로 구성된다는 것을 잘 표현하고 있다.

이때 이 문법을 이용해 파스 트리를 나타내면 루트 노트(시작 기호)에 가까워질수록 우선순위가 낮은 연산자가 위치하는 것을 볼 수 있다. 다시 말해 말단에 근접할수록 우선순위가 높은 연산자가 위치한다는 것이다.

다음 포스트에서는 구문 중심 번역에 대해 다루겠다.