[컴개/CI] 구문 분석

앞서 코드가 어떻게 컴파일 되는지에 대해 설명한 적이 있는데, 다시 한 번 복기하겠다.

컴파일러는 소스코드를 어휘분석기를 거치고, 구문분석기를 거친 후, 의미분석기

총 세 단계에 걸쳐 추상구문트리(AST)를 만들어 낸다.

이번 시간에는 구문 분석에 대해 알아보도록 하겠다.

 

구문 분석(Syntax Analysis)

구문 분석은 어휘 분석을 통해 나온 토큰에 대해

각 토큰들을 조합하여 해당 토큰들의 역할을 확인한다.

위 그림은 어휘분석기를 통해 파싱된 토큰들을

구문분석기에 넣어 파스트리를 만드는 모습이다.

각 토큰들이 조합되어 어떤 의미를 가질 수 있는지를 보여준다.

 

코드말고, 우리의 언어로 되어 있는 예시를 보자.

문법이 맞는지 확인하고, 각 단어의 역할을 확인한다.

 

구문 분석할 때, 두 가지의 질문을 던질 수 있다.

1. How to describe the syntax?

   프로그래밍 언어 개발자가 문법을 기술(설명)하는 방법

2. How to determine if the input token stream statisfies the syntax description?

   주어진 토큰들이 기술된 문법에 맞는지를 판별하는 방법

우리는 위 두 가지의 질문에 하나씩 대답하면서 구문 분석에 대해 알아보도록 하자.

 

참고로, 어휘분석(laxical analysis)은 정규표현식으로 기술하고, 상태전이도를 따라가며 판별하였다.

 

문법을 어떻게 기술할까?

구문을 분석할 때에 CFG(Context Free Grammer)를 사용한다.

CFG는 언어의 문법을 정의하는 일반적인 방법으로, 간단하고 이해하기 쉽다.

표현된 문법으로부터 자동적으로 인식기를 구현하능하다.

 

G = (N, T, P, S)로 표현하는데, 각 의미를 알아보자.

N = non-terminal 심벌 집합을 의미한다. (중간 과정 심벌)

T = terminal 심벌 집합을 의미한다. (토큰과 비슷하다.)

P = 생성 규칙의 집합이다. V -> α, where V ∈ N, α ∈ (V U T)*

S = 시작 심벌을 의미한다.

L(G) = 이 문법으로 생성되는 language

 

다음으로는 문법 심벌들의 일반적인 표기법에 대해 알아보도록 하겠다.위에서 언급한 각 의미를 자세히 파고 든다는 소리이다.

 

Terminal Symbol(T)

a, b, c와 같은 알파벳 시작 부분의 소문자롸 숫자 0, 1, 2, ..., 9+, - 와 같은 연산자 기호, 세미콜론, 콤마, 괄호와 같은 구분자'if', 'then'과 같이 따옴표 사이에 표기된 문법 심벌 (token)

 

Nonterminal Symbol(N)

A, B, C와 같이 알파벳 시작 부분을 대문자로 나타내게 된다.S는 보통 시작 심벌(start symbol)을 나타낸다.<stmt>나 <expr>과 같이 <>로 묶어 나타내기도 한다. (주어, 관형어와 비슷)

 

생성 규칙(P)

 

A -> a1, A -> a2, ...,  A -> a와 같이 생성 규칙의 왼쪽이 모두 A인 경우,

A -> a1 | a2 | ... | ak로 간단하게 표기한다.

위 사진에서 T를 T -> '0' | '1' | '2' (엄밀히 규칙이 3개이다.)로 만들 수 있다.이때 S -> T + T에서 +는 terminal symbol이라고 해석할 줄 알아야 한다.

 

시작 심벌(S)

만약, 아무런 언급이 없다면 첫 번째 생성 규칙의 왼쪽에 있는 것이 시작 심벌이다.

 

그렇다면, 우리는 왜 정규 표현식을 계속해서 사용하지 않고 CFG를 사용할까?

답은 바로 정규 표현식의 표현력 한계에 있다.

정규표현식은 토큰을 기술하기 좋고, DFA로 변환하여 구현하기 좋지만,

Block, expressions, statements 등의 Nested 구조의 구문을 표현하기 어렵다.

괄호(block)의 짝을 맞추는 것도 그 예 중 하나이다.

DFA는 상태의 개수가 유한해야 하기 때문에, 위와 같이 무한하게 만들 수 없다.

 

다음으로는 CFG를 어떻게 표기할 수 있는지 보자.

BNF(Backus-Naur Form)

nonterminal symbol은 <와 >로 묶어서 표기한다.

terminal symbol은 문자(스트링)으로 표기한다.

예)

<id> ::= <letter> | <id><letter> | <id><digit>

<letter> ::= a | b | c | ... | y | z

<digit> ::= 0 | 1 | 2 | ... | 8 | 9

 

EBNF(Extended BNF)

메타 심벌(특수 심벌)을 도입하여 반복되는 부분이나 선택적인 부분을 간결하게 표기한다.

ex)

<id> ::= <letter>{<letter><digit>}07

<letter> ::= a | b | c | ... | y | z

<digit> ::= 0 | 1 | 2 | ... | 8 | 9

위 07 메타 심벌을 통해 해당 부분이 7번 반복됨을 알려준다.

 

아래 사진은 ANTLR 문법으로 작성되었으며, 일종의 EBNF라 할 수 있다.

 

문법에 맞는지 어떻게 판별할까?

주어진 input token stream이 기술된 문법에 맞는지 판별하는 법에 대해 알아보겠다.

가장 먼저 문법과 언어에 대해 알아야 하는데,

앞서 들었던 예제를 다시 들어 보면,

문법은

S -> <주어구> <동사구>

<주어구> -> <관형구> <진주어>로 나타낼 수 있고,

위의 문법으로부터 유도된 언어가

"똑똑한 3학년이 모였습니다."가 될 수 있다.

 

유도(derivation)

문법에서 문장(언어)을 생성하는 과정을 유도라고 한다.

생성 규칙을 연속적으로 적용하여 non-terminal을 확장함으로써 얻을 수 있다.

예를 들어 보자.

E -> E + E | E * E | (E) | a인 문법이 있다. (a + a)를 유도할 때,

E => (E) => (E + E) => (a + E) => (a + a)로 유도할 수 있다.

이러한 유도 경로를 추상화(detail 제거)시켜 유도 트리로 표현할 수 있다.

 

non-terminal symbol의 대치 순서

생성 규칙의 -> 다음에 하나 이상의 non-terminal symbol이 올 경우

어떤 것부터 유도할 것인지 결정해야 한다.

 

- 좌측 유도(leftmost derivation)

가장 왼쪽에 있는 non-terminal을 먼저 대치한다.

좌측부터 글씨를 쓰는 우리나라에서 가장 자연스러운 유도 방법이다.

 

- 우측 유도(rightmost derivation)

가장 오른쪽에 있는 non-terminal을 먼저 대치한다.

좌측 유도와 우측 유도는 유도 트리가 같은데,

이 전제는 '문법이 모호하지 않은 경우'에만 해당한다.

모호한 문법과 모호하지 않은 문법은 다음 포스트에서 설명하겠다.