이번에는 지난 글에서 알아본 컴파일러의 syntax analyzer가 하는 일에 대해서 공부해볼 것이다. syntax란 문법으로 해당 코드가 문법적으로 맞게 작성되었는지를 확인할 수 있다.
우선 프로그래밍 언어를 구성하는 용어부터 알아보자.
- 몇몇의 단어(알파벳)가 모여 문장을 만든다. -> sentence
- 문장들의 집합이 언어가 된다. -> language
- lexeme : 언어를 의미를 가지는 최소한의 단위로 나눈 것.
- token : lexeme의 의미 및 행동
ex) index = 2 * count + 7;
| lexeme | token |
|---|---|
| index | identifier |
| = | assignment operator |
| 2 | int |
| * | multiply operator |
| count | identifier |
| + | add operator |
| 7 | int |
| ; | delimiter |
-
Recognizers
해당 코드가 grammar (문법)에 맞는지를 판단한다. 따라서 grammar 에 대한 정의가 중요하며, 컴파일러의 syntax analyzer가 해당 역할을 수행한다고 생각하면 된다. -
Generators
정의된 문법을 가지고 sentence를 생성하는 것을 의미한다.
Backus-Naur Form
BNF 란, context free 언어를 나타내기 위한 표기법으로, 대표적인 syntax를 기술하기 위한 방법이다.
context free란, 위치에 따라 의미가 변하지 않는 문법을 의미한다. 프로그래밍 언어가 대표적이다.
BNF는 meta-language 로, 다른 언어를 기술하기 위한 언어이다.
BNF는 다음과 같이 구성된다.
G = <N, T, S, P>
Non-terminal : leaf가 아닌 것들. <> 안에 들어가 있다면 non terminal 이다.
Terminal : leaf
Start symbol : 트리의 최상단. 시작 부분.
Production rule : 규칙들의 집합.
지금 이렇게만 보면 무슨 말인지, 하나도 이해가 안될 것이다. 하지만 BNF 자체가 그렇게 어려운 개념은 아니니, 아래의 실제 BNF 구문을 보면 이해하기 쉬울 것이다.
<program> -> <stmts>
위의 구문은 프로그램이라는 non-terminal은 <stmts>로 이루어져 있다는 것이다. non-terminal 이란, 이름 그대로 마지막이 아닌 것으로서 어떤 것의 상위 개념이라고 보면 된다. abstraction 이라고 이해해도 된다.
<stmts> -> <stmt> | <stmts>
우선 위 구문에서 | 의 의미는 or 이다. 따라서 stmts = stmt or stmts 라는 의미인데, 이는 바로 recursion이라는 것이다. 자기가 자기 자신을 호출하고 있기 때문이다. 위와 같은 경우를 right recursion 이라고 한다.
<stmt> -> <var> + <var>
<var> -> const
위의 구문을 살펴보면, stmt = var + var이고, var = const라는 것을 알 수 있다. 마지막에 const는 terminal이고, BNF 구문은 이렇게 끝난 것이다.
<>에 둘러싸여 있지 않으면, terminal이다.
이 BNF 구문을 tree로 그리면 다음과 같다.
두 개의 상수를 더하는 연산을 하는 프로그램이다.
a = b + const를 BNF로 만들면 다음과 같다.
이를 이해하기 쉽게 parse tree로 그리면,
위와 같은 형태가 된다.
지금 같이 BNF가 잘 작성된 경우에는, 이렇게 tree가 하나만 나오게 된다. 하지만, 문법이 모호한 경우에는 tree가 두 가지 이상 생길 수 있다. 즉 하나의 코드를 가지고 두 가지 이상의 의미로 해석할 수 있다는 것이다. 이런 것을 ambuguity grammar 라고 하는데, 이는 다음 포스트에서 다루도록 하겠다.
