Microsoft PowerPoint - chap5.ppt

Size: px

Start display at page:

Download "Microsoft PowerPoint - chap5.ppt"

동범 운
5 years ago
Views:

1 제 5 장 Context-Free 문법 상지대학교컴퓨터정보공학부고광만 (kkman@mail.sangji.ac.kr)

2 Contents 5.1 서론 5.2 유도와유도트리 5.3 문법변환 5.4 CFG 표기법 5.5 Push Down Automata; PDA 5.6 Context-free 언어와 PDA 언어 제 5 장 : Context-Free Grammar 2

3 서론 정규문법 간단한패턴기술에적합 프로그래밍언어의구문구조표현에부적합 토큰구조 정규표현 프로그래밍언어문법구조 Context-Free Grammar; CFG Context-Free Grammar 의장점 간단하고이해하기용이 표현된문법으로부터자동적으로인식기구현 입력된프로그램의구조를생성규칙에의해분해, 번역이유용 제 5 장 : Context-Free Grammar 3

4 Context-Free Grammar A α생성규칙 A : Nonterminal, α : V * A를문맥에관계없이 α로대치 context-free( 문맥-자유또는문맥-무관 ) 제 5 장 : Context-Free Grammar 4

5 표기법 (Notational Convention) Terminal 심볼 알파벳소문자 (a, b, c,... ), 숫자 ( 0,1,2,...,9) 연산자기호 (+, -,...) 구분자 ( 세미콜론, 콤마, 괄호 ) ' 와 ' 사이에표기된문법심볼 Nonterminal 심볼 알파벳대문자 S, 시작심볼 (start symbol) < 와 > 로묶어서나타낸문법심볼 <stmt>, <expr> 제 5 장 : Context-Free Grammar 5

6 A α 1, A α 2,..., A α k 생성규칙의왼쪽이모두 A 인경우 A α 1 α 2... α k, 택일 (alternation) 규칙 예. E EOE (E) -E id O + - * / <if_statement> -> 'if' <condition> 'then' <statement> < > 안에기술된심볼, Nonterminal 사이에기술된심볼, Terminal 제 5 장 : Context-Free Grammar 6

7 유도및유도트리 문장생성, In Context-free Grammar 문장형태의스트링에생성규칙반복적용 Nonterminal 확장 산술식 E E+E E*E (E) -E id 문장을얻기위해시작심볼 E 로부터반복적으로생성규칙적용 E -E - ( E ) - ( id ) 제 5 장 : Context-Free Grammar 7

8 생성규칙오른쪽, Nonterminal 이존재 같은문장을유도하는여러가지방법이가능 유도시대치해야할 Nonterminal을선택?? 여러가지경우가존재 예. A B C D 제 5 장 : Context-Free Grammar 8

9 좌측유도 v.s 우측유도 좌측유도 (Left derivation) 문장형태의가장왼쪽에있는Nonterminal을대치 좌문장형태 (Left-sentential form) 우측유도 (Right derivation) 문장형태의가장오른쪽에있는 Nonterminal 을대치 우문장형태 (Right-sentential form) 제 5 장 : Context-Free Grammar 9

10 문장 -(id+id) 가유도되는과정 좌측유도 E -E -(E) -(E+E) -(id+e) -(id+id). 우측유도 E -E -(E) -(E+E) -(E+id) -(id+id). 제 5 장 : Context-Free Grammar 10

11 좌파스 (left parse) 좌파스 vs. 우파스 좌측유도에서적용된일련의생성규칙순서. top-down parsing 시작심볼로부터터미널생성 ( 확장, expansion) 우파스 (right parse) 우측유도에서적용된생성규칙번호의역순. bottom-up parsing 터미널로부터넌터미널로축약하여시작심볼에도착 ( 축약, reduce) 제 5 장 : Context-Free Grammar 11

12 예, a+a*a 의좌파스와우파스 1. E E + T 2. E T 3. T T * F 4. T F 5. F (E) 6. F a E E + T E E + T 1 1 T + T E + T * F 2 3 F + T E + T * a 4 6 a + T E + F * a 6 4 a + T * F E + a * a 3 6 a + F * F T + a * a 4 2 a + a * F F + a * a 6 4 a + a * a a + a * a 6 6 좌파스 : 우파스 : 제 5 장 : Context-Free Grammar 12

13 유도트리 유도트리 (Derivation Tree) 문장유도과정을트리형태로표현 생성규칙에의해적용되는문장의계층적구조 CFG G = {V N, V T, P, S} 유도트리 노드 : 문법심볼 루트 (root) 노드 : 시작심볼 S Nonterminal 심볼 최소한하나이상의자노드를가지는노드 생성규칙 A A 1 A 2... A k A 1 A 2... A k 노드 : 노드 A의자노드 제 5 장 : Context-Free Grammar 13

14 A XYZ 의유도트리, 순서트리 (Ordered tree) internal(nonterminal) node V N external(terminal) node V T {ε} 예 6, 교재 166 A X Y Z 제 5 장 : Context-Free Grammar 14

15 유도트리 문장형태에서대치되는심볼의순서에관계없이구성 생성규칙의적용순서에따라다른유도과정이존재 두개이상의유도트리가가능 a+a*a 에대한좌측유도, 그림 5.2 E E + E E E * E a + E E + E * E a + E * E a + E * E a + a * E a + a * E a + a * a a + a * a 제 5 장 : Context-Free Grammar 15

16 모호성 (Ambiguity) 모호성 (Ambiguity) 문법 G 에의해생성되는문장이두개이상의유도트리가존재 모호한문법 어떤문장이 2 개이상의유도과정이존재 예 7, 모호한문법 S if C then S else S S if C then S S a C b 제 5 장 : Context-Free Grammar 16

17 구문분석기의출력, 유도트리 문장의유도트리를결정적으로구성 모호하지않은문법 (Unambiguous Grammar) 결정적파싱 (Deterministic Parsing) 모호하지않은문법구성 모호한문법을모호하지않은문법으로변환. 제 5 장 : Context-Free Grammar 17

18 모호한문법 ( 일반적인경우 ) 생성규칙 : A AαA 문장형태 : AαAαA 트리형태 : A A A α A A α A A α A A α A 제 5 장 : Context-Free Grammar 18

19 모호하지않은문법으로변환 연산우선순위, 결합법칙 생성규칙추가 새로운 Nnonterminal 도입 제 5 장 : Context-Free Grammar 19

20 정의 문법변환 L(G 1 ) = L(G 2 ), 문법 G 1 과G 2 는동등 문법이생성하는언어가같음. 예 9, CFG G 1, G 2 는동일. G 1 : A 1B G 2 : X Y1 A 1 X 1 B 0A Y X0 L(G 1 ) = L(G 2 ) = 1(01) * 제 5 장 : Context-Free Grammar 20

21 문법변환 다른형태의동등한문법으로변환 대입 (substitution), 확장 (expansion) 대입 (substitution) 특정생성규칙을제거하고그에해당하는생성규칙추가. if A αbγ, B β 1 β 2 β 3 β n P, then P' = ( P - {A αbγ } ) {A αβ 1 γ αβ 2 γ... αβ n γ }. 제 5 장 : Context-Free Grammar 21

22 확장 (expansion) 새로운 Nonterminal 심볼을도입. 한개의생성규칙을쪼개는방법 생성규칙 A αβ 에대해 A αx, X β 혹은 A Xβ, X α X, 새로운 Nonterminal 심볼 확장의효과 유도과정의횟수를한번늘인결과 제 5 장 : Context-Free Grammar 22

23 불필요한생성규칙제거 불필요한생성규칙 (Useless production rule) 문장을생성하는데적용할수없는생성규칙 [ 정의 5. 7] CFG G = (V N, V T, P, S) S wxy wxy (w, x, y V T *) 형태의유도과정이존재하지않으면, 심볼 X 는불필요 (useless) 불필요한생성규칙 불필요한심볼 (useless symbol) 을갖고있는생성규칙 제거 (elimination) 제 5 장 : Context-Free Grammar 23

24 불필요한심볼, X 시작심볼로부터도달할수없는심볼 X가스트링을생성할수없는 Nonterminal 심볼 생성규칙 A α Α w, w V * T, A :Terminating Nonterminal S uxw, u,w V * : X, 도달가능한심볼 (accessible symbol) 필요한생성규칙 도달가능한심볼 + Terminating Nonterminal 제 5 장 : Context-Free Grammar 24

25 불필요한생성규칙제거방법 terminating nonterminal 을구함 스트링을생성할수없는 nonterminal을포함하고있는생성규칙제거 도달가능한심볼들을구성 도달불가능심볼을포함하고있는생성규칙제거 알고리즘 5.1 예제 11, 12, 13번참조 제 5 장 : Context-Free Grammar 25

26 ε- 생성규칙제거 (ε-free) A ε, ε- 생성규칙 생성규칙의형태가 A ε, 제거. CFG G=(V N, V T, P, S), ε-free. 생성규칙 P 가 ε- 생성규칙을갖지않음 S 는 ε- 생성규칙을갖지만다른생성규칙의오른쪽에 S 가나타나지않음. ε- 생성규칙제거 구문분석시간감소 ε-free 문법 제 5 장 : Context-Free Grammar 26

27 단일생성규칙제거 단일생성규칙 (single production rule) A B 생성규칙의오른쪽에한개의 nonterminal만존재 불필요한유도과정이발생, 파싱속도증가 의미없는단일생성규칙, 제거 제 5 장 : Context-Free Grammar 27

28 Proper 문법 : CFG G = ( V N, V T, P, S ) Cycle-free if there is no derivation of the form A + A ε-free 불필요한심볼을갖지않음 제 5 장 : Context-Free Grammar 28

29 문법표기법 5.4 CFG 표기법 BNF(Backus-Naur Form) 확장된 BNF(EBNF, Extended-BNF) 문법흐름도 (Syntax diagram) 제 5 장 : Context-Free Grammar 29

30 BNF 프로그래밍언어의형식적정의 Nonterminal 심볼 : < 와 > Terminal 심볼 : 문자 명칭 (Identifier) 에대한표현 <id> ::= <letter> <id> <letter> <id> <digit> <letter> ::= a b c... y z <digit> ::= ::= : : 택일 (alternation) 교재 PP. 184, 예 17 제 5 장 : Context-Free Grammar 30

31 EBNF 반복, 선택적인부분을간결하게표현 특수한의미를갖는메타심볼 (meta symbol) 도입 메타심볼 (Meta Symbol) 언어의일부분이아니라언어를표현하려고사용된특수심볼. 제 5 장 : Context-Free Grammar 31

32 반복부분 (repetitive part) 표현 { } {a} a가영번이상반복 정규표현 a * 와같은의미 콤마로구분되는명칭리스트 : BNF 및 EBNF BNF <id_list> ::= <id_list>, <id> <id> EBNF <id_list> ::= <id> {, <id> } 제 5 장 : Context-Free Grammar 32

33 혼합문에대한 BNF 및 EBNF 표현 BNF 표현 <compound_statement> ::= begin <statement_list> end <statement_list> ::= <statement_list> ; <statement> <statement> EBNF 표현 <compound_statement> ::= begin <statement> { ; <statement> } end 제 5 장 : Context-Free Grammar 33

34 반복되는최대회수와최소회수지정 <external_name> ::= <alphabet> {<alphanumeric>} 7 <alphanumeric> ::= <alphabet> <digit> <alphabet> ::= a b c y z <digit> ::= 중괄호뒤의 0 은최소회수, 7 은최대회수 제 5 장 : Context-Free Grammar 34

35 선택적인부분 (optional part) [ ] [x] x가나타나지않거나한번만나타날수있음 [x] 는 {x} 1 예 <if_st> ::= if <cond> then <stat> [else <stat>] 제 5 장 : Context-Free Grammar 35

36 단순변수, 일차원배열변수 BNF 및 EBNF 표현 BNF 표현 : <variable> ::= <id> <id> '[' <exp> ']' EBNF 표현 : <variable> ::= <id> [ '[' <exp> '] ] 제 5 장 : Context-Free Grammar 36

37 괄호와택일기호 : ( ) 여러개의생성규칙을간단히표현 <exp> ::= <exp> + <exp> <exp> - <exp> <exp> * <exp> <exp> / <exp> <exp> ::= <exp> ( + - * / ) <exp> 제 5 장 : Context-Free Grammar 37

38 EBNF 메타심볼 vs. terminal 심볼 terminal 심볼을 ' 와 ' 로묶어표현 <BNF_rule> ::= <left_part> '::=' <right_part> <right_part> ::= <right_part_element> { ' <right_part_element> } 제 5 장 : Context-Free Grammar 38

39 문법흐름도 (Syntax diagram) 문법을도식화하여표현 초보자가프로그래밍언어의문법을쉽게이해 구성 사각형 :Nonterminal 타원 : Terminal 지시선 : 문법이움직이는경로 (path) 제 5 장 : Context-Free Grammar 39

40 Nonterminal A 사각형안을 A terminal의경우와같이지시선 사각형의내용은그안의이름에의해참조 A Terminal a 타원안을 a 지시선으로연결 a 제 5 장 : Context-Free Grammar 40

41 생성규칙 A ::= X 1 X 2 X i 가 Nonterminal 인경우... X n X 1 X 2 X 3... X n X i 가 terminal 인경우 x1 x2 x3... x n 제 5 장 : Context-Free Grammar 41

42 A ::= α 1 α 2... α n α 1 A α i α n 제 5 장 : Context-Free Grammar 42

43 EBNF A ::= {α} A α EBNF A ::= [ α ] A α 제 5 장 : Context-Free Grammar 43

44 EBNF A ::= ( α1 α2 ) β α 1 A β α 2 제 5 장 : Context-Free Grammar 44

45 푸시다운오토마타 푸시다운오토마타 (Push-Down Automata; PDA) 보조기억장치를가진인식기. Context-Free Grammar 인식기. 구성 유한상태제어 (finite state control) 전체의행동제어 현재의입력심볼, 스택의 top 심볼에따라행동 입력테이프 (input tape) 입력스트링유지 스택 (stack) 보조기억장치, 푸시다운리스트 (push-down list) 제 5 장 : Context-Free Grammar 45

46 Push Down Automata, PDA Input tape a 1 a 2... a n Finite state control Z 1 Z 2 Z n stack 제 5 장 : Context-Free Grammar 46

47 PDA P = (Q, Σ, Γ, δ, q 0, Z 0, F) Q : 상태의유한집합 Σ : 입력알파벳의유한집합 Γ : 스택심볼의유한집합 δ : 사상함수 Q (Σ {ε} ) Γ Q Γ * q 0 Q : 시작상태 (start state) Z 0 Γ: 스택의시작심볼 F Q : 종결상태 (final state) 의집합 제 5 장 : Context-Free Grammar 47

48 사상함수 ( 전이함수 ) : δ, delta δ(q, a, Z) = { (p 1,α 1 ), (p 2,α 2 ),...,(p n,α n ) } 현재의상태 : q 입력심볼 : a 스택 Top 심볼 : Z (p i,α i ) 선택 현재의 q 상태에서입력 a 를본다음상태 : p i 스택 top 심볼 Z 를 α i 로대치. 제 5 장 : Context-Free Grammar 48

49 PDA 형태 (configuration) : P 어떤시점에서 PDA P 의현재상태표현방법 Q Σ * Γ * => Triple(q, ω, α) q : 현재상태 ω: 읽지않은입력부분 α: 스택의내용 ω= ε 인경우, 모든입력심볼이읽혀졌음 P 에의한상태이동 (move) : -- (q, aω, Zα) -- (q', ω,υα) 제 5 장 : Context-Free Grammar 49

50 a=ε; ε- 이동 (ε-move) 현재의입력심볼변화없음 모든입력심볼이읽혀졌을때발생 스택이빈경우, 어떤이동도발생하지않음. * : 영번이상, + : 한번이상이동 P 시작형태 Σ * 에속하는 ω, (q 0,ω,Z 0 ) P 의종결형태 (q, ε, α), q F, α Γ* 제 5 장 : Context-Free Grammar 50

51 P 의이동 (move)ː 1) a ε: (q, aω, Zα) ( q', ω, γα) 2) a = ε : (q, ε, Z) (q', ε, γ) <===> ε-move * : zero or more moves + : one or more moves 제 5 장 : Context-Free Grammar 51

52 L(P) : PDA P 에의해언어인식 (accept). 입력스트링 ω 를다본상태가종결상태 시작상태 : (q 0, ω, Z 0 ) 종결상태 : (q, ε, α), where q F, α F* L(P) = {ω (q 0, ω, Z 0 ) * (q, ε, α), q F, α Γ* }. 제 5 장 : Context-Free Grammar 52

53 인식 (accept) 시작상태에서입력스트링 ω 를다본상태가종결상태에도달 "ω 는 P 에의해인식 (accept)" P 에의해정의되는언어 푸시다운오토마타언어 : L(P) P 에의해인식되는스트링의집합 L(P) = {ω ( q 0,ω, Z 0 ) -- (q, ε, α), q F, α Γ*} 제 5 장 : Context-Free Grammar 53

54 예 26. 언어 L = {0 n 1 n n 1} 을인식하는 PDA P = ( {q 0, q 1, q 2 }, {0, 1}, {Z, 0}, δ, q 0, Z, {q 0 } ) δ(q 0, 0, Z) = { (q 1, 0Z) } δ(q 1, 0, 0) = { (q 1, 00) } δ(q 1, 1, 0) = { (q 2, ε) } δ(q 2, 1, 0) = { (q 2, ε) } δ(q 2, ε, Z) = { (q 0, ε) } 0 에대하여차례로스택에모두이동 1 에대하여스택에있는 0 을하나씩팝 (pop) 제 5 장 : Context-Free Grammar 54

55 입력스트링 0011 에대하여 P 가인식하는과정 (q 0, 0011, Z) -- (q 1, 011, 0Z) -- (q 1, 11, 00Z) -- (q 2, 1, 0Z) -- (q 2, ε, Z) -- (q 0, ε, ε) 제 5 장 : Context-Free Grammar 55

n 정의 정규표현 (Regular Expression) n 정규문법 G 를대수학적인성질로표현 n 정규언어에속해있는스트링의모양을직접기술 n 정규문법은문법이나타내는언어의형태를체계적으로구하여정규표현으로나타낼수있음. 정규문법 (Regular ) 정규표현 (Regular ) 유

n 정의 정규표현 (Regular Expression) n 정규문법 G 를대수학적인성질로표현 n 정규언어에속해있는스트링의모양을직접기술 n 정규문법은문법이나타내는언어의형태를체계적으로구하여정규표현으로나타낼수있음. 정규문법 (Regular ) 정규표현 (Regular ) 유 Regular Expression and Context-free 상지대학교컴퓨터정보공학부고광만 (kkman@mail.sangji.ac.kr) 정규문법과정규언어 n 정규문법 (Regular ) n 촘스키 (Chomsky, N.) 문법규칙 -Type 3 n 토큰구조표현 ( 어휘분석단계 ) n 정규문법의형태 1 우선형문법 (right-linear grammar;