Regular Expression and Context-free 상지대학교컴퓨터정보공학부고광만 (kkman@mail.sangji.ac.kr) 정규문법과정규언어 n 정규문법 (Regular ) n 촘스키 (Chomsky, N.) 문법규칙 -Type 3 n 토큰구조표현 ( 어휘분석단계 ) n 정규문법의형태 1 우선형문법 (right-linear grammar; RLG) n Nonterminal 이 Terminal 뒤에나타남 n RLG: A -> tb, A -> t 2 좌선형문법 (left-linear grammar; LLG) n Nonterminal 이 Terminal 앞에나타남 n LLG: A -> Bt, A -> t (A,B V N 이고 t V T *) Lecture04_RE_CFG 2 n 정규문법이사용되는이유 n 토큰의구조는간단하므로정규문법으로표현가능 n Context-Free 보다는정규문법으로부터인식기의구현이쉬움. n 모듈러하게구성할수있음 Lecture04_RE_CFG 3 kkman@sangji.ac.kr 1
n 정의 정규표현 (Regular Expression) n 정규문법 G 를대수학적인성질로표현 n 정규언어에속해있는스트링의모양을직접기술 n 정규문법은문법이나타내는언어의형태를체계적으로구하여정규표현으로나타낼수있음. 정규문법 (Regular ) 정규표현 (Regular ) 유한오토마타 (Finite Automata) Lecture04_RE_CFG 4 n 정규표현의예 n 정규표현 : ab * n a 가나오고 b 가 0 번이상나오는스트링 n {ab n n 0} n 정규표현 : (0+1)* n {0,1}* n 정규표현 : (a+b) * abb n a 와 b 로이루어지는모든스트링뒤에 abb 가나오는언어 Lecture04_RE_CFG 5 n 명칭 (identifier) 의정규표현 n 특정한형태의스트링을표현하는데유용 n letter={a,b,..., Z,a,b,...,z}, digit={0,1,2,..., 9} n letter(letter+digit) * Lecture04_RE_CFG 6 kkman@sangji.ac.kr 2
n G = ({S, R}, {a,b}, P, S) n S as br ε n R as n 정규표현식 S = as + br +ε... (1) R = as... (2) n X = αx +β 형태의식이존재하지않음 Lecture04_RE_CFG 7 n 시작심볼 S에대해, 식 (2) 를식 (1) 에대입. S = as + b(as) +ε = as + bas +ε = (a+ba)s +ε n 변환과정에의해 L(G) 구성 n S = (a+ba)s +ε = (a+ba)* n L(G) = (a+ba)* Lecture04_RE_CFG 8 G = ( {S,A,B}, {a,b}, P, S ) 에대한 L(G)? n 정규문법 S aa bb b A ba ε B bs n 정규표현식 S = aa + bb + b... (1) A = ba +ε... (2) B = bs... (3) Lecture04_RE_CFG 9 kkman@sangji.ac.kr 3
n X = αx +β 형태의식 (2) 를풀면 A = ba +ε = b * ε = b *... (4) n 식 (4) 와 (3) 을식 (1) 에대입 S = aa + bb + b = ab* + bbs +b = bbs + (ab* + b) = (bb)*(ab* + b) L(G) = (bb)* (ab* + b) Lecture04_RE_CFG 10 정규표현? n 정규표현식 X 1 = 0X 2 + 1X 1 +ε... (1) X 2 = 0X 3 + 1X 2... (2) X 3 = 0X 1 + 1X 3... (3) n 식 (3) 에서 X 3 = 1X 3 + 0X 1 = 1*0X 1... (4) Lecture04_RE_CFG 11 n 식 (2) 에식 (4) 를대입 X 2 = 01*0X 1 + 1X 2 = 1X 2 + 01*0X 1 = 1*01*0X 1... (5) n 식 (5) 를식 (1) 에대입 X 1 = 01*01*0X 1 + 1X 1 +ε = (01*01*0 + 1)X 1 +ε = (01*01*0 + 1)* n L(X 1 ) = (01*01*0 + 1)* Lecture04_RE_CFG 12 kkman@sangji.ac.kr 4
유한오토마타 (Finite Automata; FA) n 언어인식기 (Language Recognizer) n 스트링을받아스트링이그언어의문장, "Yes" n 인식기중에가장간단한형태 n 어휘분석기의고안 / 구현 input a 0 a 1 a 2... a i a i+1 a i+2... a n Input head Finite State Control Auxiliary Storage Lecture04_RE_CFG 13 n 구성요소 n Q n Σ n δ n q 0 n F FA M = (Q, Σ, δ,q 0, F) : 상태 (state) 들의유한집합 : 입력심볼의유한집합 : 사상함수 (mapping function) n Q Σ 2 Q (power set of Q) n δ(q, a) = {p 1,p 2,...,p n } n q 상태에서입력 a 를본다음상태는 p 1 부터 p n 중하나선택 : 시작상태 (start 또는 initial state) (q 0 Q) : 종결상태의집합 (F Q) Lecture04_RE_CFG 14 n 상태전이함수 (state transition function) n 결정적유한오토마타 (Derteministic FA; DFA) n 비결정적유한오토마타 (Nonderteministic FA; NFA) n DFA 정의 n 전이함수 δ(q, a) 가다음상태로서오직한상태만갖는경우 n δ(q, a) = {p}, δ(q, a) = p Lecture04_RE_CFG 15 kkman@sangji.ac.kr 5
n 구성요소 DFA M = (Q, Σ,δ, q 0, F) n Q : 상태 (state) 들의유한집합 n Σ : 입력심볼의유한집합 n δ : 사상함수 (mapping function) n Q Σ Q n δ(q, a) = p n q 상태에서입력 a를본다음상태는 p. n q 0 : 시작상태 (start 또는 initial state) (q 0 Q) n F : 종결상태의집합 (F Q) Lecture04_RE_CFG 16 n M = ( {q 0, q 1, q 2 }, {a, b}, δ, q 0, {q 2 } ) δ(q 0, a) = q 1 δ(q 0, b) = q 2 δ(q 1, a) = q 2 δ(q 1, b) = q 0 δ(q 2, a) = q 0 δ(q 2, b) = q 1 n 상태수, 3개 : q 0, q 1, q 2 n 입력심볼 : a, b n 시작상태 : q 0 n 종결상태 : q 2 Lecture04_RE_CFG 17 n 상태전이표 (transition table) n FA의전이함수를행렬 (matrix) 형태로표현 n 행과열은각각상태집합과입력심볼표시 n 행과열이교차하는위치 : 다음상태 n 전이함수에대한상태전이표 δ a b q 0 q 1 q 2 q 1 q 2 q 0 q 2 q 0 q 1 Lecture04_RE_CFG 18 kkman@sangji.ac.kr 6
n 전이함수확장 n Q Σ Q Q Σ* Q n 한개의심볼을스트링으로확장 n δ(q, ε) = q n δ(q, xa) = δ( δ(q,x), a) n 상태 q 0 에서스트링 aba 를인식 n δ(q 0, aba) = δ(δ(q 0, ab), a) = δ(δ(δ(q0, a), b), a) Lecture04_RE_CFG 19 n δ(q 0, x) = p인경우 n q 0 로부터 x를본다음상태, p n p가종결상태에포함 (p F) n스트링 x는 M에의해인식 (accept). n 시작상태에서주어진스트링을다본상태가종결상태이면스트링인식 Lecture04_RE_CFG 20 n M 에의해인식되는언어, L(M) n DFA M 에의해인식되는스트링전체를모아놓은집합 n L(M) 정의 n L(M) = {x δ(q0, x) F}. Lecture04_RE_CFG 21 kkman@sangji.ac.kr 7
n M = ( {p, q, r}, {0, 1}, δ, p, {r} ) 에의한스트링 1001, 0110 인식? n 오토마타상태전이표 δ 0 1 p q p q r p r r r Lecture04_RE_CFG 22 n δ(p,1001) =δ(p, 001) = δ(q, 01) =δ(r, 1) = r F 스트링 1001 은 M 에의해인식 n δ(p,0110) =δ(p, 110) = δ(p, 10) = δ(p, 0) = q F 스트링 0110 은 M 에의해인식되지못함 Lecture04_RE_CFG 23 상태전이도 (state transition diagram) n 상태전이도 n 각상태를노드 (node) 로표현 n 전이함수 δ(q,a) = p n 상태 q에서 p로이동, 레이블이 a인지시선사용 n 종결상태 : 이중원, 시작상태 : start 지시선 n 상태전이도표현 n 스트링을인식과정을표현한흐름도 n 스트링을받아들이는인식기를고안하는데사용 Lecture04_RE_CFG 24 kkman@sangji.ac.kr 8
n 예 14(PP.80) 에대한상태전이도 0, 1 0 1 start p q 0 r 1 n 예 16, 명칭에대한상태전이도 letter, digit start S letter A Lecture04_RE_CFG 25 Context-Free n 정규문법 n 간단한패턴기술에적합 n 프로그래밍언어의구문구조표현에부적합 n 토큰구조 n 정규표현 n 프로그래밍언어문법구조 n Context-Free ; CFG n Context-Free 의장점 n 간단하고이해하기용이 n 표현된문법으로부터자동적으로인식기구현 n 입력된프로그램의구조를생성규칙에의해분해, 번역이유용 Lecture04_RE_CFG 27 kkman@sangji.ac.kr 9
n Context-Free n A α 생성규칙 n A : Nonterminal, α : V * n A 를문맥에관계없이 α 로대치 n context-free( 문맥 - 자유또는문맥 - 무관 ) Lecture04_RE_CFG 28 표기법 (Notational Convention) n Terminal 심볼 n 알파벳소문자 (a, b, c,... ), 숫자 ( 0,1,2,...,9) n 연산자기호 (+, -,...) n 구분자 ( 세미콜론, 콤마, 괄호 ) n ' 와 ' 사이에표기된문법심볼 n Nonterminal 심볼 n 알파벳대문자 n S, 시작심볼 (start symbol) n < 와 > 로묶어서나타낸문법심볼 n <stmt>, <expr> Lecture04_RE_CFG 29 n A α 1, A α 2,..., A α k n 생성규칙의왼쪽이모두 A 인경우 n A α 1 α 2... α k, 택일 (alternation) 규칙 n 예. n E EOE (E) -E id n O + - * / <if_statement> -> 'if' <condition> 'then' <statement> n < > 안에기술된심볼, Nonterminal n 사이에기술된심볼, Terminal Lecture04_RE_CFG 30 kkman@sangji.ac.kr 10
유도및유도트리 n 문장생성, In Context-free n 문장형태의스트링에생성규칙반복적용 n Nonterminal 확장 n 산술식 E E+E E*E (E) -E id n 문장을얻기위해시작심볼 E 로부터반복적으로생성규칙적용 E -E - ( E ) - ( id ) Lecture04_RE_CFG 31 n 생성규칙오른쪽, Nonterminal 이존재 n 같은문장을유도하는여러가지방법이가능 n 유도시대치해야할 Nonterminal 을선택?? n 여러가지경우가존재 n 예. A B C D Lecture04_RE_CFG 32 좌측유도 v.s 우측유도 n 좌측유도 (Left derivation) n 문장형태의가장왼쪽에있는 Nonterminal 을대치 n 좌문장형태 (Left-sentential form) n 우측유도 (Right derivation) n 문장형태의가장오른쪽에있는 Nonterminal 을대치 n 우문장형태 (Right-sentential form) Lecture04_RE_CFG 33 kkman@sangji.ac.kr 11
n 문장 -(id+id) 가유도되는과정 n 좌측유도 E -E -(E) -(E+E) -(id+e) -(id+id). n 우측유도 E -E -(E) -(E+E) -(E+id) -(id+id). Lecture04_RE_CFG 34 n 좌파스 (left parse) 좌파스 vs. 우파스 n 좌측유도에서적용된일련의생성규칙순서. n top-down parsing n 시작심볼로부터터미널생성 ( 확장, expansion) n 우파스 (right parse) n 우측유도에서적용된생성규칙번호의역순. n bottom-up parsing n 터미널로부터넌터미널로축약하여시작심볼에도착 ( 축약, reduce) Lecture04_RE_CFG 35 n 예, 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 1 1 T + T 2 3 F + T 4 6 a + T 6 4 a + T * F 3 6 a + F * F 4 2 a + a * F 6 4 a + a * a 6 6 E E + T E + T * F E + T * a E + F * a E + a * a T + a * a F + a * a a + a * a r 좌파스 : 1 2 4 6 3 4 6 6. r 우파스 : 6 4 2 6 4 6 3 1. Lecture04_RE_CFG 36 kkman@sangji.ac.kr 12
n 구문분석기의출력, 유도트리 n 문장의유도트리를결정적으로구성 n 모호하지않은문법 (Unambiguous ) n 결정적파싱 (Deterministic Parsing) n 모호하지않은문법구성 n 모호한문법을모호하지않은문법으로변환. Lecture04_RE_CFG 37 n 문법표기법 CFG 표기법 n BNF(Backus-Naur Form) n 확장된 BNF(EBNF, Extended-BNF) n 문법흐름도 (Syntax diagram) Lecture04_RE_CFG 38 n BNF n 프로그래밍언어의형식적정의 n Nonterminal 심볼 : < 와 > n Terminal 심볼 : 문자 n 명칭 (Identifier) 에대한표현 <id> ::= <letter> <id> <letter> <id> <digit> <letter> ::= a b c... y z <digit> ::= 0 1 2... 8 9 n ::= : n : 택일 (alternation) Lecture04_RE_CFG 39 kkman@sangji.ac.kr 13
n EBNF n 반복, 선택적인부분을간결하게표현 n 특수한의미를갖는메타심볼 (meta symbol) 도입 n 메타심볼 (Meta Symbol) n 언어의일부분이아니라언어를표현하려고사용된특수심볼. Lecture04_RE_CFG 40 n 반복부분 (repetitive part) 표현 n { } n {a} n a 가영번이상반복 n 정규표현 a * 와같은의미 n 콤마로구분되는명칭리스트 : BNF 및 EBNF n BNF <id_list> ::= <id_list>, <id> <id> n EBNF <id_list> ::= <id> {, <id> } Lecture04_RE_CFG 41 n 혼합문에대한 BNF 및 EBNF 표현 n BNF 표현 <compound_statement> ::= begin <statement_list> end <statement_list> ::= <statement_list> ; <statement> <statement> n EBNF 표현 <compound_statement> ::= begin <statement> { ; <statement> } end Lecture04_RE_CFG 42 kkman@sangji.ac.kr 14
n 반복되는최대회수와최소회수지정 <external_name> ::= <alphabet> {<alphanumeric>} 7 <alphanumeric> ::= <alphabet> <digit> <alphabet> ::= a b c y z <digit> ::= 0 1 2 9 0 n 중괄호뒤의 0 은최소회수, 7 은최대회수 Lecture04_RE_CFG 43 n 선택적인부분 (optional part) n [ ] n [x] n x 가나타나지않거나한번만나타날수있음 n [x] 는 {x} 1 n 예 <if_st> ::= if <cond> then <stat> [else <stat>] Lecture04_RE_CFG 44 n 단순변수, 일차원배열변수 BNF 및 EBNF 표현 n BNF 표현 : <variable> ::= <id> <id> '[' <exp> ']' n EBNF 표현 : <variable> ::= <id> [ '[' <exp> '] ] Lecture04_RE_CFG 45 kkman@sangji.ac.kr 15
n 괄호와택일기호 : ( ) n 여러개의생성규칙을간단히표현 <exp> ::= <exp> + <exp> <exp> - <exp> <exp> * <exp> <exp> / <exp> <exp> ::= <exp> ( + - * / ) <exp> Lecture04_RE_CFG 46 n EBNF 메타심볼 vs. terminal 심볼 n terminal 심볼을 ' 와 ' 로묶어표현 <BNF_rule> ::= <left_part> '::=' <right_part> <right_part> ::= <right_part_element> { ' <right_part_element> } Lecture04_RE_CFG 47 n 문법흐름도 (Syntax diagram) n 문법을도식화하여표현 n 초보자가프로그래밍언어의문법을쉽게이해 n 구성 n 사각형 :Nonterminal n 타원 : Terminal n 지시선 : 문법이움직이는경로 (path) Lecture04_RE_CFG 48 kkman@sangji.ac.kr 16
n Nonterminal A n 사각형안을 A n terminal 의경우와같이지시선 n 사각형의내용은그안의이름에의해참조 n Terminal a n 타원안을 a A n 지시선으로연결 a Lecture04_RE_CFG 49 n 생성규칙 A ::= X 1 X 2 n X i 가 Nonterminal인경우... X n X 1 X 2 X 3... X n n X i 가 terminal 인경우 x1 x2 x3... x n Lecture04_RE_CFG 50 n A ::= α 1 α 2... α n α 1 A α i α n Lecture04_RE_CFG 51 kkman@sangji.ac.kr 17
r EBNF A ::= {α} A α r EBNF A ::= [ α ] A α Lecture04_RE_CFG 52 n EBNF A ::= ( α1 α2 ) β α 1 A β α 2 Lecture04_RE_CFG 53 푸시다운오토마타 n 푸시다운오토마타 (Push-Down Automata; PDA) n 보조기억장치를가진인식기. n Context-Free 인식기. n 구성 n 유한상태제어 (finite state control) n 전체의행동제어 n 현재의입력심볼, 스택의 top 심볼에따라행동 n 입력테이프 (input tape) n 입력스트링유지 n 스택 (stack) n 보조기억장치, 푸시다운리스트 (push-down list) Lecture04_RE_CFG 54 kkman@sangji.ac.kr 18
n Push Down Automata, PDA Input tape a 1 a 2... a n Finite state control Z 1 Z 2 Z n stack Lecture04_RE_CFG 55 n PDA P = (Q, Σ, Γ, δ, q 0, Z 0, F) n Q : 상태의유한집합 n Σ : 입력알파벳의유한집합 n Γ : 스택심볼의유한집합 n δ : 사상함수 Q (Σ {ε} ) Γ Q Γ * n q 0 Q : 시작상태 (start state) n Z 0 Γ : 스택의시작심볼 n F Q : 종결상태 (final state) 의집합 Lecture04_RE_CFG 56 n 사상함수 ( 전이함수 ) : δ, delta δ(q, a, Z) = { (p 1,α 1 ), (p 2,α 2 ),...,(p n,α n ) } n 현재의상태 : q n 입력심볼 : a n 스택 Top 심볼 : Z n (p i,α i ) 선택 n 현재의 q 상태에서입력 a 를본다음상태 : p i n 스택 top 심볼 Z 를 α i 로대치. Lecture04_RE_CFG 57 kkman@sangji.ac.kr 19
n PDA 형태 (configuration) : P n 어떤시점에서 PDA P 의현재상태표현방법 n Q Σ * Γ * => Triple(q, ω, α) n q : 현재상태 n ω : 읽지않은입력부분 n α : 스택의내용 n ω = ε 인경우, 모든입력심볼이읽혀졌음 n P 에의한상태이동 (move) : -- (q, aω, Zα) -- (q', ω,υα) Lecture04_RE_CFG 58 n 인식 (accept) n 시작상태에서입력스트링 ω 를다본상태가종결상태에도달 n "ω 는 P 에의해인식 (accept)" n P 에의해정의되는언어 n 푸시다운오토마타언어 : L(P) n P 에의해인식되는스트링의집합 n L(P) = {ω ( q 0,ω, Z 0 ) -- (q, ε, α), q F, α Γ*} Lecture04_RE_CFG 59 n 언어 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, ε) } n 0 에대하여차례로스택에모두이동 n 1 에대하여스택에있는 0 을하나씩팝 (pop) Lecture04_RE_CFG 60 kkman@sangji.ac.kr 20
n 입력스트링 0011 에대하여 P 가인식하는과정 (q 0, 0011, Z) -- (q 1, 011, 0Z) -- (q 1, 11, 00Z) -- (q 2, 1, 0Z) -- (q 2, ε, Z) -- (q 0, ε, ε) Lecture04_RE_CFG 61 kkman@sangji.ac.kr 21