[Compiler Design] Syntax Derivation

 

 

 

 

Lexical Analysis의 결과로 lexeme을 얻고, 이걸 가져다가 문장을 이해하는게 구문분석기의 역할이다.

문법이 제대로 작성했는지 확인하고, 각 단어의 역할을 확인하기 위해 트리를 구성한다.

 

Lexical Analysis에서는 정규표현식으로 패턴을 기술했고, 그 패턴에 맞는 Lexeme을 찾아 Token을 만들었다.

Syntax Analysis에서는 Lexical Analysis에서 넘겨준 토큰의 순서가 문법에 맞는지 검사하는데..

 

우선 그걸 위해 문법을 기술해야 한다. Context Free Grammar를 사용한다.

정규표현식은 상태 수가 유한할 때만 사용할 수 있는데, 상태가 몇 개인지 알 수 없다.

 

이건 무한하게 깊어지는 중첩 구조를 처리할 수 없는 유한상태머신의 한계이기도 하다. ex) 괄호 짝 맞추기 

언어 정의 전 상태의 개수를 고정한다면 가능한데 그게 안되니까..

 

 

 

 

 

프로그래밍언어개론에서 다 했던내용.. Bankus-Naur Form으로 문법을 기술한다. 

사진에 보이는 ANTLR 문법도 일종의 BNF 이다. 

 

BNF로 문법을 정의하고, 입력이 기술한 문법에 일치하는지 확인하는 작업을 Syntax Analysis 에서 수행한다.

 

 

 

문법에 맞는 문장이라고 무조건 말이 되지는 않는다.

Syntax Analysis 이후 Semantic Analysis를 통해 이 문장이 실제로 어떤 의미인지 파악할 수 있어야 한다. 

 

문법에 맞는 문장인지 확인할 때는 Derivation을 사용한다. 

말 그대로 문법을 바탕으로 문장을 생성하는걸 유도라고 한다.

 

문법     E → E + E | E * E | (E) | a

언어     (a+a)

유도      E ->(E) -> (E+E) -> (a+E) -> (a+a)

 

문법으로 언어를 유도할 수 있으면 문법에 맞는 문장이다. 

 

유도 시 Nonterminal에 문법을 적용하는 순서가 다를 수 있다. 

가장 왼쪽에 있는 Nonterminal에 먼저 문법을 적용하면 좌측유도, 제일 오른쪽에 있는 Nonterminal에 먼저 문법을 적용하면 우측유도.

 

좌측유도는 사람이 직접 구현할 때 많이 쓰고.. 우측유도는 실제 Parser를 구현할 때 사용된다.

근데 어떻게 하든 같은 Parse Tree를 얻을 수 있다. 그냥 구현 전략의 차이. 

 

특정 입력에 대해 유도 트리가 2개 이상 나온다면 모호한 문법이다.

트리가 다르면 의미가 다르다는걸 의미하고, 모호함을 해결해야 한다. 

 

 

 

 

연산자의 우선순위를 도입해서 동일한 문법을 구현할 수 있다.

연산자 마다 새로운 Non-Terminal을 도입하고, 시작 Symbol과 가장 가까운 쪽에 연산자 우선순위가 낮은 문법을 두자.

+ 연산은 * 보다 우선순위가 낮으니 시작 심벌 E와 가까운 쪽에 Non-Terminal T를 도입했다. 

 

 

 

 

Parser로 구문을 분석한다.

주어진 문자열이 정의된 문법에 의해 생성될 수 있는지를 확인한다.

올바른 문장이라면 문장 구조 (트리) 를 반환하고, 올바르지 않은 문장이라면 오류 메세지를 반환한다. 

 

Parse Tree는 문장 구조를 나타내는 트리로, 유도 트리와 같은 형태를 가진다.

 

 

 

 

 

 

Top-Down 방식은 루트 노드로부터 시작해서 단말노드를 생성하면서 확인하는 방식이다.

좌측유도와 같은 순서로 생성규칙을 적용한다. (Left Parse)

 

Bottom-Up 방식은 단말 노드로부터 시작해서 루트 노드를 향하여 위로 생성하면서 확인하는 방식이다.

우측유도 생성규칙을 역순으로 적용한 결과와 같다. (Right Parse)

 

 

좌측유도 (Leftmost Derivation) - 문법 규칙 적용 시 가장 왼쪽에 있는 Non-Terminal부터 차례대로 치환

우측유도 (Rightmost Derivation) - 문법 규칙 적용 시 가장 오른쪽에 있는 Non-Terminal부터 차례대로 치환 

 

TopDown - 트리의 루트 노드인 시작 심벌부터 시작해 아래로 내려가며 입력 토큰과 일치시킨다

BottomUp - 트리의 리프 노드인 입력 토큰부터 시작해 문법을 거꾸로 적용하며 루트에 도달한다

 

LL 파싱 - 좌측유도 + TopDown + 좌파스

LR 파싱 - 우측유도의 역순 + BottomUp + 우파스 

 

LL 파싱과 LR 파싱은 Syntax Analysis 에 속한다. 일단 AST를 만든 후에 Semantic Analysis를 수행한다.

모호한 문법이 있다면, Syntax Analysis 단계에서 반드시 해결되어야 한다.