Regular Expression and Context-free Grammar

Presentation on theme: "Regular Expression and Context-free Grammar"— Presentation transcript:

1 Regular Expression and Context-free Grammar
상지대학교 컴퓨터정보공학부 고 광 만

2 정규 문법과 정규 언어 정규 문법(Regular Grammar) 정규 문법의 형태
촘스키(Chomsky, N.) 문법 규칙-Type 3 토큰 구조 표현(어휘 분석 단계) 정규 문법의 형태 ① 우선형 문법(right-linear grammar; RLG) Nonterminal이 Terminal 뒤에 나타남 RLG: A -> tB, A -> t ② 좌선형 문법(left-linear grammar; LLG) Nonterminal이 Terminal 앞에 나타남 LLG: A -> Bt, A -> t (A,B ∈ VN 이고 t ∈ VT*)

3 정규 문법이 사용되는 이유 토큰의 구조는 간단하므로 정규 문법으로 표현 가능
정규 문법이 사용되는 이유 토큰의 구조는 간단하므로 정규 문법으로 표현 가능 Context-Free Grammar보다는 정규 문법으로부터 인식기의 구현이 쉬움. 모듈러하게 구성할 수 있음

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

5 정규 표현의 예 정규 표현 : ab* a가 나오고 b가 0번 이상 나오는 스트링 {abn| n≥0} 정규 표현 : (0+1)*
{0,1}* 정규 표현 : (a+b)*abb a와 b로 이루어지는 모든 스트링 뒤에 abb가 나오는 언어

6 명칭(identifier)의 정규 표현 특정한 형태의 스트링을 표현하는데 유용
letter={A,B, ..., Z,a,b, ...,z}, digit={0,1,2, ..., 9} letter(letter+digit)*

7 정규 표현식 G = ({S, R}, {a,b}, P, S) S → aS | bR | ε R → aS
X = αX +β 형태의 식이 존재하지 않음

8 시작 심볼 S에 대해, 식 (2)를 식 (1)에 대입. 변환 과정에 의해 L(G) 구성 S = aS + b(aS) +ε
= (a+ba)S +ε 변환 과정에 의해 L(G) 구성 S = (a+ba)S +ε = (a+ba)* L(G) = (a+ba)*

9 G = ( {S,A,B}, {a,b}, P, S )에 대한 L(G) ?
정규 문법 S → aA | bB | b A → bA |ε B → bS 정규 표현식 S = aA + bB + b .... (1) A = bA +ε (2) B = bS (3)

10 X = αX +β형태의 식 (2)를 풀면 식 (4)와 (3)을 식 (1)에 대입
A = bA +ε = b*ε = b* (4) 식 (4)와 (3)을 식 (1)에 대입 S = aA + bB + b = ab* + bbS +b = bbS + (ab* + b) = (bb)*(ab* + b) L(G) = (bb)* (ab* + b)

11 정규 표현 ? 정규 표현식 식 (3)에서 X1 = 0X2 + 1X1 +ε .... (1)

12 식 (2)에 식(4)를 대입 식 (5)를 식 (1)에 대입 L(X1) = (01*01*0 + 1)*
X2 = 01*0X1 + 1X2 = 1X2 + 01*0X1 = 1*01*0X (5) 식 (5)를 식 (1)에 대입 X1 = 01*01*0X1 + 1X1 +ε = (01*01*0 + 1)X1 +ε = (01*01*0 + 1)* L(X1) = (01*01*0 + 1)*

13 유한 오토마타(Finite Automata; FA)
언어 인식기(Language Recognizer) 스트링을 받아 스트링이 그 언어의 문장, "Yes" 인식기 중에 가장 간단한 형태 어휘 분석기의 고안/구현 a0 a1 a ai ai+1 ai an input Input head Auxiliary Storage Finite State Control

14 FA M = (Q, Σ, δ ,q0, F) 구성 요소 Q : 상태(state)들의 유한 집합 Σ : 입력 심볼의 유한 집합
Σ : 입력 심볼의 유한 집합 δ : 사상 함수(mapping function) Q×Σ→2Q(power set of Q) δ(q, a) = {p1 ,p2 , ,pn} q 상태에서 입력 a를 본 다음 상태는 p1부터 pn중 하나 선택 q0 : 시작 상태(start 또는 initial state) (q0∈Q) F : 종결 상태의 집합 (F⊆Q)

15 상태 전이 함수(state transition function)
결정적 유한 오토마타(Derteministic FA; DFA) 비결정적 유한 오토마타(Nonderteministic FA; NFA) DFA 정의 전이 함수 δ(q, a)가 다음 상태로서 오직 한 상태만 갖는 경우 δ(q, a) = {p}, δ(q, a) = p

16 DFA M = (Q, Σ ,δ, q0, F) 구성 요소 Q : 상태(state)들의 유한 집합 Σ : 입력 심볼의 유한 집합
Σ : 입력 심볼의 유한 집합 δ : 사상 함수(mapping function) Q×Σ → Q δ(q, a) = p q 상태에서 입력 a를 본 다음 상태는 p. q0 : 시작 상태(start 또는 initial state) (q0∈Q) F : 종결 상태의 집합 (F⊆Q)

17 M = ( {q0, q1, q2}, {a, b} , δ, q0, {q2} ) δ(q0, a) = q1 δ(q0, b) = q2

18 상태 전이표(transition table)
FA의 전이 함수를 행렬(matrix) 형태로 표현 행과 열은 각각 상태 집합과 입력 심볼 표시 행과 열이 교차하는 위치 : 다음 상태 전이 함수에 대한 상태 전이표 δ a b q0 q1 q2

19 전이 함수 확장 상태 q0에서 스트링 aba를 인식 Q×Σ→Q ⇒ Q×Σ*→Q 한 개의 심볼을 스트링으로 확장
δ(q, xa) = δ( δ(q,x) , a) 상태 q0에서 스트링 aba를 인식 δ(q0, aba) = δ(δ(q0, ab), a) = δ(δ(δ(q0, a), b), a)

20 δ(q0, x) = p인 경우 스트링 x는 M에 의해 인식(accept). q0로부터 x를 본 다음 상태, p
p가 종결 상태에 포함(p∈F) 스트링 x는 M에 의해 인식(accept). 시작 상태에서 주어진 스트링을 다본 상태가 종결 상태이면 스트링 인식

21 M에 의해 인식되는 언어, L(M) L(M) = {x| δ(q0, x) ∈ F}.
DFA M에 의해 인식되는 스트링 전체를 모아 놓은 집합 L(M) 정의 L(M) = {x| δ(q0, x) ∈ F}.

22 M = ( {p, q, r}, {0, 1}, δ, p, {r} )에 의한 스트링 1001, 0110 인식 ?
오토마타 상태 전이표 δ 1 p q r

23 δ(p,1001) 스트링 1001은 M에 의해 인식 δ(p,0110) 스트링 0110은 M에 의해 인식되지 못함
=δ(p, 001) = δ(q, 01) =δ(r, 1) = r ∈ F 스트링 1001은 M에 의해 인식 δ(p,0110) =δ(p, 110) = δ(p, 10) = δ(p, 0) = q ∈ F 스트링 0110은 M에 의해 인식되지 못함

24 상태 전이도(state transition diagram)
각 상태를 노드(node)로 표현 전이 함수 δ(q,a) = p 상태 q에서 p로 이동, 레이블이 a인 지시선 사용 종결 상태 : 이중 원, 시작 상태 : start 지시선 상태 전이도 표현 스트링을 인식 과정을 표현한 흐름도 스트링을 받아 들이는 인식기를 고안하는데 사용

25 예 14(PP.80)에 대한 상태 전이도 예 16, 명칭에 대한 상태 전이도 start p q r 1 0, 1 start S
1 0, 1 start S letter letter, digit A

26 Context-Free Grammar

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

28 Context-Free Grammar A → α 생성 규칙 A : Nonterminal, α : V*

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

30 A→α1|α2|...|αk, 택일(alternation) 규칙 예.
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

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

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

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

34 문장 -(id+id)가 유도되는 과정 좌측 유도 우측 유도
E ⇒ -E ⇒ -(E) ⇒ -(E+E) ⇒ -(id+E) ⇒ -(id+id). 우측 유도 E ⇒ -E ⇒ -(E) ⇒ -(E+E) ⇒ -(E+id) ⇒ -(id+id).

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

36 예, a+a*a의 좌파스와 우파스 1. E → E + T 2. E → T 3. T → T * F
4. T → F F → (E) F → a E ⇒ E + T E ⇒ E + T ⇒ T + T ⇒ E + T * F ⇒ F + T ⇒ E + T * a ⇒ a + T ⇒ E + F * a ⇒ a + T * F ⇒ E + a * a ⇒ a + F * F ⇒ T + a * a ⇒ a + a * F ⇒ F + a * a ⇒ a + a * a ⇒ a + a * a 좌파스 : 우파스 :

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

38 CFG 표기법 문법 표기법 BNF(Backus-Naur Form) 확장된 BNF(EBNF, Extended-BNF)
문법 흐름도(Syntax diagram)

39 BNF 프로그래밍 언어의 형식적 정의 Nonterminal 심볼 : < 와 > Terminal 심볼 : ‘ 문자 ’
명칭(Identifier)에 대한 표현 <id> ::= <letter> | <id> <letter> | <id> <digit> <letter> ::= a|b|c|...|y|z <digit> ::= 0|1|2|...|8|9 ::= : → | : 택일(alternation)

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

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

42 혼합문에 대한 BNF 및 EBNF 표현 BNF 표현 EBNF 표현 <compound_statement> ::=
begin <statement_list> end <statement_list> ::= <statement_list> ; <statement> | <statement> EBNF 표현 begin <statement> { ; <statement> } end

43 반복되는 최대 회수와 최소 회수 지정 중괄호 뒤의 0은 최소 회수, 7은 최대 회수
<external_name> ::= <alphabet> {<alphanumeric>}7 <alphanumeric> ::= <alphabet> | <digit> <alphabet> ::= a|b|c|…|y|z <digit> ::= 0|1|2|…|9 중괄호 뒤의 0은 최소 회수, 7은 최대 회수

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

45 단순 변수, 일차원 배열 변수 BNF 및 EBNF 표현
<variable> ::= <id> | <id> '[' <exp> ']' EBNF 표현 : <variable> ::= <id> [ '[' <exp> ']‘ ]

46 <exp> ::= <exp> ( + | - | * | / ) <exp>
괄호와 택일 기호 : ( | ) 여러개의 생성 규칙을 간단히 표현 <exp> ::= <exp> + <exp> | <exp> - <exp> | <exp> * <exp> | <exp> / <exp> <exp> ::= <exp> ( + | - | * | / ) <exp>

47 EBNF 메타 심볼 vs. terminal 심볼
<BNF_rule> ::= <left_part> '::=' <right_part> <right_part> ::= <right_part_element> { '|’ <right_part_element> }

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

49 Nonterminal A Terminal a 사각형 안을 A terminal의 경우와 같이 지시선
사각형의 내용은 그 안의 이름에 의해 참조 A Terminal a 타원안을 a 지시선으로 연결 a

50 생성 규칙 A ::= X1 X2 ... Xn Xi가 Nonterminal인 경우 Xi가 terminal인 경우 X1 X3 Xn

51 A ::= α1|α2| |αn α1 αi αn A

52 EBNF A ::= {α} EBNF A ::= [ α ] α A α A

53 EBNF A ::= ( α1 | α2 ) β α2 A α1 β

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

55 Push Down Automata, PDA Input tape a1 a2 . . . an Z1 Finite state
control Input tape Z1 stack Z2 Zn

56 PDA P = (Q, Σ, Γ, δ, q0 , Z0, F) Q : 상태의 유한 집합 Σ : 입력 알파벳의 유한 집합
Σ : 입력 알파벳의 유한 집합 Γ : 스택 심볼의 유한집합 δ : 사상 함수 Q × (Σ∪{ε} ) × Γ → Q × Γ* q0 ∈ Q : 시작 상태(start state) Z0 ∈ Γ : 스택의 시작 심볼 F ⊆ Q : 종결 상태(final state)의 집합

57 사상 함수(전이 함수) : δ, delta δ(q, a, Z) = { (p1,α1), (p2,α2), ,(pn,αn) } 현재의 상태 : q 입력 심볼 : a 스택 Top 심볼 : Z (pi,αi) 선택 현재의 q 상태에서 입력 a를 본 다음 상태 : pi 스택 top 심볼 Z를 αi로 대치.

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

59 인식(accept) 시작 상태에서 입력 스트링 ω를 다본 상태가 종결 상태에 도달 "ω는 P에 의해 인식(accept)"
푸시다운 오토마타 언어 : L(P) P에 의해 인식되는 스트링의 집합 L(P) = {ω|( q0,ω, Z0) |-- (q, ε, α), q∈F, α∈Γ*}

60 언어 L = {0n1n|n≥1}을 인식하는 PDA δ(q0, 0, Z) = { (q1, 0Z) }
P = ( {q0, q1, q2}, {0, 1}, {Z, 0}, δ , q0, Z, {q0} ) δ(q0, 0, Z) = { (q1, 0Z) } δ(q1, 0, 0) = { (q1, 00) } δ(q1, 1, 0) = { (q2, ε) } δ(q2, 1, 0) = { (q2, ε) } δ(q2, ε, Z) = { (q0, ε) } 0에 대하여 차례로 스택에 모두 이동 1에 대하여 스택에 있는 0을 하나씩 팝(pop)

61 입력 스트링 0011에 대하여 P가 인식하는 과정 (q0, 0011, Z) |-- (q1, 011, 0Z)