CHAPTER 5 TOP-DOWN PARSING SUNG-DONG KIM, DEPT. OF COMPUTER ENGINEERING, HANSUNG UNIVERSITY

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

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

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

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

LL(K) GRAMMAR  현재 위치에서 생성해야 할 터미널 k 개를 보고서 적용할 생성규칙을 결정적으로 선택할 수 있는 문법  For A → α | β FIRST k (α) ∩ FIRST k (β) = ф (2013-1) Compiler 6

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

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

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

FIRST & FOLLOW (4)  Grammar S → aBb | Bcb | ε A → aAb | BBd B → b | ε  FIRST(S) =  FIRST(A) =  FIRST(B) = (2013-1) Compiler 10

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

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

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

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

LEFT FACTORING  A → aB | aC  Left factoring A → aD D → B | C (2013-1) Compiler 15

CHOMSKY NORMAL FORM  CNF: RHS 2 nonterminals 1 terminal  EX: A → BC A → a  Parse tree = binary tree (2013-1) Compiler 16

GREIBACH NORMAL FORM  GNF 는 모든 생성규칙의 RHS 가 터미널로 시작  두 번째 이하는 논터미널들로만 구성  어떤 문법을 기술할 때 현실적으로 모든 생성규칙 들이 GNF 요건을 만족하도록 문법을 기술하기가 어렵다. (2013-1) Compiler 17

LOOKAHEAD(A→Α)  Using FIRST and FOLLOW α ≠ ε 이고, ε ∉ FIRST(α) 인 경우 LOOKAHEAD(A→α) = FIRST(α) α ≠ ε 이고, ε ∊ FIRST(α) 인 경우 LOOKAHEAD(A→α) = ( FIRST(α) - {ε} ) ∪ FOLLOW(A) α = ε 인 경우 LOOKAHEAD(A→ε) = FOLLOW(A) (2013-1) Compiler 18

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

RECURSIVE-DESCENT PARSER (2)  Procedure for terminal a (2013-1) Compiler 20 void pa() { if (nextsymbol == 'a') nextsymbol = get_nextsymbol(); else error; }

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; }

RECURSIVE-DESCENT PARSER (4)  main() function Call S() 호출 결과로 모든 입력 스트링이 생성되고 입력 버퍼에 입력 스 트링의 끝 표시인 '$' 만 남아 있으면 파싱 성공 (2013-1) Compiler 22 void main() { nextsymbol = get_nextsymbol(); pS(); if (nextsymbol == '$') accept; else error; }

RECURSIVE-DESCENT PARSER (5)  Stack for recursive descent parser Runtime stack during procedure call (2013-1) Compiler 23

IMPLEMENTATION: EXAMPLE  Grammar A → Ba | c B → bAB | ε  구문 분석 테스트 bcbcbca: babababaa: babcbabca: (2013-1) Compiler 24

RECURSIVE-DESCENT PARSER (6)  Easy & simple implementation  Hard coding for grammar  hardwired method (2013-1) Compiler 25

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

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 (2013-1) Compiler 27

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