구문 분석

이 글은 <컴파일러 입문> (저자: 오세만)을 참고하여 만들어졌습니다.

 

구문 분석이란 주어진 입력이 올바른 프로그램인가를 검사하고 다음 단계에서 필요한 정보를 구성하는 과정이다.

이와 같은 작업을 수행하는 컴파일러의 단계는 구문 분석기(syntax analyzer)이다. 

구문 분석기는 간단히 파서(parser)라 부르며, 스캐너에 의해 생성된 토큰을 입력으로 받아 문법적인 검사를 한 후에 다음 단계인 중간 코드 생성기가 효과적으로 중간 코드를 생성할 수 있는 형태의 정보를 구성하여 출력한다.

 

6.1 구문 분석 방법

유도 트리(derivation tree) : 구문 분석기의 출력으로 생성되는 트fl

=> 이 트리가 구문 분석기에 의해 생성될 때는 파스 트리(parse tree)

 

Context-free 문법을 위한 구문 분석 방법은 파스 트리를 어떤 순서로 만들어 가느냐에 따라 

top-down 방식과 bottom-up 방식으로 구분할 수 있다.

 

• Top-down 방식은 루트 노드(root node)로부터 시작하여 단말 노드(terminal node)로 만들어 나가는 반면에
• bottom-up 방식은 단말 노드로부터 루트 노드를 향하여 위로 만들어 나간다.

이때 입력 스트링은 두 방식 다 한 번에 한 심벌씩 왼쪽부터 오른쪽으로 검조(left to right scanning)한다.

 

또한, 구문 분석 과정을 유도 과정에 의해 나타낼 수 있는데 각각 좌측 유도와 우측 유도의 순서를 따른다.

• Top-down 방식은 좌측 유도와 같은 순서의 생성 규칙이 적용되며
• bottom-up 방식은 우측 유도의 역순, 즉 우파스와 동일한 순서의 생성 규칙이 적용된다.

 

Top-down 방식은 시작 심벌(S)로부터 정의된 문법의 생성 규칙을 적용하여 유도 과정에 의해 주어진 스트링(w)과 같은 문장을 찾는 과정으로 나타낼 수 있다.

 

• 시작 심벌로부터 생성 규칙을 적용하여 유도를 해 나가면서 주어진 스트링을 생성할 수 있으면 올바른 문장이고 그렇지 않으면 틀린 문장으로 처리하는 방법이다.
• 유도 과정 중 어떤 생성 규칙이 적용되었을 때 그 번호를 출력하거나 또는 서브트리를 만들어 나간다.
• 즉, top-down 방법은 입력 스트링에 대한 좌측 유도 과정을 찾는 시도로 간주될 수 있으며 마찬가지로 루트 노드로부터 차례로 주어진 입력 스트링에 대한 파스 트리를 구성하는 방법으로 생각할 수 있다.

 

시작 심벌로부터 생성 규칙을 적용하여 문장을 유도해 나갈 때, 즉 문장 형태에서 나타난 nonterminal을 계속 대치해 나갈 때, 그 nonterminal에 대한 생성 규칙이 여러 개 있으면 어떤 생성 규칙을 적용해야 되는지는 비결정적(nondeterministic)이다.

그러나 문법이 어떤 특정한 조건을 만족한다면 결정적으로 생성 규칙을 선택할 수 있고, 주어진 문장이 옳은지를 입력 길이의 선형 시간(linear time)에 판단할 수 있다.

 

Bottom-up 방식은 주어진 스트링(w)으로부터 시작하여 문법의 시작 심벌(S)로 축약시키는 구문 분석 방법이다.

• 어떤 문장 형태(sentential form)에서 특정한 생성 규칙의 rhs(right hand side)를 찾아 lhs(left hand side)로 바꾸는 것을 reduce한다고 말한다. 
• 따라서 bottom-up 방법은 주어진 스트링으로부터 차례로 reduce를 반복하여 시작 심벌로 갈 수 있으면 올바른 문장이고 그렇지 않으면 틀린 문장으로 간주한다.
• Bottom-up 구문 분석에서, reduce 될 때 만들어지는 일련의 생성 규칙 번호를 reduce sequence라 하며 이것은 우측 유도 과정에서 적용된 생성 규칙 번호의 역순이 된다. 
• 또한, reduce될 때마다 서브트리를 만들어 전체적인 파스 트리를 구성할 수 있다.

Bottom-up 방식에서는 문장 형태에서 생성 규칙의 rhs를 찾아 그것을 lhs로 reduce한다.

=>핵심은 문장 형태에서 어떻게 rhs를 찾을 것인가 하는 것과 같은 rhs를 갖는 생성 규칙이 여러 개 있을 때 어떤 생성 규칙을 적용할 것인가 하는 점이다.

 

6.2 구문 분석기의 출력

구문 분석을 수행하는 구문 분석기(syntax analyzer)는 입력으로 스트링 w를 받아 만일 w가 정의된 문법의 문장이라면 구문 분석 정보를 생성하고 w가 정의된 문법의 문장이 아니라면 에러 메시지(error message)를 출력하는 작업을 한다.

다시 말해, 주어진 스트링이 정의된 문법에 의해 생성될 수 있는지의 여부를 결정하는 과정으로 올바른 문장에 대해서는 다음 단계에서 필요한 구문 분석 정보를 출력으로 내는데 다음과 같은 기능을 나타낸다.

=> 구문 분석기의 출력은 다음 단계인 중간 코드 생성의 입력이 된다.

 

6.2.1 파스

유도 과정을 통하여 주어진 스트링이 올바른 문장인가를 검사할 때 좌측 유도 과정을 적용하는 방법과 우측 유도 과정을 적용하는 방법이 있다.

이때 유도 과정에서 적용된 일련의 생성 규칙 번호를 파스라 하며,

파스의 종류에는 좌측 유도 과정에서 생성된 좌파스(left parse)와 우측 유도 과정에서 적용된 생성 규칙 번호의 역순인 우파스(right parse)가 있다.

 

이와 같은 좌파스 또는 우파스가 구문 분석기의 출력으로 나올 수 있으며, 일반적으로 top-down 방법일 때는 좌파스가 생성되고,  bottom-up일 때는 우파스가 생성된다.

그러면 구문 분석기의 다음 단계인 중간 코드 생성에서는 각 생성 규칙에 결합된 행동 코드(action code)를 파스에 따라 실행하거나 또는 파스를 이루는 생성 규칙이 구해질 때마다 그에 해당하는 행동 코드를 실행한다.

 

6.2.2 파스 트리

파스 트리(parse tree)는 올바른 문장에 대해 구문 분석기가 그 문장의 구조를 트리 형태로 나타낸 것으로 

루트 노드, 중간 노드, 단말 노드로 구성되는데 루트 노드는 문법의 시작 심벌이고, 중간 노드는 각 생성 규칙의 좌측  nonterminal에 해당되며, 단말 노드는 주어진 스트링을 생성하는 terminal 심벌들이 된다. 

 

파스 트리는 주어진 스트링에 대해 형태는 같지만 구문 분석 방법에 따라 구성되는 순서가 다르다. Top-down 방식은 루트 노드로부터 생성 규칙이 적용되어 직접 유도될 때마다 트리가 구성되며, bottom-up 방식은 주어진 문장으로부터 생성 규칙이 reduce될 때 서브트리가 만들어진다.

 

주어진 스트링을 구문 분석하여 구성된 파스 트리의 형태가 2개 이상 생길 수 있다.

파스 트리가 2개 생긴다는 것은 주어진 스트링을 결정적으로 구문 분석할 수 없다는 것을 의미한다.

즉, 구문 분석하는 과정 중에 어떤 생성 규칙을 적용하여 구문 분석을 해야 할지 판단할 수 없어서 더 이상 구문 분석할 수 없게 된다.

 

연산자 +와 *에 대한 연산 순서는 + < *이므로 위 파스 트리 중 1번이 이에 해당하는 트리가 된다. 

이 말은 스트링 id + id * id에서 입력 심벌이 *인 경우에, 곱셈이 덧셈보다 순위가 높으므로 구문 분석 시 id * id를 먼저 처리하고 덧셈에 관한 부분은 나중에 계산하는 것을 의미한다.

 

그러나 2번의 파스 트리는 곱셈에 관한 부분을 처리하기 전에 덧셈 부분을 먼저 처리하므로 +가 *보다 순위가 높은 경우가 된다.

따라서, 주어진 스트링을 결정적으로 구문 분석하기 위해서는 단지 한 개의 파스 트리가 생성되어야 하므로 2번과 같이 바람직하지 못한 트리는 버려야 한다.

 

6.2.3 추상 구문 트리

• 파스 트리가 구문 분석의 결과로 문법 구조(syntactic structure)에 관한 정확한 정보를 갖고 있으나 
• 파스 트리의 중간 노드에서 표현되는 nonterminal은 단지 문법적인 정보만을 위한 것으로 구문 분석 다음 단계인 코드 생성 단계에서는 아무런 의미가 없고 구문 분석 시간의 지연과 트리가 차지하는 기억 공간의 낭비만 초래할 뿐이다.
• 또한 문법 항목을 구별하기 위한 구분자나 지정어 등도 이미 구문 검사가 끝난 후에는 아무런 의미가 없다. 
• 따라서 중간 코드 생성 단계에서는 이와 같은 불필요한 정보를 제거한 트리가 더 효과적이다.

 

추상 구문 트리(AST: Abstract Syntax Tree)는 파스 트리의 변형된 형태로 코드 생성 단계에서 꼭 필요한 의미 정보(semantic information)만을 갖는 트리이다.

따라서, 추상 구문 트리는 파스 트리보다 소스 프로그램에 대한 의미정보를 훨씬 효율적으로 나타낼 수 있다.

 

* 추상 구문 트리를 때때로 구문 트리(syntax tree)라고 부르기도 한다.

 => 하지만 좀 더 정확히 말하자면 소스 프로그램에 대한 의미적 내용을 표현하고 있기 때문에 의미 트리(semantic tree)라고 부르는 것이 타당하다.

 

추상 구문 트리의 비단말 노드는 의미있는 생성 규칙의 이름이 되며 단말 노드는 의미있는 termianl 심벌이 된다.

의미 있는 생성 규칙과 의미있는 terminal 심벌은 모두 컴파일러를 구현하는 사람(compiler implementor)이 결정하며 코드 생성 단계에서 필요한 정보만을 갖도록 지정한다.

 

일반적으로 의미있는 terminal 심벌은 보통 토큰 값(token value)을 갖는 terminal로 명칭과 상수이며,

의미있는 생성 규칙은 특정한 구문 구조를 표현하고 있는 생성 규칙으로 다음 단계인 중간 코드 생성 단계에서 트리를 운행하면서 중간 코드를 쉽게 생성할 수 있도록 고안한다.

 

프로그래밍 언어의 일반 문장에 대해서도 모두 추상 구문 트리를 설계할 수 있다.

또한 역으로 고안된 트리 형태를 갖도록 문법에서 명시할 수 있다.

 

 

Bottom-up 구문 분석 방법에서 파스 트리는 주어진 스트링에 속하는 모든 terminal들에 대해서 단말 노드를 만들고 reduce가 일어날 때마다 새로운 서브트리를 만들어 연결하는데 비하여 추상 구문 트리는 컴파일러 구현자가 지정한 terminal로만 단말 노드를 만들고 의미 있는 생성 규칙으로 reduce할 때 지금까지 만든 자노드들을 한 데 묶어 서브트리를 구성한다.

 

Section 6.3 Top-down 방법

Top-down 방식으로 구문 분석을 한다는 것은 주어진 스트링과 같은 문장을 생성하기 위하여 시작 심벌로부터 생성 규칙을 적용하여 좌측 유도해 나가는 방법이다.

• 좌측 유도 과정에서 생성 규칙이 잘못 적용되었으면 그 생성 규칙에서 보았던 스트링을 다시 검조(scanning)하기 위하여 입력으로 보내고 다른 생성 규칙을 적용하여 유도를 시도한다. (backup, backtracking)
• 한 입력 심벌을 여러 번 반복하여 다루기 때문에 시간이 매우 많이 걸린다.
• 따라서 실제적인 컴파일러의 파싱 알고리즘으로 사용하기 위해서는 효율적인 방법이 필요하다.

이 절에서 우리는 backtracking을 하는 일반적인 top-down 방식(general top-down method)을 구체적으로 살펴보고 이 방식에서 발생되는 문제점과 그 해결책을 생각해보자.

 

6.3.1 일반적인 top-down 방법

일반적인 top-down 방식은 주어진 스트링이 정의된 문법에 의해 인식되는가를 검사하기 위하여 backtracking을 하면서 구문 분석을 하는 방법으로 다음과 같은 과정으로 행해진다.

 

1. 처음에 시작 심벌의 첫 번째 생성 규칙을 적용하여 유도한다.

2. 주어진 입력 스트링과 유도된 문장 형태(sentential form)를 한 번에 한 심벌씩 차례로 비교한다.

    (1)  비교 과정에서 nonterminal이 나오면, 이 nonterminal 심벌의 첫 번째 생성 규칙을 적용하여 유도한다.

    (2) 비교한 두 심벌이 같으면, 계속 비교해 나간다.

    (3) 비교한 두 심벌이 같지 않으면, 생성 규칙을 잘못 적용한 것이므로 현재 적용된 생성 규칙을 제거하고 그 다음 생성 규칙을 적용한다.            이때 입력 심벌의 위치는 제거한 생성 규칙에서 보았던 심벌의 개수만큼 입력으로 되돌려 보낸다.

3. 2번 과정을 반복하다가 더 이상 적용할 생성 규칙이 없으면 입력 스트링을 틀린 문장으로 간주하고, 문장 형태에 나타난 스트링이 입력 스트링과 같아지면 올바른 문장으로 인식한다.

 

결론적으로, 일반적으로 top-down 방법은 backtracking을 하면서 차례로 생성 규칙을 적용하여 주어진 입력 스트링과 같은 스트링에 다다르면 올바른 스트링으로 인식하고 시작 심벌의 맨 마지막 생성 규칙을 적용해서도 같은 스트링이 생성되지 않으면 틀린 스트링으로 판별하는 방법이다.

 

일반적으로 top-down 방식으로 구문 분석할 때 left-recursion이 존재하면 무한 루프에 빠지게 된다.

또한 결정적으로 구문 분석을 하기 위해서는 backtracking을 하지 않아야 한다.

 

6.3.2 Left-recursion

문법이 left-recursive하다는 것은 어떤 a에 대해 A => Aa의 유도 과정이 있는 nonterminal A가 존재하는 경우

=> top-down 구문 분석 시에 같은 생성 규칙이 순환적으로 적용되어 무한 루프에 빠지게 되고 주어진 문장을 구문 분석할 수 없게 된다.

따라서, 문법 변환을 통하여 left-recursion을 제거해야만 한다.

 

Top-down 구문 분석에서 무한 루프에 빠지지 않기 위해서는 left-recursion을 제거해야만 한다.

먼저, 직접 left-recursion을 제거하는 방법을 생각해보자.

직접 left-recursion이 있는 nonterminal 심벌의 일반적인 생성 규칙 형태는 좌 순환이 있는 생성 규칙 + 없는 생성 규칙

 

간접 left-recursion 제거 방법

• 일정한 순서로 nonterminal들을 순서화
• 생성 규칙에서 lhs보다 순서적으로 앞선 nonterminal이 rhs의 첫 번째로 나오는 생성 규칙에서 간접 순환이 발생
• 대입(substitution)기법을 통하여 제거

6.3.3 Left-factoring

Top-down 구문 분석에서 같은 심벌들을 prefix로 갖는 두 개 이상의 생성 규칙이 있을 때 주어진 스트링이 올바른 문장인가를 검사하기 위하여 구문 분석기가 어떤 생성 규칙을 적용해야 할지 결정할 수 없다.

 

if ,구문 분석기가 생성 규칙을 잘못 적용했다면, 그 생성 규칙을 제거하고 다른 생성 규칙을 적용해야 하므로 구문 분석 시간이 오래 걸리고 비효율적이다. 

따라서 구문 분석 결정 과정을 다음 심벌을 볼 때까지 연기함으로써 구문 분석기의 혼란을 막을 수 있다.

즉, 공통 앞부분(common prefix)을 새로운 nonterminal을 도입하여 인수 분해해야 한다.

 

6.3.4 No-backtracking의 조건

결정적으로 구문 분석할 수 있다(deterministic top-down parsing)는 의미는 구문 분석 과정에서 입력 심벌에 따라 nonterminal에 대한 생성 규칙을 결정적으로 선택할 수 있다는 것이며 이 경우에 backtracking을 하지 않게 된다.

그러나, 문법이 left-recursion을 갖지 않고 left-factoring이 되었다고 하더라도 주어진 스트링을 결정적으로 구문 분석할 수 있는 것이 아니다.

좀 더 제약조건이 필요

Top-down 구문 분석에서 정의된 문법이 어떤 조건을 만족하면 주어진 스트링을 결정적으로 구문 분석할 수 있는데 이를 LL조건(LL condition)이라 하며 이 조건을 만족하는 문법을 LL 문법(LL grammar)라고 한다.

 

6.4 Bottom-up 방법

Bottom-up 방법은 주어진 스트링부터 시작 심벌로 축약되어 가는 과정

주어진 스트링이 시작 심벌로 축약될 수 있으면 올바른 문장,  그렇지 않으면 틀린 문장으로 간주

이때 트리를 단말 노드로부터 즉 바닥(bottom)에서 위(up)로 거꾸로 만들 수 있다.

 

 

6.4.1 Reduce

Top-down 방법이 시작 심벌로부터 확장(expand)을 반복하여 주어진 스트링을 생성해 나가는 과정이라면,

bottom-up 방법은 주어진 스트링으로부터 시작 심벌로 축약(reduce)해 나가는 과정이라 생각할 수 있다.

(bottom-up 방법의 핵심은 reduce)

 

즉, 구문 분석 도중에 나타나는 문장 형태의 일부분이 정의된 생성 규칙의 rhs와 같을 경우 이 생성 규칙의 lhs로 대치하는 것을 의미한다.

 

정의된 문법이 모호하지 않다면 모든 우 문장 형태(right sentential form)에 대해 단지 한 개의 handle만이 존재하고 이 handle에 적용할 생성 규칙이 유일하면 주어진 스트링을 결정적으로 구문 분석할 수 있다는 것을 의미한다.

 

6.4.2 Shift-reduce 구문 분석

Shift-reduce 구문 분석은 bottom-up 방법의 일종이다.

이 방법은 스택(stack)과 입력 버퍼(input buffer)를 사용하여 구현할 수 있는데 보통 파싱 스택(parsing stack)이라 부르며

문장 형태에서 handle을 찾을 때가지 필요한 문법 심벌들을 유지하고 입력 버퍼는 주어진 스트링을 보유한다.

=> Shift-reduce 파서의 행동은 shift, reduce, accept, error의 네 가지이며 이와 같은 행동을 스택의 top과 현재의 입력 심벌에 따라 파싱 테이블(parsing table)을 참조하여 결정한다.

 

• Shift 행동은 현재의 입력 심벌을 스택으로 이동하는 것을 의미.
• reduce는 스택 top 부분에 있는 handle을 그에 따른 생성 규칙으로 축약하는 행동
• accept는 주어진 스트링이 문법의 올바른 문장임을 알리는 행동
• error는 현재 보고있는 입력 심벌이 그 상태에서 나타날 수 없기 때문에 틀린 문장

shift 행동은 입력 포인터를 하나 증가하여 다음 심벌을 가리키도록 핟고 현재의 입력 심벌은 스택에 push하는 작업을 수행한다.

• 스택의 top 부분에 handle이 나타날 때까지 계속해서 shift를 행한다.
• handle을 찾으면 그 handle에 해당하는 생성 규칙으로 reduce하여 문법의 시작 심벌에 이를 때까지 반복한다.
• shift와 reduce 행동의 연속으로 이루어지기 때문에 shift-reduce 구문 분석이라 부른다.

여기서 $는 end marker이며, 단계 1에서는 스택에 $, 그리고 입력 버퍼에는 주어진 스트링과 입력의 끝을 나타내는 $ 기호를 첨가하여 넣는다.

이 상태를 초기 상태(initial configuration)라한다.

 

6.4.3 트리 생성

Shift-reduce 구문 분석 방법에서 파싱을 하면서 효과적으로 트리를 생성할 수 있다.

Shift 해동에 단말 노드를 만들고 reduce 행동에 서브 트리를 만들어 전체적인 트리를 구성할 수 있다.

• buildNode(a):  terminal a를 단말 노드로 만든다.
• buildTree(n): 생성 규칙 번호 n에 해당하는 서브트리를 만든다.

1. shift: shift되는 모든 심벌에 대해 단말 노드를 만든다.

2. reduce: reduce가 일어날 때마다 서브트리를 만든다.

3. accept: 현재 구성된 파스 트리를 복귀한다.

4. error: 행동에 대해서는 이제까지 구성한 트리가 아무 의미 없게 된다.