Pushdown Automata

Pushdown Automata

 

finite automata와 다른 점은 stack symbol T와 ,start symbol of stack z0가 추가되었다는 점이다.

 

문제를 풀 때, δ(q0,주어진 값,z0)로 시작한다.

 

결과가 하나라면 deterministic push-down automata DPDA가 되고

하나 이상이라면 non-deterministic push-down automata NPDA가 된다.

---

 

---

---

Extended Transition Fuction of PDA

 

---

Syntax Analysis

 

스캐너에 의해 생성된 토큰을 입력으로 받아 주어진 문법에 맞는지를 검사하고, 문법에 맞으면 파스 트리를 출력하고 맞지 않으면 에러를 출력

Syntax analysis를 담당하는 도구를 syntax analyzer 혹은 parser라고 한다.

 

Top-down parsing:

입력 문자열을 한번에 한 심벌씩 좌에서 우로 검사(left to right scanning)하면서 루트 노드에서 시작하여 터미널 노드로 만들어나가는 방법이다.

즉, 시작 기호 S로부터 문법의 규칙을 적용하여 leftmost derivation에 의해 주어진 문장을 찾아가는 방법. Left-parse가 생성된다.

 

Bottom-up parsing:

입력 문자열을 한번에 한 심벌씩 좌에서 우로 검사(left to right scanning)하면서 터미널 노드에서 시작하여 루트 노드로 만들어나가는 방법이다.

입력된 문장에서 reduce에 의해 시작 기호를 찾아가는 방법. Right-parse(rightmost derivation의 역순)가 생성된다.

---

Top-down Parsing

시작 기호로부터 생성 규칙에 좌단 유도만을 적용하는 방법으로 구현이 간단하지만 backtracking 문제 때문에 상업적인 용도로는 잘 사용하지 않는다.

 

1. start symbol에 대해 production rule을 적용한다. 이때 production rule이 여러 개 존재하면 첫 번째 rule부터 적용한다. Production rule을 적용할 때마다 부분 파스 트리를 구성해나간다.

2. 생성된 문장 형태의 문자열과 input symbol을 차례로 비교한다.

3. 만약 유도된 문자열과 input symbol이 같으면 계속 비교해나간다.

4. 비교한 두 기호가 같지 않으면 production rule을 잘못 적용한 것이므로 현재 적용된 production rule을 제거하고 다른 production rule을 적용한다. 이때 input symbol의 위치는 제거한 production rule에서 보았던 기호의 개수만큼 뒤로 이동하는데 이를 backtracking이라고 한다.

5. 이와 같은 과정을 반복한다.

6. 더 이상 적용할 production rule이 없으면 주어진 문장을 주어진 문법에 올바르지 않은 문장으로 인식하고 에러 메시지를 출력한다.

7. 만약 생성된 문자열이 주어진 문자열과 일치하면 올바른 문장으로 인식하고 파스 트리를 출력한다.

---

총 backtracking이 두번 발생하였다. 매우 안좋은 현상이다.

---

Developing Top-down Parsing

결론적으로 일반적인 하향식 구문 분석은 역추적을 하면서 차례로 생성 규칙을 적용한다.

이때 주어진 문자열과 같은 문자열을 생성하면 올바른 문장으로 인식하고, 시작기호로부터 모든 생성 규칙을 적용해도 주어진 문자열과 같은 문자열이 생성되지 않으면 주어진 문자열이 주어진 문법으로부터 생성될 수 없는 문장이라고 판단하여 에러 메시지를 내보낸다.

 

이 과정에서 생성 규칙이 잘못 적용되어 주어진 문자열을 생성할 수 없으면 그 생성 규칙에서 보았던 문자열을 다시 scan하기 위해 입력으로 보내며 다른 생성 규칙을 가지고 유도를 시도한다.

 

Backtracking회피:

top-down parsing에서는 문법에 제약 조건을 붙여서 deterministic한 구문분석이 가능하다.

이런 제약 조건을 LL조건(LL condition)이라 한다. LL 조건을 만족하는 문법을 LL 문법이라 하며, LL 문법으로 top-down parser를 만들어 syntax analysis을 하는 방법을 LL parsing이라 한다.

 

LL Parsing:

주어진 문자열과 같은 문장을 생성하기 위해 현재의 input symbol를 보고 적용될 생성 규칙을 결정적으로 선택하여 유도.

현재의 input symbol와 생성된 터미널 기호가 같지 않으면 주어진 문장을 틀린 문장으로 간주한다.

 

LL Condition:

유도 과정에서 나타난 문장 형태에서 논터미널을 대체하는 생성 규칙을 deterministic하게 선택하기 위한 조건

FIRST와 FOLLOW를 이용한다.