Download presentation
Presentation is loading. Please wait.
1
CHAPTER 5 TOP-DOWN PARSING SUNG-DONG KIM, DEPT. OF COMPUTER ENGINEERING, HANSUNG UNIVERSITY
2
LL PARSING Left-to-right scanning & Leftmost derivation Deterministic parsing Nondeterministic problem A → α | β | γ How to do deterministic parsing without backtracking ? A → aα | bβ | cγ (2013-1) Compiler 2
3
GRAMMAR WITHOUT BACKTRACKING EX 1 S → aA | bB A → aBb | bBb | cBb B → d | e | f EX 2 S → AbB | BbB A → aBb | bBb | cBb B → d | e | f (2013-1) Compiler 3
4
LL(1) GRAMMAR 각 생성규칙을 적용할 때 현재 위치에서 생성되어야 할 터 미널 1 개를 보고 어떤 생성규칙을 적용할지 알 수 있는 결 정적 파싱이 가능한 문법 EX) A → α | β Set of terminals produced on A→α: FIRST(α) Set of terminals produced on A→β: FIRST(β) LL(1) condition: condition for deterministic parsing FIRST(α) ∩ FIRST(β) = ф (2013-1) Compiler 4
5
LL(2) GRAMMAR Example grammar S → aAb | aBb | acc A → a | Acc B → b S- 생성규칙을 적용할 때 현재 위치에서 생성되는 첫 번째 문자 는 모두 a 터미널 문자 1 개만 보았을 때 결정적 파싱이 불가능 생성할 문자를 2 개로 확장하여 aa/ab/ac 를 보면 결정적 파싱이 가능 이 문법은 LL(1) 문법이 아니고 LL(2) 문법 (2013-1) Compiler 5
6
LL(K) GRAMMAR 현재 위치에서 생성해야 할 터미널 k 개를 보고서 적용할 생성규칙을 결정적으로 선택할 수 있는 문법 For A → α | β FIRST k (α) ∩ FIRST k (β) = ф (2013-1) Compiler 6
7
FIRST & FOLLOW (1) FIRST(A): set of terminals from nonterminal A FIRST(α): set of terminals from sentential form α EX S → AbB | BbB A → aBb | bBb | cBb B → d | e | f FIRST(A) = FIRST(aBb) ∪ FIRST(bBb) ∪ FIRST(cBb) = { a, b, c } FIRST(B) = FIRST(d) ∪ FIRST(e) ∪ FIRST(f) = { d, e, f } FIRST(S) = FIRST(AbB) ∪ FIRST(BbB) = { a, b, c, d, e, f } (2013-1) Compiler 7
8
FIRST & FOLLOW (2) EX 4) FIRST for ε-production A → BabA | c B → b | ε FIRST(ε-production) = {ε} FIRST(B) = FIRST(b) ∪ FIRST(ε) = { b, ε } Nullable nonterminal From nullable nonterminal, ε can be produced by derivation FIRST(A) = FIRST(BabA) ∪ FIRST(c) = { a, b, c } (2013-1) Compiler 8
9
FIRST & FOLLOW (3) First for X→Y 1 Y 2 Y 3 ⋯ Y k ε ∉ FIRST(Y 1 ) : FIRST(Y 1 Y 2 Y 3 ⋯ Y k ) = FIRST(Y 1 ) ε ∈ FIRST(Y 1 ): FIRST(Y 1 Y 2 Y 3 ⋯ Y k ) = { FIRST(Y 1 ) - {ε} ) ∪ FIRST(Y 2 Y 3 ⋯ Y k ) Ring sum operation A ㊉ B = A, if ε ∉ A (A-{ε}) ∪ B, if ε ∊ A FIRST(Y 1 Y 2 Y 3 ⋯ Y k ) = FIRST(Y 1 ) ㊉ FIRST(Y 2 Y 3 ⋯ Y k ) = FIRST(Y 1 ) ㊉ FIRST(Y 2 ) ㊉... ㊉ FIRST(Y k ) (2013-1) Compiler 9
10
FIRST & FOLLOW (4) Grammar S → aBb | Bcb | ε A → aAb | BBd B → b | ε FIRST(S) = FIRST(A) = FIRST(B) = (2013-1) Compiler 10
11
FIRST & FOLLOW (5) EX 5) 아래 문법은 결정적 파싱이 가능한가 ? A → BbA | c B → b | ε FIRST(A) = FIRST(BbA) ∪ FIRST(c) = { b, c } FIRST(B) = FIRST(b) ∪ FIRST(ε) = { b, ε } B-production FOLLOW(B) (2013-1) Compiler 11
12
FIRST & FOLLOW (6) FOLLOW(B): A → αBβ ε ∉ FIRST(β) : FOLLOW(B) = FIRST(β) ε ∈ FIRST(β): FOLLOW(B) = FOLLOW(B) ∪ FOLLOW(A) β=ε (A→ ε): FOLLOW(B) = FOLLOW(B) ∪ FOLLOW(A) B is starting symbol, FOLLOW(B) = FOLLOW(B) ∪ {'$‘} Nonterminal B 가 생성규칙의 RHS 에서 2 회 이상 발견되는 경우는 각각 FOLLOW(B) 를 구하여 합집합 (2013-1) Compiler 12
13
FIRST & FOLLOW (7) Grammar S → aBb | Bcb | ε A → aAb | BBd B → b | ε FIRST(S) = { a, b, c, ε } FIRST(A) = { a, b, d } FIRST(B) = { b, ε } FOLLOW(S) = FOLLOW(A) = FOLLOW(B) = (2013-1) Compiler 13
14
LEFT RECURSION Left recursion problem A → Aα | β Infinite loop: A ⇒ Aα ⇒ Aαα ⇒ Aαα ⇒ Aααα ⇒... Solution: left recursive right recursive 문법 A → Aα | β 이 생성하는 스트링 유형은 βα * α * 를 우순환 규칙으로 기술 : A' → α A' | ε Right recursive rule for βα * A → β A‘ A' → α A' | ε (2013-1) Compiler 14
15
LEFT FACTORING A → aB | aC Left factoring A → aD D → B | C (2013-1) Compiler 15
16
CHOMSKY NORMAL FORM CNF: RHS 2 nonterminals 1 terminal EX: A → BC A → a Parse tree = binary tree (2013-1) Compiler 16
17
GREIBACH NORMAL FORM GNF 는 모든 생성규칙의 RHS 가 터미널로 시작 두 번째 이하는 논터미널들로만 구성 어떤 문법을 기술할 때 현실적으로 모든 생성규칙 들이 GNF 요건을 만족하도록 문법을 기술하기가 어렵다. (2013-1) Compiler 17
18
LOOKAHEAD(A→Α) Using FIRST and FOLLOW α ≠ ε 이고, ε ∉ FIRST(α) 인 경우 LOOKAHEAD(A→α) = FIRST(α) α ≠ ε 이고, ε ∊ FIRST(α) 인 경우 LOOKAHEAD(A→α) = ( FIRST(α) - {ε} ) ∪ FOLLOW(A) α = ε 인 경우 LOOKAHEAD(A→ε) = FOLLOW(A) (2013-1) Compiler 18
19
RECURSIVE-DESCENT PARSER (1) How to implement Write recursive procedure Left-most derivation for LL(1) For each terminal and nonterminal, write procedure For A → α |β Selection based on L.A.(A→α) and L.A.(A→β) L.A.(A→α) ∩ L.A.(A→β) = ф LL(1) (2013-1) Compiler 19
20
RECURSIVE-DESCENT PARSER (2) Procedure for terminal a (2013-1) Compiler 20 void pa() { if (nextsymbol == 'a') nextsymbol = get_nextsymbol(); else error; }
21
RECURSIVE-DESCENT PARSER (3) Procedure for nonterminal A (2013-1) Compiler 21 void pA() { case nextsymbol of LOOKAHEAD(A→X 1 X 2 ⋯ X m ): for i:=1 to m do pX i (); LOOKAHEAD(A→Y 1 Y 2 ⋯ Y n ): for i:=1 to n do pY i ();........ LOOKAHEAD(A→Z 1 Z 2 ⋯ Z r ): for i:=1 to r do pZ i (); otherwise: error; }
22
RECURSIVE-DESCENT PARSER (4) main() function Call S() 호출 결과로 모든 입력 스트링이 생성되고 입력 버퍼에 입력 스 트링의 끝 표시인 '$' 만 남아 있으면 파싱 성공 (2013-1) Compiler 22 void main() { nextsymbol = get_nextsymbol(); pS(); if (nextsymbol == '$') accept; else error; }
23
RECURSIVE-DESCENT PARSER (5) Stack for recursive descent parser Runtime stack during procedure call (2013-1) Compiler 23
24
IMPLEMENTATION: EXAMPLE Grammar A → Ba | c B → bAB | ε 구문 분석 테스트 bcbcbca: babababaa: babcbabca: (2013-1) Compiler 24
25
RECURSIVE-DESCENT PARSER (6) Easy & simple implementation Hard coding for grammar hardwired method (2013-1) Compiler 25
26
PREDICTIVE PARSER (1) Table driven method parsing table Stack: leftmost derivation process Initial stack: starting symbol a + a * a $ E Predictive parser (expand-pop) Predictive parsing table Parse tree (2013-1) Compiler 26
27
PREDICTIVE PARSER (2) Predictive parsing table Grammar S → bAb | aB | ε A → aAb | bBa B → b | ε FIRST FIRST(S) = { a, b, ε } FIRST(A) = { a, b } FIRST(B) = { b, ε } FOLLOW FOLLOW(S) = { $ } FOLLOW(A) = { b } FOLLOW(B) = { a, $ } a b $ SABSAB 2 1 3 4 5 7 6 7 (2013-1) Compiler 27
28
PREDICTIVE PARSER (3) More than 2 entries in parsing table: not LL(1) grammar For non LL(1) grammar: 그 의미에 따라 강제로 하나의 생 성규칙을 선택 deterministic parser (2013-1) Compiler 28
Similar presentations
