제 5 장 하향식 파싱
5.1 하향식 파싱 개념 문법 G를 사용하여 스트링 a + a * a를 유도하는 과정 G = ({E, OP }, {a, +, -, *, /, (, )}, P, E ) P : E → E OP E |( E ) | - E | a OP → + | - | * | / 이 문법에서 산술 수식 a + a * a 를 생성하는 좌단으로 유도하는 과정은 아래와 같다. E ⇒ E OP E ⇒ E OP E OP E ⇒ a OP E OP E ⇒ a + E OP E ⇒ a + a OP E ⇒ a + a * E ⇒ a + a * a
그림 5.1 산술 수식 a + a * a 의 좌단 유도 트리
다른 생성규칙을 적용하여 유도 E ⇒ E OP E ⇒ E OP E OP E ⇒ a OP E OP E 다음 단계 유도에 OP → + 대신에 OP → / 를 대치한다. 그러면 아래와 같이 유도하지만 원하는 a + a * a 를 생성하지는 않는다. E ⇒ E OP E ⇒ E OP E OP E ⇒ a OP E OP E ⇒ a / E OP E ⇒ a / a OP E ⇒ a / a * E ⇒ a / a * a
백트래킹에 의한 산술 수식 a + a * a의 유도 트리
좌측 순환 α에 대하여 S ⇒ Sα와 같은 유도가 생기는 넌터미널 S가 존재하는 경우이다. 문법 G에 E → E OP E 와 같이 좌측-순환이 발생할 수 있는 생성 규칙이 있거나, α에 대하여 S ⇒ Sα와 같은 유도가 생기는 넌터미널 S가 존재하는 경우이다.
5.2 리커시브 디센트 파싱 하향식 파싱은 입력 스트링을 좌단 유도하면서 루트에서 잎 노드까지 전위 순회하면서 파스 트리를 구성 수식 -a + a * a 를 파싱하는 리커시브 디센트 파싱 예 G : E → - F OP F F → a OP → + 이 문법에서 E → - F OP F 는 - 로 시작하고 그 뒤에 F가 오고, 그 뒤에는 순서대로 OP와 F가 온다. F → a와 OP → +는 a와 + 만으로 끝난다는 의미이다.
리커시브 디센트 파서를 구성한 예 function E( ) /* E → - F OP F */ { { if (nextsymbol == '-') { get_nextsymbol( ); F( ); OP( ); } else Error( ); } function F( ) /* F → a */ { if (nextsymbol == 'a') get_nextsymbol( ) else Error( ); }
리커시브 디센트 파서를 구성한 예 function OP( ) /* OP → + */ { { if (nextsymbol == '+') get_nextsymbol( ) /* OP → + */ else Error( ); } main( ) { get_nextsymbol( ); E( ); if (next_symbol == '↲') Accept( ) else Error( ); }
리커시브 디센트 파서 구현에서 고려할 사항 문법의 생성 규칙이 어떻게 구성되어 있는가에 따라 문제가 발생할 수 있으며 구현 방법도 달라질 수 있다. 아래 문법을 살펴보자. P1: A → aAb /* 넌터미널 A가 생성하는 두 규칙의 다른 터미널 a와 b로 시작 */ A → b P2: A → aAb /* a와 ε 로 시작한다 */ A → ε P3: A → aAb /* 넌터미널 A가 생성하는 규칙에서 두 개 모두 터미널 a로 시작 */ A → a
예 5.1 위의 문법 규칙 P1에서 첫 번째 생성 규칙의 S-터미널 집합은 {a}이며, 두 번째 생성 규칙에서는 {b}이다. 정의 5.1 S-터미널 집합(Selection-터미널 집합)은 문법의 생성규칙을 적용하도록 하는 입력 심볼(터미널)의 집합이다. 예 5.1 위의 문법 규칙 P1에서 첫 번째 생성 규칙의 S-터미널 집합은 {a}이며, 두 번째 생성 규칙에서는 {b}이다. P1: A → aAb A → b
5.2.1 문법에 A → aα형식의 생성 규칙이 있는 경우 아래 생성 규칙 P4를 살펴보자. P4: 1. A → aAc 2. A → bAc 3. A → c 문법 규칙 P4에서 스트링 abccc를 유도하면 아래와 같다. A ⇒a aAc ⇒b abAcc ⇒c abccc A → aα형식의 생성 규칙에서는 S-터미널 집합에서 터미널이 하나만 있지만 어떤 문맥-자유 문법에서는 터미널이 여러 개 있을 수 있다.
리커시브 디센트 파서 예 5.2 아래는 문법의 생성 규칙 P5에 대한 리커시브 디센트 파서이다. P5: 1. A → aAB 3. B → a 4. B → bBa
function A( ) { if (nextsymbol == 'a') /* 규칙 1 */ { get_nextsymbol( ); A( ); B( ); } else if (nextsymbol == 'b') get_nextsymbol( ) /* 규칙 2 */ else Reject( ); } function B ( ) if (nextsymbol == 'a') get_nextsymbol( ) /* 규칙 3 */ else if (nextsymbol == 'b') { /* 규칙 4 */ get_nextsymbol( ); B( ); if (nextsymbol == 'a') get_nextsymbol( ) else Reject( ); } else Reject( );
main( ) /* 파싱 시작 */ char nextsymbol; /* 입력 문자 */ { get_nextsymbol(nextsymbol); A( ); if (nextsymbol == '↲') Accept( ) else Reject( ); }
실습 5. 1 아래 문법에 대하여 리커시브 디센트 파서를 구성하시오 실습 5.1 아래 문법에 대하여 리커시브 디센트 파서를 구성하시오. 이 문법에서 생성 규칙 1과 2는 다른 터미널 a, b로 시작하면서 A를 정의하지만, 규칙 3과 4는 다른 터미널 a, b로 시작하면서 B를 정의한다. 1. A → aAbB 2. A → baB 3. B → aAa 4. B → b
5.2.2 문법에 A → ε 형식의 생성 규칙이 있는 경우 이 형식은 오른쪽 맨 처음 심볼이 ε 인 경우,A는 넌터미널이고 이 넌터미널을 정의하는 생성 규칙은 각각 다른 S-터미널 집합을 가진다. 아래의 문법 규칙을 살펴보자. P6: 1. A → aBA 2. A → b 3. B → cBA 4. B → ε 생성 규칙 4의 B → ε에 대해서는 S-터미널 집합을 구할 수 없다(입력 심볼에는 ε 이 없다).
정의 5.2 넌터미널 A의 FOLLOW 집합은 S↲에서 유도하는 문장 형식에서 A의 바로 뒤에 올 수 있는 모든 터미널(혹은 끝표시 ↲)의 집합이다. 즉, α와 β에 대하여 S ⇒*αAaβ 형식의 유도가 있는 경우에 터미널 a의 집합을 말한다. FOLLOW 집합은 FOLLOW(A)로 표기하며 S는 시작 넌터미널 심볼이다.
예 5. 3 문법 규칙 P6에서 A의 FOLLOW 집합을 구하기 위하여 유도해보자 예 5.3 문법 규칙 P6에서 A의 FOLLOW 집합을 구하기 위하여 유도해보자. 넌터미널 심볼 A는 아래와 같이 문장 형식을 유도한다. A↲⇒ aBA↲⇒ acBAA↲⇒ acBAaBA↲⇒ ... ⇒ acBAb↲⇒ ... 이 유도에서 밑줄친 부분처럼 넌터미널 A에 대하여 터미널 심볼 a가 바로 뒤에 있다. 그러므로 FOLLOW(A) = { a, b, ↲} 이다. 또한 넌터미널 심볼 B는 아래와 같은 문장 형식을 유도한다. A↲⇒ aBA↲⇒ aBaBA↲... ⇒ ... aBb↲⇒ ... 이 유도에서도 넌터미널 B에 대하여 터미널 심볼 a와 b가 바로 뒤에 있다. 그러므로 FOLLOW(B) = { a, b }이다.
파서가 입력 스트링 acbb 를 유도하는 과정을 통하여 문법 규칙 P6의 S-터미널 집합을 살펴보자. P6: 1. A → aBA S-터미널 집합 = {a} 2. A → b S-터미널 집합 = {b} 3. B → cBA S-터미널 집합 = {c} 4. B → ε S-터미널 집합 = {a, b} 넌터미널 B에 대해서는 입력 심볼에 따라 유도를 결정 심볼이 c이면 생성 규칙 3을 선택 입력 심볼이 a거나 b면 규칙 4를 선택
입력 스트링 acbb 를 파싱하는 과정 1. a가 현재의 입력 스트링이고 생성 규칙 1을 적용한다. A ⇒a aBA A ⇒a aBA ⇒c acBAA 3. b가 현재의 입력 스트링이고 생성 규칙 4를 적용한다. 생성 규칙 4는 B → ε 이고 S-터미널 집합 아니기 때문에 더 이상 입력 심볼을 읽지 않고 되돌아간다. A ⇒a aBA ⇒c acBAA ⇒b acεAA ⇒ acAA 4. b가 현재의 입력 스트링이고 S-터미널 집합에 의하여 생성 규칙 2의 A → b를 적용한다. A ⇒a aBA ⇒c acBAA ⇒b acεAb ⇒ acAb
생성 규칙 P6에 대한 리커시브 디센트 파서 function A( ) { { if (nextsymbol == 'a') /* 규칙 1 */ { get_nextsymbol( ); B( ); A( ); } else if (nextsymbol == 'b') get_nextsymbol( ) /* 규칙 2 */ else Reject( ); }
function B( ) { if (nextsymbol == 'c') /* 규칙 3 */ { get_nextsymbol( ); B( ); A( ); } else if (nextsymbol == 'a' || nextsymbol == 'b') return( ) /* 규칙 4 */ else Reject( ); } main ( ); /* 파싱 시작 */ char nextsymbol; { get_nextsymbol( ); A( ); if (nextsymbol == '↲') Accept( ) else Reject( );
실습 5.2 아래 문법에서 S-터미널 집합을 구하고, 리커시브 디센트 파서를 구성해 보자. 1. One → 1 Zero 1 2. One → 0 3. Zero → 0 One 0 4. Zero → ε 이 문법에서 규칙 4에 대한 S-터미널 집합을 구하기 위해서 넌터미널 Zero에 대한 FOLLOW 집합을 구한다.
5.3 LL(1) 문법 정의 5.3 어떤 문법 G에서 두 개의 생성규칙 A → α와 A → β가 아래 특성을 가지면 LL(1) 조건이라 한다. 1. α와 β 둘 다 같은 터미널 a로 시작하는 스트링을 유도하지 않는다. 2. α와 β 중에서 반드시 하나는 빈스트링을 유도할 수 있다. 3. β ⇒* ε 이면, α는 FOLLOW(A)에 있는 어떤 터미널로 시작하는 스트링을 유도하지 않는다.
문법 규칙이 A → α(단, α는 터미널과 넌터미널 모두 가능한 임의의 스트링)와 같이 일반적인 형식인 경우에는 아래 같이 넌터미널 A 하나가 생성규칙 여러 개를 정의하는 경우가 있다. A → aα A → bα 이 경우에는 여러 개의 유도가 있기 때문에 LL(1) 문법이 아니며 하향식으로 파싱하기가 어렵다.
5.4 예측 파싱 예측 파싱은 리커시브 디센트 파싱이긴 하지만 백트래킹이 없는 하향식 파싱으로 어떤 생성 규칙을 적용할 것인가를 미리 결정하여 적용하는 기법이다. 현재 입력 심볼 a 와 넌터미널 심볼 A에 대하여, 생성 규칙 A → α1|α2| ... |αn 에서 a로 시작하는 생성 규칙 하나를 선택한다. S → aBbSc S → bBbS S → cSe 위 문법에서는 S라는 넌터미널에 대해 적용할 생성 규칙은 세개이다. 예측 파싱은 문맥-자유 문법인 오직 LL(k) 문법에서만 가능
5.4.1 예측 파싱을 위한 자동 기계 모델 그림 5.3 예측 파싱을 위한 자동 기계 모델 이 기계는 어떤 생성 규칙을 적용할 것인지를 자동으로 결정 그림 5.3 예측 파싱을 위한 자동 기계 모델
예측 파싱 루틴은 입력 터미널 심볼을 하나씩 읽어서 스택 톱에 있는 넌터미널 심볼과 비교한다. 스택의 넌터미널과 입력 터미널의 관계를 전이 테이블을 검사한다. 두 심볼 사이의 관계 정보가 전이 테이블에 있으면 이 정보에 따라 예측 파싱 루틴은 다음 행동을 진행한다. 전이 테이블에 넌터미널과 터미널 사이에 정보가 없으면 에러가 발생한다. 이 모델에서 알 수 있듯이 예측 파싱 루틴은 전이 테이블에 있는 정보에 따라 기계적으로 다음 진행을 결정 어떤 생성 규칙을 선택할 것인가를 고민할 필요가 없다. 문법의 생성 규칙에서 전이 테이블만 만들면 하향식으로 파싱할 수 있다.
5.4.2 자동 기계에 의한 예측 파서의 구조와 동작 그림 5.4 자동 기계 모델에 의한 예측 파서 구조
파싱 테이블 P의 구조 터미널 넌터미널 a1 a2 ... am ↲ A1 생성 규칙 에러 ... A2 A3 An
P[A, a] 형식의 테이블 내용 P[A, a] 형식에서 Ai, (i = 1, 2, ...., n)는 넌터미널 심볼 aj,(j = 1, 2, ...., m)는 터미널 심볼 파싱 핸들러는파싱 테이블에서 입력 터미널 심볼 aj 와 스택 톱의 넌터미널 심볼 Ai 를 매치한다. 파싱 테이블 내용은 P[Ai, aj] = “생성 규칙” 이거나 P[Ai, aj] = “에러” 내용이 P[Ai, aj] = “생성 규칙” 이면 스택의 톱에 있는 넌터미널을 이 생성 규칙의 오른쪽 심볼 스트링으로 대치한다.
파싱 예 아래에서 왼쪽 부분이 스택이고 오른쪽 부분이 입력 큐인 상태라 하자. (#......X, aj aj+1 ... ↲) P[Ai, aj] = “X → αβω” 이면, 스택 톱의 넌터미널 심볼을 아래처럼 대치한다. (#......ωβα, aj aj+1 ... ↲) 스택 톱에는 생성 규칙의 αβω 에서 맨 앞 심볼인 α이 오도록 거꾸러 대치한다. 그러나 P[Ai, aj] = “에러” 이면 에러 메시지를 통지한다.
aabbbb를 예측 파싱하는 예 문법 1. S → aSb 2. S → bA 3. A → aA 4. A → b 이 문법의 파싱 테이블은 아래와 같다. 터미널 넌터미널 a b S S → aSb S → bA A A → aA A → b
(#S, aabbbb↲) (#bSa, aabbbb↲) (#bS, abbbb↲) (#bbSa, abbbb↲) (#bbS, bbbb↲) (#bbAb, bbbb↲) (#bbA, bbb↲) (#bbb, bbb↲) (#bb, bb↲) (#b, b↲) (#, ↲)
예측 파싱에서 파싱 핸들러의 행위 function Predictive_Parsing _Handler ( ) /* 예측 파싱 핸들러 동작 */ { a = get_nextsymbol( ); /* 입력 큐의 스트링에서 토큰 하나를 가져 온다 */ while ( ) { X = Stack(top); if ( X == ↲) accept( ); if ( X ∈ VT || ↲) if ( X == a ) remove X from the stack and get_nextsymbol( ) else error(1); else /* X 가 넌터미널이면 */ if ( P[X, a] == X → Y1Y2...Yk ) replace X by YkYk-1,...,Y1; /* Y1 이 스택 톱에 오도록 대치한다 */ else error(2); } }
실습 5.3 아래 문법과 파싱 테이블을 이용하여 aba를 예측 파싱하여 보자. 1. S → aSb 2. S → bA 3. A → aA 4. A → b 파싱 테이블 터미널 넌터미널 a b S S → aSb S → bA A A → aA A → b
실습 5.4 실습 5.3의 문법과 파싱 테이블을 이용하여 bbb를 예측 파싱하여 보자.
실습 5.6 아래 문법과 파싱 테이블을 이용하여 10000을 예측 파싱하여 보자. 1. S → 1S0 2. S → 0A 3. A → 1A 4. A → 0 이 문법의 파싱 테이블은 아래와 같다. 터미널 넌터미널 1 S S → 1S0 S → 0A A A → 1A A → 0
5.4.3 예측 파서의 파싱 테이블 만들기 function Making_Predictive_Parsing _Table ( ) /* 예측 파싱 테이블 만들기 */ { for (each production A→α) { for ( a ∈ FIRST(α)) P[A, a] = A→α; if ( ε ∈ FIRST(α) && a ∈ FOLLOW(A)) P[A, a] = A→α; if ( ε ∈ FIRST(α) && ↲∈ FOLLOW(α)) P[A, ↲] = A→α; } }
예측 파싱 테이블을 만들기 예 1. S → aSb 2. S → bA 3. A → aA 4. A → b 파싱 테이블을 만들기 전에 먼저 중요한 것은 이 문법에 대한 FIRST와 FOLLOW 집합을 구하는 것이다. FIRST(S) = {a, b} FIRST(A) = {a, b} FOLLOW(S) = {b, ↲} FOLLOW(A) = {a, b, ↲}
(1) 생성 규칙 S → aSb에서 FIRST(S) = {a} 이므로 P[S, a] = S → aSb (2) 생성 규칙 S → bA에서 FIRST(S) = {b} 이므로 P[S, b] = S → bA (3) 생성 규칙 A → aA에서 FIRST(A) = {a} 이므로 P[A, a] = A → aA (4) 생성 규칙 A → b에서 FIRST(A) = {b} 이므로 P[A, b] = A → b 파싱 테이블 터미널 넌터미널 a b S S → aSb S → bA A A → aA A → b
널가능(α⇒*ε)한 문법의 예측 파싱 테이블 1. E → TE ' 2. E ' → +TE ' 3. E ' → ε 4. T → FT ' 5. T ' → *FT ' 6. T ' → ε 7. F → ( E ) 8. F → a
위 문법의 FIRST 집합을 구하면 아래와 같다. FIRST(E) = { (, a } FIRST(T) = { (, a } FIRST(F) = { (, a } FIRST(E') = { +, ε} FIRST(T') = { *, ε} 위 문법의 FOLLOW 집합을 구하면 아래와 같다. FOLLOW(E) = FOLLOW(E ') = { ), ↲} FOLLOW(T) = FOLLOW(T ') = { +, ), ↲} FOLLOW(F) = { +, *, ), ↲}
1. 생성 규칙 E → TE '에 대해서 a ∈ FIRST(α)에 해당하는 터미널 a는 FIRST(E) = { (, a }이다. P[E, (] = E → TE' P[E, a] = E → TE' 2. 생성 규칙 E ' → +TE ' 에 대해서는 FIRST(E ') = { +, ε} 이다. P[E ', +] = E ' → +TE ' 3. E ' → ε 에 대해서는 FOLLOW(E') = { ), ↲} 이다. P[E ', )] = E ' → ε P[E ', ↲] = E ' → ε
생성한 예측 파싱 테이블 터미널 넌터미널 a + * ( ) ↲ E E → TE' E → TE' E' E' → +TE' 터미널 넌터미널 a + * ( ) ↲ E E → TE' E → TE' E' E' → +TE' E' → ε T T → FT' T' T' → ε T' → *FT' F F → a F → ( E )
입력 스트링 a + a * a 를 파싱 (#E, a+a*a↲) (#E'T, a+a*a↲) (#E'T'F, a+a*a↲) (#E'T'a, a+a*a↲) (#E'T', +a*a↲) (#E', +a*a↲) (#E'T+, +a*a↲) (#E'T, a*a↲) (#E'T'F, a*a↲) (#E'T'a, a*a↲) (#E'T', *a↲) (#E'T'F*, *a↲) (#E'T'F, a↲) (#E'T'a, a↲) (#E'T', ↲) (#E', ↲) (#, ↲)
5.5 FIRST와 FOLLOW 집합 구하기
5.5.1 FIRST 터미널 집합 구하기 정의 5.5 FIRST(A) 집합은 A가 넌터미널 심볼이면, A에서 유도되는 모든 스트링의 맨 앞에 있는 터미널의 집합이다. 또한 A⇒*ε 이면 ε 도 FIRST(A)의 집합에 속한다. FIRST(A) = { a ∈VT )∪{ε} | A ⇒* aβ, β∈V* } 정의에 따라 아래 생성 규칙에서 각 넌터미널에 대한 FIRST 터미널 집합을 구한다. S → aA | A A → bB | B B → c
넌터미널 S 에서의 FIRST 터미널 집합은 FIRST(S) = { a, b, c } 이다. S ⇒ aA S ⇒ A ⇒ bB S ⇒ A ⇒ B ⇒ c 넌터미널 S 에서의 FIRST 터미널 집합은 FIRST(S) = { a, b, c } 이다. 2. 다음은 생성 규칙 A 에서는 아래와 같이 두 개의 유도가 가능하고 각 유도의 문장 형식에서 맨 앞에 오는 터미널 심볼은 b와 c 이다. A ⇒ bB A ⇒ B ⇒ c
3. 넌터미널 A 에서의 FIRST 터미널 집합은 FIRST(A) = { b, c } 이다. 넌터미널 B 에서의 FIRST 터미널 집합은 FIRST(B) = { c } 이다.
ε을 생성하는 경우의 FIRST 터미널 집합을 구하는 과정 심볼 스트링이 A1A2 ... An 처럼 연속으로 있는 경우에는 FIRST(A1A2 ... An) 터미널 집합을 아래와 같이 구한다. FIRST(A1A2 ... An) = (....((FIRST(A1) ∪ FIRST(A2)) ∪ FIRST(A3)) ∪..... ∪ FIRST(An))
예 (1) FIRST(p) = { a, b, c, d }이고, FIRST(q) = { c, d, e } 이면, FIRST(p)∪FIRST(q) = { a, b, c, d } (2) FIRST(p) = { x, y, z, ε }이고, FIRST(q) = { a, b } 이면, FIRST(p)∪FIRST(q) = { x, y, z, a, b } (3) FIRST(p) = { a, b, ε }이고, FIRST(q) = { x, y, ε } 이면, FIRST(p)∪FIRST(q) = { a, b, x, y, ε } 이다.
FIRST(X) 터미널 집합을 구하는 방법 정리 (1) X가 터미널 심볼이면, X의 FIRST 터미널 심볼은 X이다. 즉, X ∈VT이면, FIRST(X) = { X } 이다. (2) X→ aα 의 생성 규칙이 있으면 a 를 FIRST(X) 에 넣는다. 즉, X → aα P 이고 a ∈ VT 이면, FIRST(X) = FIRST(X) ∪ {a} 이다. 또한, X 가 ε를 생성하면 X 의 FIRST 집합에 ε 을 넣는다. 즉, X→ε ∈P 이면 FIRST(X) = FIRST(X) ∪ {ε}이다. (3) X → A1A2 ... Ak 의 생성 규칙이 있으면 FIRST(X) = FIRST(X) ∪ FIRST(A1A2 ... Ak) 이다. FIRST(X) = FIRST(X) ∪ FIRST(A1A2 ... Ak) = FIRST(X) ∪ (....((FIRST(A1) ∪ FIRST(A2)) ∪ FIRST(A3)) ∪..... ∪ FIRST(An))
예 5.4 아래와 같이 프로그램 구조를 나타내는 간단한 문법에서 FIRST 터미널 집합을 구해보자. Prog → Decl Exec ; Decl → # Prog | type Exec | int Exec → Decl Prog | stmt 생성 규칙의 형식에 따라 각 넌터미널의 FIRST 터미널 집합을 구할 수 있다. FIRST(Prog) = { } FIRST(Decl) = { #, type, int } FIRST(Exec) = { stmt }
이 각 집합으로부터 각 넌터미널의 FIRST 터미널 집합을 아래와 같이 구한다. FIRST(Prog) = FIRST(Prog) ∪ FIRST(Decl Exec ;) FIRST(Prog) = FIRST(Prog) ∪ (( FIRST(Decl) ∪FIRST(Exec)) ∪FIRST(;) ) 여기에서 FIRST(Decl)에는 ε 이 없기 때문에 아래와 같다. FIRST(Decl)∪FIRST(Exec) = FIRST(Decl) = { #, type, int }
최종적으로 아래와 같다. (( FIRST(Decl) ∪FIRST(Exec)) ∪ FIRST(;) ) = FIRST(Decl) = { #, type, int } 구해진 FIRST(Prog) 터미널 집합 FIRST(Prog) = FIRST(Prog) ∪ FIRST(Decl Exec ;) = { } ∪ { #, int, type } = { #, int, type }
같은 방법으로 FIRST(Exec) = FIRST(Exec)∪ ( FIRST(Decl Prog ) = { stmt } ∪ { #, int, type } = { #, stmt, int, type } 이 문법에서 최종으로 구한 각 넌터미널의 FIRST 터미널 집합은 아래와 같다. FIRST(Prog) = { #, int, type } FIRST(Decl) = { #, int, type } FIRST(Exec) = { #, stmt, int, type }
예 5.5 많이 사용하는 아래와 같은 산술 수식 문법에서 FIRST 터미널 집합을 구해보자. G: 1. E → TE′ 2. E′ → +TE′ 3. E′ → ε 4. T → FT′ 5. T′ → *FT′ 6. T′ → ε 7. F → ( E ) 8. F → a
최종적으로 구해진 FIRST 터미널 집합은 다음과 같다. FIRST(E) = FIRST(T) = FIRST(F) = { (, a } FIRST(E′) = { +, ε } FIRST(T′) = { * , ε }
FIRST 집합을 구하는 알고리즘 function FIRST_SET; input: grammar G = (VN, VT, P, S ); output: FIRST_SET; { for (each production) { /* 생성규칙이 터미널 자체이면 이 심볼은 FIRST 집합이다. */ if (X ∈VT ) FIRST(X) = X; /* X→ aα 형식과 X → ε 형식이 있으면 a와 ε 를 FIRST(X) 에 넣는다 */ if (X→ aα∈ P) FIRST(X) = FIRST(X) ∪ {a}; if (X → ε ∈ P) FIRST(X) = FIRST(X) = FIRST(X) ∪ {ε}; } for (X ∈VN && X → A1A2 ... Ak ∈P) { /* FIRST(X) = FIRST(X)∪(....((FIRST(A1)∪FIRST(A2))∪FIRST(A3))∪.....∪ FIRST(Ak)) */ /* 여기에서 합집합 연산 (FIRST(Ak) ∪ FIRST(Ak+1)) 은 아래처럼 결과를 가진다 */ /* ε∉ FIRST(Ak) 이면 연산 결과는 FIRST(Ak) 이다 */ /* ε∈ FIRST(Ak) 이면 연산 결과는 (FIRST(Ak) - {ε}) ∪ FIRST(Ak+1) 이다 */ p = FIRST(A1) for (k =2; k <= n; k++) { if ( ε∉ p ) p = p else if ( ε∈ p ) p = (p - {ε}) ∪ FIRST(Ak); } FIRST(X) = FIRST(X)∪p; }
5.5.2 FOLLOW 터미널 집합 구하기 정의 5.6 FOLLOW(A) 집합은 문장형식에서 넌터미널 A의 바로 뒤에 있는 터미널 심볼의 집합이다. 즉, 문장형식 S ⇒*αAaβ에서 터미널 a 를 말한다. 어느 유도 시점에서 A 와 a 사이에 어떤 심볼이 있을 수도 있는데 이것은 ε을 유도하였다가 사라진 것이다. A가 어떤 문장형식의 오른쪽 맨 끝에 있는 심볼이면 입력 스트링의 끝을 의미하는 ↲도 FOLLOW(A)에 속한다. FOLLOW(A) = { a ∈VT )∪{↲} | S ⇒*αAaβ, α,β∈V*}
단계별로 FOLLOW 터미널 집합을 구하기 (1) 맨 처음 시작 심벌에서는 ↲를 FOLLOW 집합에 넣는다. 즉, FOLLOW(S) = { ↲}이다. (2) 생성 규칙이 A→αBβ 와 같은 형식이고 β≠ε 이면, 넌터미널 B의 FOLLOW 에는 FIRST(β) 집합에서 ε 을 제외한 나머지 터미널 심볼을 넣는다.즉, A→αBβ이고 β≠ ε 이면 FOLLOW(B) = FOLLOW(B) ∪ ( FIRST(β) - {ε} ) 이다. (3) 생성 규칙이 A→αB 형식이면 A의 FOLLOW 터미널 전체를 B의 FOLLOW에 넣는다. 즉, A→αB∈P 이면 FOLLOW(B) = FOLLOW(B) ∪ FOLLOW(A) 이다. (4) 또한 생성 규칙이 A→αBβ 형식이면서 FIRST(β) 집합에 ε이 있는 경우 (즉, β ⇒*ε )에도 A의 FOLLOW 터미널 심볼 전체를 B의 FOLLOW에 넣는다. 즉, A→αBβ 이며 β ⇒*ε이면 FOLLOW(B) = FOLLOW(B) ∪ FOLLOW(A) 이다.
예 5. 6 예 5. 5에서 이미 사용한 산술 수식 문법에서 FOLLOW 터미널 집합을 구해보자 예 5.6 예 5.5에서 이미 사용한 산술 수식 문법에서 FOLLOW 터미널 집합을 구해보자. 각 넌터미널의 FOLLOW 집합을 구하기 위해 예 5.5에서 구한 FIRST 집합을 이용한다. 위 문법에 대한 FOLLOW 터미널 집합은 아래와 같다. FOLLOW(E) = { ↲, )} FOLLOW(E′) = { ↲, )} FOLLOW(T) = {↲, ), +} FOLLOW(T′) = {↲, ), +} FOLLOW(F) = {*, ↲, ), +}
FOLLOW 집합을 구하는 알고리즘 function FOLLOW_SET; input: grammar G = (VN, VT, P, S ); output: FOLLOW_SET; /* 생성 규칙의 각 넌터미널 심볼의 초기 FOLLOW 집합은 비어 있다. */ { /* S 가 시작심볼이고 ↲가 입력문장의 끝이면 ↲를 FOLLOW(S) 에 넣는다. */ if (S∈'Start Symbol' && '↲'= 'End Mark') FOLLOW(S) = '↲'; for (A→αBβ∈P && β≠ε) { FOLLOW(B) = FOLLOW(B) ∪ ( FIRST(β) - {ε}); } for (A→αB∈P) { FOLLOW(B) = FOLLOW(B) ∪ FOLLOW(A); for (A→αBβ∈P && ε∈FIRST(β)) { /* 남아있는 넌 터미널에 대해 아래 과정을 반복한다 */ for (X → A1A2 ... An-1An ∈P) { for (j = n; j > = 2; j--) { if (ε∈FIRST(Aj)) { FOLLOW(Aj-1) = FOLLOW(X); } } }
5.6 예측 파싱에서 고려할 사항 프로그래밍 언어의 if 문의 구조를 살펴보자. Stmt → if Bexpr then Stmt Stmt' | a Stmt' → else Stmt | ε Bexpr → bool 파싱 테이블을 구성하기 위해 문법을 아래와 같이 다시 쓸 수 있다. 1. Stmt → if Bexpr then Stmt Stmt' 2. Stmt → a 3. Stmt' → else Stmt 4. Stmt' → ε 5. Bexpr → bool
이 문법의 FIRST와 FOLLOW 집합은 아래와 같다. FIRST(Stmt) = { if, a } FIRST(Stmt') = {else, ε} FIRST(Bexpr) = { bool } FOLLOW(Stmt) = { else, ↲} FOLLOW(Stmt') = { else, ↲} FOLLOW(Bexpr) = { then }
아래 생성 규칙에서 a ∈ FIRST(α)에 해당하는 터미널은 if와 a 이므로 FIRST(Stmt) = { if, a }이다. P[A, a] = A→α를 만들면 아래와 같다. P[Stmt, if] = if Bexpr then Stmt Stmt' P[Stmt, a] = a
아래 생성 규칙에서 a ∈ FIRST(α)에 해당하는 터미널은 else와 ε 이므로 FIRST(Stmt') = {else, ε}이다. P[A, a] = A→α를 만들면 아래와 같다. P[Stmt', else] = else Stmt
Stmt' → ε 에 대해서는 아래와 같다. P[Stmt', else] = Stmt' → ε P[Stmt', ↲] = Stmt' → ε 생성 규칙 Bexpr → bool 에서는 아래와 같다. P[Bexpr, bool] = Bexpr → bool
이 문법에서 FIRST와 FOLLOW 집합으로 만든 파싱 테이블 터미널 넌터미널 a bool else if then ↲ Stmt Stmt → a Stmt→if Bexpr then Stmt Stmt' Stmt' Stmt'→else Stmt Stmt'→ε Stmt' → ε Bexpr Bexpr → bool
이 테이블의 문제점:충돌 현상 이렇게 P[Stmt', else]의 내용이 두 개 이상 있으면 충돌이 있다고 한다. 생성 규칙 3인 Stmt' → else Stmt 로 대치해야할지 생성 규칙 4인 Stmt' → ε으로 대치해야 할지 대치할 생성 규칙이 두 개 이상 있으므로 이 문법은 LL(1) 문법이 아니며 올바르게 파싱할 수 없다.
실습 5.7 if 문에 대한 위의 문법과 파싱 테이블에서 아래 문장을 파싱해 보자. if bool then if bool then a else a
5.7 예측 파싱에서 에러 처리 실습 5.3에서와 같이 주어진 파싱 테이블을 이용하여 aba를 예측 파싱하면, 넌터미널 심볼 A가 스택 톱에 있고, 입력 터미널은 ↲인 경우에는 아래와 같이 파싱을 완전히 수행하지 않는다. (#S, aba↲) (#bSa, aba↲) (#bS, ba↲) (#bAb, ba↲) (#bA, a↲) (#bAa, a↲) (#bA, ↲) (더 이상 매치가 일어나지 않으므로 파싱을 진행할 수 없음)
에러가 포함된 파싱 테이블 예 터미널 넌터미널 a + * ( ) ↲ E E → TE' error E' E' → +TE' 터미널 넌터미널 a + * ( ) ↲ E E → TE' error E' E' → +TE' E' → ε T T → FT' T' T' → ε T' → *FT' F F → a F → ( E )
입력 스트링 a a * a 의 파싱 (#E, aa*a↲) (#E 'T, aa*a↲) (#E 'T 'F, aa*a↲) (#E 'T 'a, aa*a↲) (#E 'T ', a*a↲) 에러 발생, 입력에서 a를 지나간다 (#E 'T ', *a↲) (#E 'T 'F*, *a↲) (#E 'T 'F, a↲) (#E 'T 'a, a↲) (#E 'T ', ↲) (#E ', ↲) (#, ↲) 파싱 끝
제 5 장 끝