Digital Intelligence

FIRST(a) G : context-free 문법 FIRST(α) = {x ∈VT | α-(*)->xβ, β∈V*} 의미: 문자열 α로부터 유도되어 첫 번째로 나타날 수 있는 터미널 기호들의 집합 계산방법 (1) {X} ∈VT , {X} ∈ FIRST(X) (2) X ∈VN, X → aβ , {a} ∈ FIRST(X) X → ε , {ε} ∈ FIRST(X) (3) X → Y1Y2 … Yk FIRST(X)＝FIRST(X)∪FIRST(Y1Y2… Yk) Nullable A -> ε이면 A는 nullable 하다. ring sum Å e Î A이면 AÅB는 A이고, e Ï A이면 AÅB는 ( A - {e} ) È B이다. FIRST(ABC) = FIRST(A) Å FIRST(B) Å FIRST(C) FOLL..

불필요한 기호(useless symbol) 터미널 문자열을 생성할 수 없는 논터미널 기호이거나 시작기호로부터 도달 불가능한(unaccessible)기호. 만약 CFG G=(VN, VT, P, S)의 문법기호에 대하여 S=(*)=> εXβ =(*)=>w, 단 w ∈ VT*와 같은 유도과정이 존재할 때, 기호X는 필요하다(useful)고 한다. 또한 필요한 기호가 아닌 기호를 불필요하다(useless)고 한다. 불필요한 생성규칙(useless production) 불필요한 기호를 가지고 있는 생성규칙 제거방법 1. 터미널 문자열을 생성할 수 없는 논터미널 기호를 가진 불필요한 생성규칙의 제거 2. 시작기호로부터 도달 불가능한 기호를 갖는 생성규칙 제거 1,2 순서로 적용해야 완전한 제거가 가능하다.

좌단유도(leftmost derivation) 의미 : 유도과정의 각 단계에서 문장형태(sentantial form)의 가장 왼쪽에 있는 논터미널 기호를 계속해서 대체(replacement)하는 경우 표현 : =lm=> 이 때 나타나는 문장형태를 좌문장형태(left-sentential form)라 함 좌파스(left-parse) : 좌단유도에 의해 적용된 일련의 생성규칙의 순서. top-down구문분석에 의해 생성됨 우단유도(right derivation) 의미 : 가장 오른쪽에 있는 논터미널 기호를 계속해서 대체하는 경우 표현 : =rm=> 이 때 나타나는 문장형태를 우문장형태(right-sentential form)라 함 우파스(right-parse) : 우단유도에 의해 적용된 일련의 생성규칙의 순서..

푸시다운 오토마타의 7개 구성요소 M=(Q, Σ, T, δ, q0, z0, F) Q : 상태들의 유한집합 Σ : 입력기호들의 유한집합 T : 스택기호들의 유한집합 δ : 전이함수 Q X (∑∪{ε}) X T -> Q X T* q0 ∈ Q : 시작(start state)상태 z0 ∈ T: 스택의 시작기호 F ⊆ Q : 종결상태(final state)의 집합 전이함수δ (q,a,z) = {(p1,r1),(p2,r2),...,(pm,rm)}에서 - m = 1 이면 결정적 푸시다운 오토마타(DPDA:Deterministic Push-Down Automata) - m ≥ 2 이면 비결정적 푸시다운 오토마타(NPDA:Non-Deterministic Push-Down Automata)

- Immediate Left-Recursion : A -> Aα 형태의 생성규칙 - Indirect Left-Recursion : A =(+)=> Aα 형태의 유도과정이 존재하는 경우 문제점 Top-Down구문분석시, 같은 생성규칙이 반복 적용되어 무한루프 제거방법 right-recursion으로 변환함

같은 기호들을 prefix로 갖는 2개 이상의 생성규칙이 존재할 경우, 공통된 prefix를 인수분해하는 것을 left-factoring이라고 한다. 구문분석기가 어떤 생성규칙을 적용해야할 지 결정할 수 없어서, 규칙의 선택값을 순차적으로 재시도하게 되는 현상(backtracking)을 방지하기 위해서 left-factoring을 수행한다. 입력 : 문법 G 출력 : 동일한 left-factoring된 문법 방법 begin repeat Find the production A -> αβ1|αβ2||...|αβn|γ (*γ는 문자열*) Find the longest prefix α ; If α ≠ ε then replace all tha A -> αβ1|αβ2||...|αβn|γ by A -> αA'|γ A..

단일생성규칙(single production, unit production) 오른편이 단 하나의 Non-Terminal로 구성되는 생성규칙을 말한다.CFG G(VN, VT, P, S)가 어떤 A∈ VN에 대하여 A=(+)=>A형태의 유도과정을 가지지 않을 때, cycle-free라고 하며, 만약 G가 cycle-free이며, ε-free, 그리고 불필요한 기호를 가지지 않으면 그 문법은 proper하다고 한다. 제거방법 오른편에 Non-terminal 기호가 한개만 나오는 생성규칙을 찾아서, 그 자리를 다른 생성규칙들로 대체함으로써 제거한다.

ε-생성규칙을 제거하는 방법은 간단하다. 모든 S에 ε을 대입하면 된다. CFG G=(VN,VT,P,S)가 다음 중 한 가지 조건만을 만족할 경우에 ε-free문법이라고 한다 1. P가 생성규칙을 갖지 않는다. 2. 시작기호 S만이 S->ε 인 ε생성규칙을 가질 경우, 다른 생성규칙의 오른쪽에 S가 나타나지 않는다.