[컴파일러개론] 중간고사 정리 - Syntax Analysis

Syntax Analysis

어휘분석 후 토큰들을 구문분석기(파서)를 이용해 파스 트리를 구성한다.

 

Syntax Analysis와 관련된 질문들

1) 문법을 기술하는 방법

2) input token stream이 기술된 문법에 맞는지 판별하는 방법

 

---

1) 문법을 기술하는 방법

CFG(Context Free Grammar)

표현된 문법으로부터 자동적으로 인식기를 구현할 수 있다.

 

G = (N, T, P, S)

N : non-terminal 심벌 집합 (중간과정 심벌)

T : terminal 심벌 집합

P : 생성규칙 집합

S : 시작 심벌

 

L(G)는 이 문법으로 생성되는 언어

 

정규표현식은 Nested 구조의 구문을 표현하기에 power가 떨어진다.

=> 문법 기술에는 적합하지 않음

 

BNF(Backus-Naur Form)

non-terminal 심벌은 <>로 묶어 표기

 

EBNF(Extended BNF)

메타 심벌 도입

- 반복되는 부분이나 선택적인 부분을 간결하게 표현하기 위한 특수 심벌

{ 수식 } 반복횟수

 

antlr 문법도 일종의 EBNF

 

다음 정규표현식을 CFG로 바꾸어 적으시오.
1. a+

S -> aS | a ( S -> Sa | a)

2. a*

S -> aS | e ( S -> Sa | e)

---

2) input token stream이 기술된 문법에 맞는지 판별하는 방법

유도란 문법에서 언어를 생성해내는 것이다.

구문분석은 언어에서 문법을 확인해 가는 것으로,

유도되는지 보면 된다.

 

유도(derivation)

문법에서 문장을 생성하기

생성 규칙을 연속적으로 적용하여 nonterminal을 확장함으로써 얻는다.

 

- 좌측유도 : 가장 왼쪽에 있는 nonterminal 먼저 대치

- 우측유도 : 가장 오른쪽에 있는 nonterminal 먼저 대치

 

좌측유도, 우측유도의 유도 트리는 같다.

 

---

모호성(Ambiguity)

문법 G에 의해 생성되는 어떤 문장이 두 개 이상의 유도 트리를 갖는다면 문법 G는 모호하다.

=> 문법이 잘못된 것

 

모호성의 해결

같은 뜻을 가지는 동일한 문법을 만들자

 

1. 연산자 우선순위 도입

- 연산자마다 새로운 non-terminal을 도입하되

- Recursion을 left, right 둘 중 하나만 두고,

- 시작심벌과 가장 가까운 쪽에 연산자 우선순위가 낮은 것을 둔다.

 

2. 결합법칙 도입

- Left-Recursion : 좌측결합

- Right-Recursion : 우측결합

 

---

구문분석 방법

구문분석(=파스)

- 유도가되는지 보면 된다.

- 올바른 문장에 대해서는 문장 구조를, 틀린 문장에 대해서는 오류 메시지를 나타낸다.

 

일련의 토큰은 파서를 거쳐 문장 구조가 된다.

 

파스 트리(parse tree)

- 문장 구조를 나타내는 트리

 

 

구문 분석 방법

- Top-down 방식

    루트 노드부터 시작하여 단말노드를 생성하며 확인

    모든 방법을 다 해볼 수 있다.

    좌측유도와 같은 순서의 생성규칙을 적용한다.

    - 좌파스 : 좌측유도 중 적용된 생성규칙들의 리스트

 

- Bottom-up 방식

    단말 노드로부터 루트 노드를 향하여 위로 생성하며 확인

    토큰 하나를 받을 때마다 집을 짓듯이

    우측유도의 역순의 생성규칙을 적용한다.

    - 우파스 : 우측유도 중 적용된 생성규칙들의 리스트의 역순