[컴파일러] 구문분석, Top down과 Bottom up

구문분석

어떤 문자열(문장)이 정의된 문법에 의해 생성될 수 있는지의 여부를 결정하는 과정이다.

일련의 token들은 구문분석기(parser)를 통해 문장구조가 파악된다.

구문분석이 가능하다는 것은 정의된 문법에 의해 유도가 가능하다는 것이다. 구문분석 과정에서 계속해서 생성규칙을 적용해나가며 다시쓰기를 반복한다. 그러다가 최종적으로 유도가 되어 구문분석이 된다면 정의된 문법에 대해 "올바른 문장"이라는 것이고, 올바른 문장은 "문장 구조"를 가진다. 구문분석에 실패하면 틀린 문자열이다.

 

문장구조를 나타내기 위한 자료구조는 "파스트리" 그리고 "생성규칙 번호 리스트"가 있다. 

생성규칙 번호 리스트는 유도해나갈 때 적용된 일련의 생성규칙 번호 리스트다. 좌측유도인지 우측유도인지만 알면 이 리스트만 가지고도 파스트리를 만들 수 있다. 

 

 

파스트리

문장구조를 가지면 "문장 구조를 나타내는 트리"인 "파스트리(parse tree)"로 나타낼 수 있다.

파스트리는 유도트리와 같은 모양이다.
파스트리든 유도트리든 어떤 문자열을 생성해나가는 생성 규칙을 적용해나가는 것이기 때문이다.
- 루트노드 (start symbol)
- 중간노드 (생성규칙의 좌측 nonterminal symbol)
- 단말노드 (terminal symbol, 즉 token)

 

++ cf. 유도와 구문분석

구문분석이 유도랑 비슷하고 트리도 같다고는 하지만, 생각하는 방향은 서로 반대다.

유도는 Start부터 terminal까지 내려가는 관계에 집중을 하지만,

구문분석은 "주어진 문장이 있을 때" terminal에서부터 "어떻게 파스트리를 만들어 낼 것인가"를 생각한다.

 

 

++ recall : 유도

start symbol로부터 문자열을 유도한다는 것은 일련의 생성규칙을 적용해나가며 문자열을 완성시키는 것이다. 즉, 유도 과정에서 일련의 생성 규칙 번호가 발생한다. 좌측 유도와 우측 유도의 생성 규칙 번호는 다르다.

 

 

---

구문분석의 두 가지 방법

 

Top down과 Bottom up이 있다. 무엇이 좋은지 답은 없다. 

java의 구문분석기 antlr는 Top-down을 사용하고, 

근본 구문분석기인 lex기반은 bottom-up을 사용한다.

 

:: Top down ::

Top down은 시작심벌로부터 그냥 유도를 해보는 방식이다. 직관적이다! 좌측유도 기반으로 어떤 생성규칙을 적용하다가 막히면 다른 생성규칙을 적용해보는 방식이다.

좀 더 자세히 말하자면, 어떤 nonterminal에 대해 생성규칙을 적용할 때는 가장 첫번째 생성규칙 먼저 유도해나간다. 그렇게 새로운 문자열을 유도해나가는데, 입력 문자열이 안 만들어지면 backtracking하며 모든 방법을 다 적용해보는 것이다.해보다가 트리 만들어지면 오케이, 끝까지 트리 못 만들면 오류발생!

그런데 backtracking은 top down 방식에서 큰 오버헤드가 될 수 있으며, top down 방식의 큰 단점이다. 재수 없을 경우 컴파일이 너무 오래 걸릴 수도 있다. 이런 오버헤드를 극복한, 즉 backtracking이 없는 Top down 파싱 방법인 LL파싱이 존재한다. 

* LL파싱

1. LL파싱의 의미 : Left to right scanning & Leftmost Derivation 즉 좌에서 우로 읽으며 좌측유도를 통해 좌파스를 생성하는 구문분석 방법이다.

2. backtracking이 없다는 장점

단순한 Top down 방식과 다르게 backtracking이 없는 이유는, 하나의 입력 문자에 대해서 단 하나의 생성 규칙만 적용되게 하기 때문이다. 이를 "결정적으로(deterministic) 파싱"한다고 한다. 결정적 구문 분석을 가능하게 하는 이유는 문맥 자유 문법에 LL조건을 붙이기 때문이다. First set과 Follow set을 사용하여 생성규칙을 선택하도록 하여 결정적인 구문 분석을 가능하게 한다. (참고)

예를들어 인풋으로 문자 a가 들어왔다고 하자. 만약 다음의 생성규칙 S→aAd, S→aB 두개가 존재한다면 "파싱 불가능 하다." 다시 말해 LL파싱은 입력문자:생성규칙이 일대일로 매치되는 깔끔한 입력문자만 파싱 가능하다. 즉 파싱의 범위가 매우 좁다.

∨ 좌파스를 형성한다 : 좌측유도 중 적용된 생성규칙들의 리스트

 

 

:: Bottom up ::

Bottom up은 트리를 만들 때 문자열(token, terminal, 문장)에서부터 올라간다. 적용가능한 생성규칙들을 적용해나가며 시작심벌까지 도착해야 한다. 이때, bottom up을 진행하면 우측유도의 역순의 생성규칙을 적용하게 된다.

∨ 우파스를 형성한다 : 우측유도 중 적용된 생성규칙들의 리스트의 역순

 

어떤 문자열에 대한 구문분석을 할 때,

모호하지 않은 문법이 정의되었다면 Top down방식, Bottom up방식에 의해 생성된 파스트리가 동일하다.

 

 

 

---

예제

좌측유도와 우측유도를 공부할 때 봤던 동일한 예제다. 

결론적으로 (좌측, 우측)유도가 되므로 구문분석이 가능한 문자열이 주어진 것이다. 

그럼 구문분석의 결과로 파스트리를 형성할 수 있고, 유도방법(좌,우)에 따라 좌파스와 우파스가 결정된다.

또한 좌파스, 우파스로 인해 형성된 파스트리가 동일하다! (모호하지 않은 문법이 정의된 상태이므로)

 

Let : 

문자열  a + a * a  에 대해

아래와 같은 생성규칙들이 있다.

1. E -> E + T
2. E -> T
3. T -> T * F
4. T -> F
5. F -> ( E )
6. F -> a

 

Then: 

좌측유도

▼ 좌파스 : 12463466

E => E + T  (규칙1)

  => T + T  (규칙2)

  => F + T  (규칙4)

  => a + T  (규칙6)

  => a + T * F  (규칙3)

  => a + F * F  (규칙4)

  => a + a * F  (규칙6)

  => a + a * a  (규칙6)

 

우측유도

▼ 우파스 : 64264631

E => E + T  (규칙1)

  => E + T * F  (규칙3)

  => E + T * a  (규칙6)

  => E + F * a  (규칙4)

  => E + a * a  (규칙6)

  => T + a * a  (규칙2)

  => F + a * a  (규칙4)

  => a + a * a  (규칙6)

 

각 좌파스, 우파스에 따라 파스트리를 그려보면 다음과 같다.

동일한 파스트리가 그려진다.