컴파일러구성 _통합.pdf
Document Details
Tags
Full Transcript
1강 컴파일러란? 학습내용 1 컴파일러의 개념과 번역기의 종류 2 컴파일러의 논리적 구조 3 컴파일러의 물리적 구조 4 간단한 컴파일러 실행 예 5 최적화 컴파일러의 개념과 번역기의 종류 컴파일러의 개념 컴파일러란? 언어를 번역한다. 번역기 번역기의 종류 원시프로그램 번역기...
1강 컴파일러란? 학습내용 1 컴파일러의 개념과 번역기의 종류 2 컴파일러의 논리적 구조 3 컴파일러의 물리적 구조 4 간단한 컴파일러 실행 예 5 최적화 컴파일러의 개념과 번역기의 종류 컴파일러의 개념 컴파일러란? 언어를 번역한다. 번역기 번역기의 종류 원시프로그램 번역기 목적프로그램 어셈블리어 어셈블러 기계어 고급언어 컴파일러 저급언어 고급언어 인터프리터 실행결과 고급언어 프리프로세서 고급언어 컴파일러와 인터프리터 효율적 컴파일러 기법 반복문 처리에 효과 큰 기억장소 요구 번역 후 실행 FORTRAN, COBOL, PASCAL, C, C++,JAVA 인터프리터 기법 번역과 실행 실행시간이 길다 사용자와 대화식 융통성 LISP, APL, SNOBOL 과목개설이유 컴파일러 구현의 어려움 FORTRAN 컴파일러구현 (1957 backus) 발전과정 · 연산자 우선순위문법 · bottom up : LR(K) · top down : LL(K) 영어번역과 컴파일러 영어문장 I am a Boy 단어분석 I am a Boy I am a Boy 문장분석 주어 동사 보어 의미분석 나는 소년이다. 영어번역과 컴파일러 프로그램 ABC := E ✽ 3.14 + ABC/E; 어휘분석 ABC := E ✽ 3.14 + ABC / E ; 구문분석 식별자 := 식✽식+식/식; 식별자 := 식별자✽숫자+식별자/식별자; 의미분석 기억장소 곱셈+나눗셈 목적코드 레지스터의 수 생성 컴파일러의 논리적구조 프로그램 ABC := E ✽ 3.14 + ABC/E; 어휘분석 ABC := E ✽ 3.14 + ABC / E ; 구문분석 식별자 := 산술식; 의미분석 기억장소 곱셈+나눗셈 수행시간, 기억공간 최소화 목적코드 : 레지스터의 수 생성 컴파일러의 논리적구조 프로그램 ABC := E ✽ 3.14 + ABC/E; 어휘분석 ABC := E ✽ 3.14 + ABC / E ; 구문분석 식별자 := 산술식; 의미분석 기억장소 곱셈+나눗셈 중간코드 최적화를 위한 코드 최적화 수행시간, 기억공간 최소화 목적코드 레지스터의 수 생성 컴파일러의 논리적구조 논리적 구조 6단계 고급언어 컴파일러 저급언어 어 구 의 중 코 최 휘 문 미 간 드 적 분 분 분 코 생 화 석 석 석 드 성 1. 어휘분석 기본어휘가 문법에 맞는지 분석 어휘를 토큰으로 변환 연산자, 식별자, 예약어, 구분자, 상수 어휘분석 : Lexical Analysis, Scan 어휘분석기: Lexical Analyzer, Scanner 어휘분석 예 원시프로그램 ABC := E ✽ 3.14 + ABC/E; 어휘분석 결과 10개의 토큰 ABC := E ✽ 3.14 + ABC / E ; 어휘분석 예 원시프로그램 ABC := E ✽ 3.14 + ABC/E; 어휘분석 결과 10개의 토큰 (1,0) := (1,1) ✽ (2,0) + (1,0) / (1,1) ; 2. 구문분석 구문이 문법에 맞는지 분석한다. 분석결과를 파스트리로 출력 구문분석 : Syntax Analysis, Parse 구문분석기: Syntax Analyzer, Parser 구문분석 예 ABC := E ✽ 3.14 + ABC/E; 치환문 식별자 := 식; 식별자 := 식+식; 식별자 := 식✽식+식/식; 식별자 := 식별자✽숫자+식별자/식별자; ABC := E✽3.14+ABC/E; 파스트리 parse tree 치환문 assignment statement 식별자 식 identifier := expression 식 식 expression expression + 식 식 식 식 expression ✽ expression expression / expression 식별자 숫자 식별자 식별자 identifier number identifier identifier E 3.14 ABC E 구문트리 Abstract syntax tree := ABC + ✽ / E 3.14 ABC E 3. 의미분석 파스트리에 의미부여 실행 전 사전작업 자료구조정의, 혼합형연산, 기호표 ABC := E✽3.14 + ABC/E; 4. 중간코드 최적화를 위한 중간단계 후위표현 3 주소코드 U 코드 문법지시적변환 4. 중간코드 3 주소코드: Quadruple (✽, E, 3.14, T0) ( /, ABC, E, T1) ( +, T0, T1, T2) ( :=, T2, Φ, ABC) 4. 중간코드 3 주소코드: Quadruple T0 =E,E3.14, (✽, ✽ 3.14 T0) (T1 = ABCE,/ T1) /, ABC, E (T2 +, = T0T1, T0, + T1 T2) (ABC :=, T2, Φ, ABC) := T2 5. 최적화 효율화 수행시간 최소화 기억공간 최소화 6. 목적코드 생성 사용할 레지스터의 수 계산과정 명령어 종류 컴파일러의 물리적 구조 컴파일러의 논리적 구조와 물리적구조 어휘분석 구문분석 1 패스 의미분석 중간코드 최적화 2 패스 코드생성 1-패스 컴파일러 효율성(기계코드 변환) 실행속도가 빠르다. backpatching IF (A OR B) AND C THEN 2-패스 컴파일러 이식성(Portability) 기계독립적, 최적화 기억장소 절약 기계코드 표현 제약 실행속도가 느리다. 간단한 컴파일러 실행 예 컴파일러의 실행 예 연산자우선순위 이용 과정만 설명 ABC := E＊3.14 + ABC / E; 컴파일러의 실행 예 ABC := E✽3.14 + ABC / E; 100 LOAD 201 150 3.14 101 MULT 150 : 102 STORE 160 160 103 LOAD 200 : 104 DIV 201 200 ABC 105 ADD 160 201 E 106 STORE 200 컴파일러의 실행 예 ABC := E✽3.14 + ABC / E; 100 LOAD 201 150 3.14 101 MULT 150 : 102 STORE 160 160 E＊3.14 103 LOAD 200 : 104 DIV 201 200 ABC 105 ADD 160 201 E 106 STORE 200 AC E✽3.14 컴파일러의 실행 예 ABC := E✽3.14 + ABC / E; 100 LOAD 201 150 3.14 101 MULT 150 : 102 STORE 160 160 E＊3.14 103 LOAD 200 : 104 DIV 201 200 ABC 105 ADD 160 201 E 106 STORE 200 AC ABC / E 컴파일러의 실행 예 ABC := E✽3.14 + ABC / E; 100 LOAD 201 150 3.14 101 MULT 150 : 102 STORE 160 160 E＊3.14 103 LOAD 200 : 104 DIV 201 200 ABC 105 ADD 160 201 E 106 STORE 200 AC ABC / E + E✽3.14 컴파일러의 실행 예 ABC := E✽3.14 + ABC / E; 100 LOAD 201 150 3.14 101 MULT 150 : 102 STORE 160 160 E＊3.14 103 LOAD 200 : 104 DIV 201 200 ABC 105 ADD 160 201 E 106 STORE 200 AC ABC / E + E✽3.14 컴파일러의 실행 예 ABC := E＊3.14 + ABC / E; 변수 상수 0 2 2 1 1 1 0 0 기호표 피연산자 연산자 컴파일러의 실행 예 ABC := E＊3.14 + ABC / E; 변수 상수 0 ABC 2 2 1 1 1 0 (1,0) 0 기호표 피연산자 연산자 컴파일러의 실행 예 ABC := E＊3.14 + ABC / E; 변수 상수 0 ABC 2 2 1 1 1 0 (1,0) 0 := 기호표 피연산자 연산자 컴파일러의 실행 예 ABC := E＊3.14 + ABC / E; 변수 상수 0 ABC 2 2 1 E 1 (1,1) 1 0 (1,0) 0 := 기호표 피연산자 연산자 컴파일러의 실행 예 ABC := E＊3.14 + ABC / E; 변수 상수 0 ABC 3.14 2 2 1 1 (1,1) 1 ✽ E 0 (1,0) 0 := 기호표 피연산자 연산자 컴파일러의 실행 예 ABC := E＊3.14 + ABC / E; 변수 상수 0 ABC 3.14 2 (2,0) 2 1 1 (1,1) 1 ✽ E 0 (1,0) 0 := 기호표 피연산자 연산자 컴파일러의 실행 예 ABC := E＊3.14 + ABC / E; 변수 상수 0 ABC 3.14 2 (2,0) 2 1 1 (1,1) 1 ✽ E 0 (1,0) 0 := 기호표 피연산자 연산자 컴파일러의 실행 예 ABC := E＊3.14 + ABC / E; (30,0) 변수 상수 0 ABC 3.14 2 (2,0) 2 1 1 (1,1) 1 ✽ E 0 (1,0) 0 := 기호표 피연산자 연산자 100 LOAD (1, 1) 101 MULT (2, 0) 30 E✽3.14 컴파일러의 실행 예 ABC := E＊3.14 + ABC / E; (30,0) 변수 상수 0 ABC 3.14 2 2 1 E 1 (30,0) 1 0 (1,0) 0 := 기호표 피연산자 연산자 100 LOAD (1, 1) 101 MULT (2, 0) 30 E✽3.14 컴파일러의 실행 예 ABC := E＊3.14 + ABC / E; (30,0) 변수 상수 0 ABC 3.14 2 (1,0) 2 1 1 (30,0) 1 + E 0 (1,0) 0 := 기호표 피연산자 연산자 100 LOAD (1, 1) 101 MULT (2, 0) 30 E✽3.14 컴파일러의 실행 예 ABC := E＊3.14 + ABC / E; (30,0) 변수 상수 0 ABC 3.14 2 (1,0) 2 / 1 1 (30,0) 1 + E 0 (1,0) 0 := 기호표 피연산자 연산자 100 LOAD (1, 1) 101 MULT (2, 0) 30 E✽3.14 컴파일러의 실행 예 ABC := E＊3.14 + ABC / E; (30,0) 변수 상수 3 (1,1) 0 ABC 3.14 2 (1,0) 2 / 1 1 (30,0) 1 + E 0 (1,0) 0 := 기호표 피연산자 연산자 100 LOAD (1, 1) 101 MULT (2, 0) 30 E✽3.14 컴파일러의 실행 예 ABC := E＊3.14 + ABC / E; (30,0) 변수 상수 3 (1,1) 0 ABC 3.14 2 (1,0) 2 / 1 1 (30,0) 1 + E 0 (1,0) 0 := 기호표 피연산자 연산자 100 LOAD (1, 1) 101 MULT (2, 0) 30 E✽3.14 컴파일러의 실행 예 ABC := E＊3.14 + ABC / E; (40,0) 변수 상수 3 (1,1) 0 ABC 3.14 2 (1,0) 2 / 1 1 (40,0) 1 + E 0 (1,0) 0 := 기호표 피연산자 연산자 100 LOAD (1, 1) 101 MULT (2, 0) 102 STORE (40, 0) 40 E✽3.14 30 E✽3.14 컴파일러의 실행 예 ABC := E＊3.14 + ABC / E; (40,0) 변수 상수 3 (1,1) 0 ABC 3.14 2 (1,0) 2 / 1 E 1 (40,0) 1 + 0 (1,0) 0 := 기호표 피연산자 연산자 100 LOAD (1, 1) 103 LOAD (1, 0) 101 MULT (2, 0) 104 DIV (1, 1) 102 STORE (40, 0) 40 E✽3.14 30 ABC/E 컴파일러의 실행 예 ABC := E＊3.14 + ABC / E; (40,0) (30,0) 변수 상수 3 0 ABC 3.14 2 (30,0) 2 1 E 1 (40,0) 1 + 0 (1,0) 0 := 기호표 피연산자 연산자 100 LOAD (1, 1) 103 LOAD (1, 0) 101 MULT (2, 0) 104 DIV (1, 1) 102 STORE (40, 0) 40 E✽3.14 30 ABC/E 컴파일러의 실행 예 ABC := E＊3.14 + ABC / E; (40,0) (30,0) 변수 상수 3 0 ABC 3.14 2 (30,0) 2 1 E 1 (40,0) 1 + 0 (1,0) 0 := 기호표 피연산자 연산자 100 LOAD (1, 1) 103 LOAD (1, 0) 101 MULT (2, 0) 104 DIV (1, 1) 102 STORE (40, 0) 105 ADD (40, 0) 40 E✽3.14 30 ABC/E + E✽3.14 컴파일러의 실행 예 ABC := E＊3.14 + ABC / E; (30,0) 변수 상수 3 0 ABC 3.14 2 2 1 E 1 (30,0) 1 0 (1,0) 0 := 기호표 피연산자 연산자 100 LOAD (1, 1) 103 LOAD (1, 0) 101 MULT (2, 0) 104 DIV (1, 1) 102 STORE (40, 0) 105 ADD (40, 0) 40 E✽3.14 30 ABC/E + E✽3.14 컴파일러의 실행 예 ABC := E＊3.14 + ABC / E; (30,0) 변수 상수 3 0 ABC 3.14 2 2 1 E 1 (30,0) 1 0 (1,0) 0 := 기호표 피연산자 연산자 100 LOAD (1, 1) 103 LOAD (1, 0) 101 MULT (2, 0) 104 DIV (1, 1) 102 STORE (40, 0) 105 ADD (40, 0) 106 STORE (1, 0) 컴파일러의 실행 예 100 LOAD (1,1) 101 MULT (2,0) 102 STORE (40,0) 103 LOAD (1,0) 104 DIV (1,1) 105 ADD (40,0) 106 STORE (1,0) (1,0) 200 (1,1) 201 컴파일러의 실행 예 100 LOAD 201 101 MULT (2,0) 102 STORE (40,0) 103 LOAD 200 104 DIV 201 105 ADD (40,0) 106 STORE 200 (1,0) 200 (1,1) 201 컴파일러의 실행 예 100 LOAD 201 101 MULT (2,0) 102 STORE (40,0) 103 LOAD 200 104 DIV 201 105 ADD (40,0) 106 STORE 200 (1,0) 200 (2,0) 150 (1,1) 201 (40,0) 160 컴파일러의 실행 예 100 LOAD 201 101 MULT 150 102 STORE 160 103 LOAD 200 104 DIV 201 105 ADD 160 106 STORE 200 (1,0) 200 (2,0) 150 (1,1) 201 (40,0) 160 컴파일러의 실행 예 ABC := E✽3.14 + ABC / E; 100 LOAD 201 150 3.14 101 MULT 150 : 102 STORE 160 160 103 LOAD 200 : 104 DIV 201 200 ABC 105 ADD 160 201 E 106 STORE 200 최적화 컴파일러의 실행 예 ABC := E＊3.14 + ABC / E; (30,0) 변수 상수 3 0 ABC 3.14 2 2 1 E 1 (30,0) 1 0 (1,0) 0 := 기호표 피연산자 연산자 100 LOAD (1, 1) 103 LOAD (1, 0) 101 MULT (2, 0) 104 DIV (1, 1) 102 STORE (40, 0) 105 ADD (40, 0) 40 E✽3.14 30 ABC/E + E✽3.14 컴파일러의 실행 예 ABC := E＊3.14 + ABC / E; (30,0) 변수 상수 3 0 ABC 3.14 2 103 LOAD2 (1, 0) 104 DIV 1(1, 1) 1 (30,0) 1 E 0 (1,0) 0 := 기호표 연산자 100 LOAD (1, 1) 103 LOAD (1, 0) 101 MULT (2, 0) 104 DIV (1, 1) 102 STORE (40, 0) 105 ADD (40, 0) 40,0 E✽3.14 40,1 30 ABC/E 컴파일러의 실행 예 ABC := E＊3.14 + ABC / E; (40,1) 변수 상수 3 0 ABC 3.14 2 103 LOAD2 (1, 0) 1 104 DIV 1(1, 1) (30,0) 1 E 105 STORE (40,1) 0 (1,0) 0 := 기호표 연산자 100 LOAD (1, 1) 103 LOAD (1, 0) 101 MULT (2, 0) 104 DIV (1, 1) 102 STORE (40, 0) 105 ADD (40, 0) 40,0 E✽3.14 40,1 ABC/E 30 ABC/E 컴파일러의 실행 예 ABC := E＊3.14 + ABC / E; (40,1) 변수 상수 3 0 ABC 3.14 2 103 LOAD2 (1, 0) 104 DIV (1, 1) 1 E 1 (30,0) 1 105 STORE (40,1) 0 (1,0)LOAD0 (40,0) 106 := 기호표 107 연산자 100 LOAD (1, 1) 103 LOAD (1, 0) 101 MULT (2, 0) 104 DIV (1, 1) 102 STORE (40, 0) 105 ADD (40, 0) 40,0 E✽3.14 40,1 ABC/E 30 E✽3.14 컴파일러의 실행 예 ABC := E＊3.14 + ABC / E; (40,1) 변수 상수 3 0 ABC 3.14 2 103 LOAD2 (1, 0) 104 DIV (1, 1) 1 E 1 (30,0) 1 105 STORE (40,1) 0 (1,0)LOAD0 (40,0) 106 := 기호표 107 ADD 연산자 (40,1) 100 LOAD (1, 1) 103 LOAD (1, 0) 101 MULT (2, 0) 104 DIV (1, 1) 102 STORE (40, 0) 105 ADD (40, 0) 40,0 E✽3.14 40,1 ABC/E 30 E✽3.14 + ABC/E 학습요약 1 컴파일러의 개념과 번역기의 종류 2 컴파일러의 논리적 구조 3 컴파일러의 물리적 구조 4 간단한 컴파일러 실행 예 5 최적화 다음시간안내 2강의 학습내용 1 형식언어의 기초 2 형식문법 3 문법의 표현 방법 4 정규표현과 정규문법 2강 형식언어와 형식문법 학습내용 1 형식언어의 기초 2 형식문법 3 문법의 4종류 4 문법의 표현 방법 5 정규문법과 정규표현 컴파일러 교재구성 2장 : 형식언어와 오토마타 3장 : 어휘분석 4장 : Context-free 언어와 푸시다운 오토마타 5장 : 구문분석 문법의 예(식별자) ABC := E ✽ 3.14 + ABC / E; 식별자 문 법 : 첫 글자는 영문자 영문자 + 숫자 8자 이내 문법의 예(식별자) 7 ::= {}0 ::= ｜ ::= a｜b｜c ···｜y｜z ::= 0｜1｜2 ··· ｜8｜9 예) abc BNF : - Backus Normal Form - Backus Naur Form EBNF - Extended BNF 문법의 예(식별자) 7 ::= {}0 ::= ｜ ::= a｜b｜c ···｜y｜z ::= 0｜1｜2 ··· ｜8｜9 예) abc BNF : 7 {} - Backus Normal Form 0 - Backus Naur Form EBNF - Extended BNF 문법의 예(식별자) 7 ::= {}0 ::= ｜ ::= a｜b｜c ···｜y｜z ::= 0｜1｜2 ··· ｜8｜9 예) abc BNF : 7 {} - Backus Normal Form 0 7 - Backus Naur Form {｜}0 EBNF - Extended BNF 문법의 예(식별자) 7 ::= {}0 ::= ｜ ::= a｜b｜c ···｜y｜z ::= 0｜1｜2 ··· ｜8｜9 예) abc BNF : 7 {} - Backus Normal Form 0 7 - Backus Naur Form {｜}0 2 EBNF {} 0 - Extended BNF 문법의 예(식별자) 7 ::= {}0 ::= ｜ ::= a｜b｜c ···｜y｜z ::= 0｜1｜2 ··· ｜8｜9 예) abc BNF : 7 {} - Backus Normal Form 0 7 - Backus Naur Form {｜}0 2 EBNF {} 0 - Extended BNF abc 형식언어의 기초 형식언어의 기초 알파벳 기호들의 유한 집합 문자열 기호들이 0, 1개 이상나열 형식언어 문자열들의 집합 형식언어의 기초 알파벳: T = { a, b, c } 문자열(w) : , a, ca, abc,... a = a = a 공문자열: 기호들이 0 개 나열 형식언어의 기초 알파벳: T = { a, b, c } 문자열(w) : , a, ca, abc,... an = aaaaa … a T* = { , a, b, c, aa, ab, ac, …} T스타, T클로저(closure) T+ = { a, b, c, aa, ab, ac, …} T대거(dagger) T의 형식언어 L T* 형식언어의 기초 a* = { , a, aa, aaa, aaaa, … } (a｜b)* = { , a, aa, aaa, aaaa, … b, bb, bbb, bbbb, … ab, aab, aabb, abb, … anbmakbj abbabb, …… }. 형식문법 형식문법 [예] G = ({S, A}, {0, 1}, P, S) P : S 0AS S0 A S1A A 10 A SS 형식문법 [예] G = ({S, A}, {0, 1}, P, S) P : S 0｜ 0AS A S1A A 10 A SS 형식문법 [예] G = ({S, A}, {0, 1}, P, S) P : S 0｜ 0AS A SS｜10｜S1A 형식문법 [예] G = ({S, A}, {0, 1}, P, S) P : S 0｜ 0AS A SS｜10｜S1A S0 유도, 생성한다 형식문법 [예] G = ({S, A}, {0, 1}, P, S) P : S 0｜ 0AS A SS｜10｜S1A S 0AS 유도, 생성한다 0SSS 0000 S 0,0000 형식문법 [예] G = ({S, A}, {0, 1}, P, S) P : S 0｜ 0AS A SS｜10｜S1A S 0AS 유도, 생성한다 0S1AS 0S110S 001100 S 0,0000,001100 형식문법 VN VT [예] G = ({S, A}, {0, 1}, P, S) VN : non terminal = {S,A} P : S 0｜ 0AS VT : terminal = {0,1} A SS｜10｜S1A S 0AS VN : 논터미널 기호들의 유한집합 0S1AS VT : 터미널 기호들의 유한집합 0S110S P : 생성규칙의 집합 001100 S : 시작기호 S 0,0000,001100 형식문법 형식문법 G = (VN, VT , P, S) 단, VN : 논터미널 기호들의 유한집합 VT : 터미널 기호들의 유한집합 P : 생성규칙의 집합 S : 시작기호. 문법의 4 종류 문법의 4 종류(chomsky계층구조) type 0 type 1 ,｜｜｜｜ type 2 (CFG) A , A VN type 3 (Regular Grammar) A tB or A Bt A t A t 우선형 좌선형 문법의 4 종류(chomsky계층구조) type 0 위축형 문법 포함 type 1 ,｜｜｜｜ 비위축형 문법 type 2 (CFG) Context Free Grammar A , A VN 구문분석 type 3 (Regular Grammar) A tB or A Bt 정규문법 , 어휘분석 A t A t 우선형 좌선형 문법의 4 종류(chomsky계층구조) type 0 type 1 , ｜｜｜｜ type 2 A , A VN A tB type 3 At 문법의 4 종류(chomsky계층구조) [예] G1 = ({S,A,B,C}, {a,b,c}, P, S) P: S A A abC bB bb A aABC CB BC bC bb type 1 ,｜｜｜｜ 문법의 4 종류(chomsky계층구조) [예] G1 = ({S,A,B,C}, {a,b,c}, P, S) S A, CB BC A abC, bC bb A aABC, bB bb A abC A aABC A aABC abb aabCBC aaABCBC aabbBC aaaABCBCBC S = anb2n aabbbb. 문법의 4 종류(chomsky계층구조) [예] G2 = ({S, C}, {a, b}, P, S) P : S aCa Cb C aCa type 2 (CFG) A , A VN 문법의 4 종류(chomsky계층구조) [예] G2 = ({S, C}, {a, b}, P, S) P : S aCa C b｜aCa S aCa aba aaCaa aabaa aaaCaaa aaabaaa anban. 문법의 4 종류(chomsky계층구조) [예] 식별자(EBNF) 7 ::= {}0 ::= ｜ ::= a｜b｜c ···｜y｜z ::= 0｜1｜2 ··· ｜8｜9 type 2 (CFG) A , A VN. 문법의 4 종류(chomsky계층구조) [예] G3 = ({S, B, C}, {a, b}, P, S) P : S aS ｜ aB B bC C a ｜ aC type 3 A tB, A t 문법의 4 종류(chomsky계층구조) [예] G3 = ({S, B, C}, {a, b}, P, S) P : S aS ｜ aB B bC C a ｜ aC S aB abC aba aba 문법의 4 종류(chomsky계층구조) [예] G3 = ({S, B, C}, {a, b}, P, S) P : S aS ｜ aB B bC C a ｜ aC S aB S aB abC abC abaC aba abaaC abam aba abam 문법의 4 종류(chomsky계층구조) [예] G3 = ({S, B, C}, {a, b}, P, S) P : S aS ｜ aB B bC ∴S = anbam C a ｜ aC S aB S aB S aS abC abC aaS abaC anS aba abaaC abam aba abam anS 문법의 표현방법 1. 문법도표 P : V0 aV1 V1 bV0｜a V0 a V1 V1 b V0 V1 a 1. 문법도표 P : V0 aV1 V1 bV0｜a V0 a V1 V1 b V0 b V0 V1 V1 a a 1. 문법도표 b V0 P : V0 aV1 V0 a a V1 bV0｜a V0 a V1 b V0 V1 a 1. 문법도표 b V0 P : V0 aV1 a a V1 bV0｜a V0 a a aa a abaa b ababaa 2. BNF /EBNF 표기법 예(식별자) 7 ::= {}0 식별자 ::= ｜ 문 법: 첫 글자는 영문자 ::= a｜b｜c ···｜y｜z 영문자 + 숫자 ::= 0｜1｜2 ··· 8｜9 8자 이내 예) a5c 7 {}0 BNF {｜} - Backus Normal Form - Backus Naur Form a5c 3. 정규표현 1. Ø 공집합 2. ε 3. a ∈ VT a, b ∈ VT 4. (a) (P+Q) a+b (b) (P·Q) ab (c) (P*) a*, (ab)*, (a+b)* 5. 이 밖의 정규표현은 없다. 3. 정규표현 1. Ø 공집합 0*(0+1) * 2. ε 00* (0+1) *1 3. a ∈ VT a, b ∈ VT 4. (a) (P+Q) a+b (a + b) *abb (b) (P·Q) ab (c) (P*) a*, (ab)*, (a+b)* 5. 이 밖의 정규표현은 없다. 정규문법정규표현 [예] G3 P : S aS ｜ aB B bC S = anbam C a ｜ aC S aB S aS S aB abC aaS abC aba anS abaC abaaC abam 정규문법과 정규표현 정규문법 ⇒ 정규표현 X → αX α, β: 정규표현 ε α X→β X ＝ αX ＋β의 유일해는 X ＝ α＊β 이다 정규문법 ⇒ 정규표현 문자열을 유도해 보면 X → αX X→β X→β X → αX → αβ → ααX → ααβ → αααX → αααβ → ααααX → ααααβ : ∴X ＝ α＊β 정규문법 ⇒ 정규표현 [예1] G ＝ ({S}, {a, b}, P, S) S = aS｜bS｜b = (a + b)S + b 정규표현 방정식 S → aS S → aS｜bS S → bS S → (a｜b)S 정규문법 ⇒ 정규표현 [예1] G ＝ ({S}, {a, b}, P, S) S = aS｜bS｜b = (a + b)S + b = (a+b)S + b α β X ＝ αX ＋β = (a+b)*b X ＝ α＊β 정규문법 ⇒ 정규표현 [예2] G ＝ ({S, A}, {a, b}, P, S) S aA ┃ bS A aA ┃ bA ┃ b S = aA + bS 정규표현 방정식 A = aA + bA+b 정규문법 ⇒ 정규표현 [예2] G ＝ ({S, A}, {a, b}, P, S) S = aA ＋ bS —① A = aA ＋ bA + b — ② A = (a＋b)A + b X ＝ αX ＋β α β X ＝ α＊β 정규문법 ⇒ 정규표현 [예2] G ＝ ({S, A}, {a, b}, P, S) S = aA ＋ bS —① A = aA ＋ bA + b — ② A = (a＋b)A + b = (a+b)*b X ＝ αX ＋β α β X ＝ α＊β 정규문법 ⇒ 정규표현 [예2] G ＝ ({S, A}, {a, b}, P, S) S = aA ＋ bS A= (a+b)*b = a(a+b)*b + bS = bS + a(a+b)*b X ＝ αX ＋β = b*a(a+b)*b X ＝ α＊β 정규문법 ⇒ 정규표현 [예3] G ＝ ({S, A, B}, {a, b}, P, S) S aA ┃ bS A aS ┃ bB B aB ┃ bB ┃ ε 정규문법 ⇒ 정규표현 [예3] G ＝ ({S, A, B}, {a, b}, P, S) S = aA ＋ bS —① A = aS ＋ bB —② B = aB ＋ bB ＋ ε — ③ 정규표현 방정식 정규문법 ⇒ 정규표현 S = aA ＋ bS —① A = aS ＋ bB —② B = aB ＋ bB ＋ ε — ③ B = (a＋b) B ＋ ε = (a＋b)＊ε = (a＋b)＊ — ④ α β X ＝ αX ＋β 의 유일해는 X ＝ α＊β 정규문법 ⇒ 정규표현 S = aA ＋ bS —① A = aS ＋ bB —② B = aB ＋ bB ＋ ε — ③ B = (a＋b) B ＋ ε = (a＋b)＊ — ④ S = aA+bS. 정규문법 ⇒ 정규표현 S = aA ＋ bS —① A = aS ＋ bB —② B = aB ＋ bB ＋ ε — ③ B= (a＋b) B ＋ ε = (a＋b)＊ — ④ S= aA+bS = a(aS + bB) + bS = aaS ＋ abB ＋ bS = (aa+b)S ＋ abB. 정규문법 ⇒ 정규표현 S = aA ＋ bS —① A = aS ＋ bB —② B = aB ＋ bB ＋ ε — ③ B= (a＋b) B ＋ ε = (a＋b)＊ — ④ S= aA+bS = a(aS + bB) + bS = aaS ＋ abB ＋ bS = (aa+b)S ＋ ab(a＋b)＊ α β. 정규문법 ⇒ 정규표현 S = aA ＋ bS —① A = aS ＋ bB —② B = aB ＋ bB ＋ ε — ③ B= (a＋b) B ＋ ε = (a＋b)＊ — ④ S= aA+bS X ＝ αX ＋β 의 유일해는 = a(aS + bB) + bS X ＝ α＊β = aaS ＋ abB ＋ bS = (aa+b)S ＋ ab(a＋b)＊ = (aa+b)＊ab(a ＋ b)＊ α β. 요약 1 형식언어의 기초 2 형식문법 3 문법의 4종류 4 문법의 표현 방법 5 정규문법과 정규표현 다음시간안내 3강 학습내용 1 유한오토마타 2 정규표현과 유한오토마타 3 NFA와 DFA의 동치관계 3강 유한오토마타 목차 1 유한 오토마타 2 정규표현과 유한오토마타 3 NFA와 DFA의 동치관계 4 ε–전이 NFA 5 두 개 이상의 상태전이 NFA 유한 오토마타 유한오토마타 (Finite Automata) Yes 문자열w 유한 오토마타 w ∈ L(T) No 프로그램 설계를 위한 수학적 모델 문자열이 언어의 문장인지 판단한다 유한오토마타 (Finite Automata) 식별자 ABC := E * 3.14 + ABC / E; 1. 첫자는 영자 2. 다음부터 영자와 숫자의 조합 유한오토마타 (Finite Automata) 식별자 ABC := E * 3.14 + ABC / E; 1. 첫자는 영자 2. 다음부터 영자와 숫자의 조합 a| b |c | z | 0 |1 | | 9 start q0 a| b |c | z q1 유한오토마타 (Finite Automata) a| b |c | z | 0 |1 | | 9 start q0 a| b |c | z q1 (예) abc 식별자(YES) q0 a q1 b q1 c q1 유한오토마타 (Finite Automata) a| b |c | z | 0 |1 | | 9 start q0 a| b |c | z q1 (예) b7a8 식별자(YES) q0 b q1 7 q1 a q1 8 q1 유한오토마타 (Finite Automata) a| b |c | z | 0 |1 | | 9 start q0 a| b |c | z q1 (예) b=7 식별자가 아니다(NO) q0 b q1 = 유한오토마타 (Finite Automata) 형식적 표현 a| b |c | z | 0 |1 | | 9 start q0 a| b |c | z q1 형식적 표현 M ＝ (Q, Σ, δ, q0 , F) 단, Q ＝ { q0, q1 } Σ ＝ { a, b, c, …, z, 0, 1, …, 9 } q0 ＝ q0 , F ＝ { q 1} 유한오토마타 (Finite Automata) 형식적 표현 a| b |c | z | 0 |1 | | 9 start q0 a| b |c | z q1 형식적 표현 전이함수 δ a b c …z 0 1 … 9 q0 q 1 q 1 q 1 … q 1 ø ø …ø q1 q1 q1 q1 … q1 q1 q1 … q1 유한오토마타 (Finite Automata) 형식적 표현 M ＝ (Q, Σ, δ, q0 , F) 단, Q ＝ { q0, q1 } Σ ＝ { a, b, c, …, z, 0, 1, …, 9 } q0 ＝ q0 , F ＝ { q 1} 전이함수 δ a b c …z 0 1 … 9 q0 q 1 q 1 q 1 … q 1 ø ø …ø q1 q1 q1 q1 … q1 q1 q1 … q1. 정규표현과 유한오토마타 정규표현 유한오토마타 a a A C ab (a + b) A F 정규표현 유한오토마타 a a+ A a a＊ A 정규표현 유한오토마타 ab (a + b)＊ A 정규표현 유한오토마타 (예) (a + b)＊abb a|b start a b b A B C D 유한오토마타의 단순화 (예) (a + b)＊abb a 2 3 a b b 0 1 6 7 8 9 10 11 12 13 start b 4 5 a|b start A a B b C b D 유한오토마타의 단순화 1) a a A B C A C 2) a a A B A 3) a B D A F a|b A F b C E 유한오토마타의 단순화 4) a a A B F A 5) a a A B C D A . NFA와 DFA의 동치관계 유한오토마타 (FA) 결정적 유한오토마타(DFA) 하나의 입력기호에 대하여 - Deterministic Finite Automata 한 개의 상태 전이 만 가능 비결정적 유한오토마타(NFA) 하나의 입력기호에 대하여 - Non Deterministic Finite Automata 두 개 이상의 상태 전이, - 구현이 복잡하고 성능저하 ε-전이가 있다. (예) DFA - 식별자 결정적 유한오토마타(DFA) a| b |c | z | 0 |1 | | 9 start q0 a| b |c | z q1 전이함수 δ a b c …z 0 1 … 9 q0 q 1 q 1 q 1 … q 1 ø ø …ø q1 q1 q1 q1 … q1 q1 q1 … q1 (예) NFA 비결정적 유한오토마타(NFA) 0 1 하나의 입력기호에 대하여 두 개 이상의 1 상태 전이가 나타난다. q0 q1 0 0 δ 0 1 0 0 q0 {q0, q2} {q1} q2 q1 {q0, q2} {q1} q2 {q1} {q2} 1 (예) DFA와 NFA의 동치관계 DFA와 NFA는 서로가 동등하다. DFA ⊂ NFA 이므로 NFA ⊂ DFA 임을 증명해 주면 된다. NFA(Non Deterministic FA) (1) ε-전이가 있다. c 2 3 0 1 6 d 4 5 NFA(Non Deterministic FA) (2) 두 개 이상의 상태전이 1 B A 1 C 하나의 입력기호에 대하여 두 개 이상의 상태 전이가 나타난다.. (1)ε–전이 NFA DFA 증명 (1) ε-전이 NFA a 2 3 (a + b)*abb a b b 0 1 6 7 8 9 10 11 12 13 start b 4 5 (1) ε-전이 NFA (ε-closure) a 2 3 (a + b)*abb a b b 0 1 6 7 8 9 10 11 12 13 start b 4 5 ε-closure(0) = {0,1,2,4,7,8} (1) ε-전이 NFA (ε-closure) a 2 3 (a + b)*abb a b b 0 1 6 7 8 9 10 11 12 13 start b 4 5 ε-closure(0) = {0,1,2,4,7,8} ε-closure(1) = {1,2,4}. (1) ε-전이 NFA (ε-closure) a 2 3 (a + b)*abb a b b 0 1 6 7 8 9 10 11 12 13 start b 4 5 ε-closure(0) = {0,1,2,4,7,8} ε-closure(1) = {1,2,4} ε-closure(3) = {1,2,3,4,6,7,8} (1) ε-전이 NFA (ε-closure) a 2 3 (a + b)*abb a b b 0 1 6 7 8 9 10 11 12 13 start b 4 5 ε-closure(0) = {0,1,2,4,7,8} ε-closure(1) = {1,2,4} ε-closure(5) = {5,6,7,8,1,2,4} ε-closure(3) = {1,2,3,4,6,7,8} (1) ε-전이 NFA (ε-closure) a 2 3 (a + b)*abb a b b 0 1 6 7 8 9 10 11 12 13 start b 4 5 ε-closure(0,9) = ε-closure(0)∪ε-closure(9) ε-closure(0) = {0,1,2,4,7,8} = {0,1,2,4,7,8,9,10} ε-closure(9) = {9,10} (1) ε-전이 NFA (ε-closure) a 2 3 (a + b)*abb a b b 0 1 6 7 8 9 10 11 12 13 start b 4 5 ε-closure(3) = {1,2,3,4,6,7,8} ε-closure(9) = {9,10} ε-closure(3,9) = {1,2,3,4,6,7,8, 9,10} (1) ε-전이 NFA DFA a 2 3 (a + b)*abb a b b 0 1 6 7 8 9 10 11 12 13 start b 4 5 ε-closure(0) = {0,1,2,4,7,8} = A (1) ε-전이 NFA DFA start a A 2 3 a b b 0 1 6 7 8 9 10 11 12 13 start b 4 5 ε-closure(0) = {0,1,2,4,7,8} = A (1) ε-전이 NFA DFA a start a A b 2 3 a b b 0 1 6 7 8 9 10 11 12 13 start b 4 5 ε-closure(0) = {0,1,2,4,7,8} = A (1) ε-전이 NFA DFA a start B ε-cl(3, 9) a A b 2 3 a b b 0 1 6 7 8 9 10 11 12 13 start b 4 5 ε-closure(0) = {0,1,2,4,7,8} = A ε-closure(3,9) = {3,6,1,2,4,7,8,9,10} = B (1) ε-전이 NFA DFA a start B ε-cl(3, 9) a A b 2 3 C ε-cl(5) a b b 0 1 6 7 8 9 10 11 12 13 start b 4 5 ε-closure(0) = {0,1,2,4,7,8} = A ε-closure(3,9) = {3,6,1,2,4,7,8,9,10} = B ε-closure(5) = {5,6,7,8,1,2,4} = C (1) ε-전이 NFA DFA a a B b start A C b (1) ε-전이 NFA DFA a B ε-cl(3, 9) a B b 2 3 ε-cl(3, 9) D ε-cl(5,11) a b b 0 1 6 7 8 9 10 11 12 13 start b 4 5 ε-closure(3,9) = {1,2,3,4,6,7,8,9,10} = B ε-closure(5) = {1,2,4,5,6,7,8} ε-closure(11) = {11,12} ε-closure(5,11) = {1,2,4,5,6,7,8,11,12} = D (1) ε-전이 NFA DFA a a ε-closure (3, 9) = B B b ε-cl(3, 9) ε-closure (5,11) = D start A C b ε-cl(5) (1) ε-전이 NFA DFA a b ε-closure (5,11) a B D ε-cl(3, 9) start A a C b ε-cl(5) b (1) ε-전이 NFA DFA a B ε-cl(3, 9) a C b 2 3 ε-cl(5) C ε-cl(5) a b b 0 1 6 7 8 9 10 11 12 13 start b 4 5 ε-closure(3,9) = {1,2,3,4,6,7,8,9,10} = B ε-closure(5) = {1,2,4,5,6,7,8} = C (1) ε-전이 NFA DFA a b ε-closure (5,11) a B D ε-cl(3, 9) start A a ε-closure (3, 9) = B C b ε-closure (5) = C ε-cl(5) b (1) ε-전이 NFA DFA a a b a B D b ε-cl(5,11) start A a C b b (1) ε-전이 NFA DFA a B ε-cl(3, 9) a D b 2 3 ε-cl(5,11) E ε-cl(5,13) a b b 0 1 6 7 8 9 10 11 12 13 start b 4 5 ε-closure(5,11) = {1,2,4,5,6,7,8,11,12} = D ε-closure(5) = {1,2,4,5,6,7,8} ε-closure(13) = {13} ε-closure(5,13) = {1,2,4,5,6,7,8,13} = E (1) ε-전이 NFA DFA ε-closure (3, 9) = B a a b a B D ε-cl(5,11) b start A a ε-closure (5,13)= E C b b (1) ε-전이 NFA DFA a b a B D a ε-cl(5,11) b start A a C E b ε-closure (5,13) b (1) ε-전이 NFA DFA a B ε-cl(3, 9) a E b 2 3 ε-cl(5,13) C ε-cl(5) a b b 0 1 6 7 8 9 10 11 12 13 start b 4 5 ε-closure(5,13) = {1,2,4,5,6,7,8,13} = E ε-closure(3,9) = {1,2,3,4,6,7,8,9,10} = B ε-closure(5) = {1,2,4,5,6,7,8} = C (1) ε-전이 NFA DFA a ε-cl(3, 9) b a B D a ε-cl(5,11) b start A a ε-cl(5) a ε-cl(3,9) C E b ε-cl(5,13) b ε-cl(5) b (1) ε-전이 NFA DFA a b a B D a b start A a a C E b b b (1) ε-전이 NFA DFA a b A B C B B D C B C D B E a E B C b a B D a b start A a a C E b b b. (2)두 개 이상의 상태전이 NFA (2) 두 개 이상의 상태전이 M＝( { q0, q1}, {0,1}, δ, q0 , { q1} ) δ 0 1 q0 {q0, q1} {q0} q1 ø {q0, q1} 0|1 1 1 q0 q1 0 (2) 두 개 이상의 상태전이 δ(q0,0) = {q0, q1} δ(q0,1) = {q0} δ(q1,0) =ø δ(q1,1) = {q0, q1} δ 0 1 q0 {q0, q1} {q0} q1 ø {q0, q1} (2) 두 개 이상의 상태전이 δ’([q0],0) = δ(q0 ,0) = {q0, q1} = [q0, q1] δ(q0,0) = {q0, q1} [ q0, q1] δ(q0,1) = {q0} [ q0] δ(q1,0) =ø ø δ(q1,1) = {q0, q1} [ q0, q1] δ 0 1 δ’ 0 1 q0 {q0, q1} {q0} [q0] [q0, q1] [q0] [q1] ø [q0, q1] q1 ø {q0, q1} [q0, q1] (2) 두 개 이상의 상태전이 δ(q0 ,0) ∪ δ(q1 ,0) = {q0, q1} [q0, q1] δ([q0, q1],0) = {q0, q1} [ q0, q1] δ([q0, q1],1) = {q0, q1} [ q0, q1] δ(q0 ,1) ∪ δ(q1 ,1) = {q0, q1} [q0, q1] δδ’ 0 0 1 1 q[q 0 0] {q0[q , q01, }q1] {q1[q } 0] q[q 11 ] φ ø {q0[q , q0,1}q1] [q0, q1] [q0, q1] [q0, q1] (2) 두 개 이상의 상태전이 δ´([q0], 0) = δ({q0},0) ={q0, q1} = [ q0, q1] δ´([q0], 1) = δ({q0},1) ={q0} = [ q0] δ´([q1], 0) = δ({q1},0) = ø δ´([q1], 1) = δ({q1},1) ={q0, q1} = [ q0, q1] δ´([q0, q1], 0) = δ({q0, q1},0) = [ q0, q1] δ´([q0, q1], 1) = δ({q0, q1},1) = [ q0, q1] δ´ 0 1 [ q0]=A [q1]=B [ q0, q1]=C [q0] [q0, q1] [q0] [q1] ø [q0, q1] [q0, q1] [q0, q1] [q0, q1] (2) 두 개 이상의 상태전이 [ q0]=A [q1]=B [ q0, q1]=C δ´ 0 1 δA ] [q [q 0 , q ] 1[qA ] 0 0 1 1 q[q0 ] {q0, qΦ1ø} {q [q1}, q ] 1 0 1 [qq01, q1] [q φ , q {q 0 1 ] 0, q,1}q ] [q 0 1 (2) 두 개 이상의 상태전이 [ q0]=A [q1]=B [ q0, q1]=C δ´ 0 1 δA ] [q [q 0 , q ] 1[qA ] 0 0 1 1 q[qB 0 ] {q0, qΦ1ø} {q [q1}, q ] 1 0 1 [qq01, q1] [q φ , q {q 0 1 ] 0, q,1}q ] [q 0 1 (2) 두 개 이상의 상태전이 [ q0]=A [q1]=B [ q0, q1]=C δ´ 0 1 δA ] [q [q 0 C , q ] 1[qA ] 0 0 1 1 q[qB 0 ] {q0, qΦ 1ø} {q [q 1}C 1 0, q1] [qq0C φC 1, q1] [q 0 , q 1 {q ] , qC [q 0 0,1 }q ] 1 (2) 두 개 이상의 상태전이 1 start A B 0 1 C δ´ 0 1 0|1 A C A B ø C C C C (2) 두 개 이상의 상태전이 1 start A 0 C 0|1 δ´ 0 1 A C A C C C (2) 두 개 이상의 상태전이 1 0|1 start 0 A C δ´ 0 1 A C A C C C 정규문법 요약 → 정규표현 1 유한 오토마타 → 유한오토마타 2 정규표현과 유한오토마타 3 NFA와 DFA의 동치관계 4 ε–전이 NFA 5 두 개 이상의 상태전이 NFA 다음시간안내 4강 학습내용 1 DFA 구현 2 DFA의 상태 최소화 3 동치관계 증명 4 정규문법=정규표현=DFA 4강 DFA 와 동치관계 목차 1 DFA 구현 2 DFA의 상태 최소화 3 정규문법 ⇒ 정규표현 4 정규표현 ⇒ 유한오토마타 5 유한오토마타 ⇒ 정규문법 DFA 구현 DFA의 구현(PASCAL) b start 전이함수표 S0 a a b c b c S0 S1 S0 S2 ab c S1 c S1 S2 S0 S0 a S2 S2 S0 S0 S1 DFA의 구현(PASCAL) b start 전이함수표 S0 a a b c b c S0 S1 S0 S 2 a b c S1 S1 S2 S0 S 0 c S2 S0 S0 S 1 a S2 abc 는 accept! (예) abc a b c S0 S1 S0 S2 DFA의 구현(PASCAL) b start 전이함수표 S0 a a b c b c S0 S1 S0 S 2 a b c S1 S1 S2 S0 S 0 c S2 S0 S0 S 1 a S2 aab 는 reject! (예) aab a a b S0 S1 S2 S0 DFA의 구현(PASCAL) b start 전이함수표 S0 a a b c b c S0 S1 S0 S 2 a b c S1 S1 S2 S0 S 0 c S2 S0 S0 S 1 a S2 aa 는 accept! (예) aa a a S0 S1 S2 DFA의 구현(PASCAL) program DFA(input, output) ; 전이함수표 type a b c sigma ＝ ‘a’ … ‘c’ S0 S1 S0 S 2 state ＝ (s0, s1, s2) S1 S2 S0 S 0 S2 S0 S0 S 1 var transitiontable : array[state,sigma]of state ; finalstate : set of state ; DFA의 구현(PASCAL) function deltabar(s : state) : state ; function accept : boolean ; b procedure initialize ; start S 0 a begin { main program } bc ab c initialize ; c S1 if accept then S 2 a writeln('accepted') ; else writeln('rejected') ; end. DFA의 구현(PASCAL) procedure initialize ; b begin start S0 a finalstate :＝ s2 ; bc transitiontable[s0, ‘a’] := s1 ; ab c S1 transitiontable[s0, ‘b’] := s0 ; c a transitiontable[s0, ‘c’] := s2 ; S2 transitiontable[s1, ‘a’] := s2 ; transitiontable[s1, ‘b’] := s0 ; a b c transitiontable[s1, ‘c’] := s0 ; S0 S1 S 0 S 2 transitiontable[s2, ‘a’] := s0 ; S1 S2 S 0 S 0 transitiontable[s2, ‘b’] := s0 ; transitiontable[s2, ‘c’] := s1 ; S2 S0 S 0 S 1 end ; DFA의 구현(PASCAL) aa function deltabar(s : state) : state ; function accept : boolean ; b procedure initialize ; start S 0 a begin { main program } bc ab c initialize ; c S1 if accept then S 2 a writeln('accepted') ; else writeln('rejected') ; end. DFA의 구현(PASCAL) aa function accept : boolean ; begin s2 accept :＝ deltabar(s0) in finalstate end ; b start S0 a bc ab c S1 c a S2 DFA의 구현(PASCAL) aa s0 function deltabar(s : state) : state ; var b t : state ; c : sigma ; start S0 a begin bc t := s ; s0 ab c S1 while not eoln do c begin S2 a read(c) ; t :＝ transitiontable[t, c] ; end ; deltabar := t end ; DFA의 구현(PASCAL) aa s0 function deltabar(s : state) : state ; var b t : state ; c : sigma ; start S0 a begin bc t := s ; s0 ab c S1 while not eoln do c begin S2 a read(c) ; aa s1 t :＝ transitiontable[t, c] ; a b c end ; s0 a S0 S1 S0 S2 deltabar := t S1 S2 S0 S0 end ; S2 S0 S0 S1 DFA의 구현(PASCAL) aa s0 function deltabar(s : state) : state ; var b t : state ; c : sigma ; start S0 a begin bc t := s ; s0 ab c S1 while not eoln do c begin S2 a read(c) ; aa s1 t :＝ transitiontable[t, c] ; a b c s2 end ; s0 a S0 S1 S0 S2 deltabar := t s2 s1 a S1 S2 S0 S0 end ; S2 S0 S0 S1 DFA의 구현(PASCAL) aa function accept : boolean ; b begin start S0 a true accept :＝ deltabar(s0) in s2 ab c bc S1 end ; s2 c a S2 DFA의 구현(PASCAL) aa function deltabar(s : state) : state ; function accept : boolean ; b start procedure initialize ; S 0 a bc begin { main program } ab c S1 initialize ; c a if accept then true S 2 writeln('accepted') ; else writeln('rejected') ; end.. DFA의 상태 최소화 DFA의 상태 최소화 a b A B C B B D C B C a D B E b E B C a B D a b start A a a C E b b b a 2 3 (a + b)*abb a b b 0 1 6 7 8 9 10 11 12 13 start b 4 5 ε-전이 NFA DFA 동치류 입력 A B C D E a B B B B B b C D C E C a b a B a D start b A a a C E b b b 동치류 1 2 입력 A B C D E a B B B B B b C D C E C a b a B a D start b A a a C E b b b 동치류 1 2 입력 A B C D E a B B B B B b C D C 2 C a b a B a D start b A a a C E b b b 동치류 1 2 입력 A B C D E a 1 1 1 1 1 b 1 1 1 2 1 a b a B a D start b A a a C E b b b 동치류 1 2 입력 A B C D E a 1 1 1 1 1 b 1 1 1 2 1 a b a B a D start b A a a C E b b b 동치류 1 2 3 입력 A B C D E a 1 1 1 1 1 b 1 1 1 3 1 a b a B a D start b A a a C E b b b 동치류 1 2 3 입력 A B C D E a 1 1 1 1 1 b 1 2 1 3 1 a b a B a D start b A a a C E b b b 동치류 1 2 3 입력 A C B D E a 1 1 1 1 1 b 1 1 2 3 1 a b a B a D start b A a a C E b b b 동치류 1 2 3 4 입력 A C B D E a 1 1 1 1 1 b 1 1 3 4 1 a b a B a D start b A a a C E b b b 동치류 1 2 3 4 입력 A C B D E a 2 2 2 2 2 b 1 1 3 4 1 a b a B a D start b A a a C E b b b 동치류 1 2 3 4 입력 X Y Z W a 2 2 2 2 2 b 1 1 3 4 1 a b a Y a Z start b X a a X W b b b 동치류 1 2 3 4 입력 X Y Z W a 2 2 2 2 b 1 3 4 1 a b a Y a Z start b X a a X W b b b 동치류 1 2 3 4 입력 X Y Z W a 2 2 2 2 b 1 3 4 1 a b Y a Z b a start a X W b b 동치류 1 2 3 4 입력 X Y Z W a Y Y Y Y b X Z W X a b Y a Z b a start a X W b b DFA의 상태 최소화 동치류 입력 A B C D E a B B B B B b C D C E C 동치류 1 2 3 4 입력 X Y Z W a Y Y Y Y B X Z W X DFA의 상태 최소화 a b a B a D b start A a a a b C E Y a Z b b b b a a start X W b b. 동치관계 정규문법 정규표현 유한오토마타 어휘분석기 정규문법 ⇒ 정규표현 정규문법 ⇒ 정규표현 α, β: 정규표현 ε α X ＝ αX ＋β 의 유일해는 X ＝ α＊ β X → αX X ＝ α＊β X→β 정규문법 ⇒ 정규표현 [예3] G ＝ ({S, A, B}, {a, b}, P, S) S aA ┃ bS A aS ┃ bB B aB ┃ bB ┃ ε 정규문법 ⇒ 정규표현 S = aA ＋ bS —① A = aS ＋ bB —② B = aB ＋ bB ＋ ε — ③ B= (a＋b) B ＋ ε = (a＋b)＊ — ④ S= aA + bS X ＝ αX ＋β 의 유일해는 = a(aS + bB) + bS X ＝ α＊β = aaS ＋ abB ＋ bS = (aa + b)S ＋ ab(a＋b)＊ = (aa + b)＊ab(a＋b)＊ α β. 정규표현 ⇒ 유한오토마타 정규표현 ⇒ 유한오토마타 a a A C (a + b) ab A F a a+ A a a＊ A a b (a + b)＊ A (예) (a + b)＊abb a|b start a b b A B C D. 유한오토마타 ⇒ 정규문법 유한오토마타 ⇒ 정규문법 A aC a A C A aF ab A F A bF 유한오토마타 ⇒ 정규문법 a A A aA a A aA A A 유한오토마타 ⇒ 정규문법 a|b start a b b A B C D 유한오토마타 ⇒ 정규문법 a|b start a b b A B C D P : A aA A bA A aB 유한오토마타 ⇒ 정규문법 a|b start a b b A B C D P : A aA B bC A bA C bD A aB Dε 유한오토마타 ⇒ 정규문법 G ＝ (VN, VT, P, S) 단 VN ＝ { A, B, C, D} VT ＝ {a, b} S＝ A P : A aA, A bA, A aB B bC, C bD, D ε 요약 1 DFA 구현 2 DFA의 상태 최소화 3 정규문법 ⇒ 정규표현 4 정규표현 ⇒ 유한오토마타 5 유한오토마타 ⇒ 정규문법 다음시간안내 5강 학습내용 1 어휘분석 설계 2 LEX 소개 3 LEX 실습 5강 어휘분석과 LEX 목차 1 어휘분석기 설계 2 어휘분석기 구현 3 LEX의 기능 4 LEX의 활용사례 5 LEX 실습 어휘분석기 설계 어휘 분석 어휘분석이란? 원시프로그램을 읽어 들여 토큰이라는 의미 있는 문법 단위로 분리하는 것. 정규문법이 주어지고 문법단위에 대한 토큰표를 작성한 후 DFA를 작성한다. 어휘 분석의 예 원시프로그램 ABC := E * 3.14 + ABC/E; 어휘분석 결과 10개의 토큰 ABC := E * 3.14 + ABC / E ; 어휘 분석의 예 원시프로그램 ABC := E * 3.14 + ABC/E; 어휘분석 결과 10개의 토큰 ABC := E * 3.14 + ABC / E ; (1,0) := (1,1) ＊ (2,0) + (1,0) / (1,1) ; 어휘 분석기 설계 토큰의 종류 (1) 식별자(identifier) : 프로그래머가 정의하는 변수, 이름, ABC, E ,.. (2) 상수(constant) : 정수, 실수, 문자형상수, 100, 3.14, “abc”,.. (3) 예약어(reserved word) : 구현시 이미 정의된 지정어, DO, IF, WHILE (4) 연산자(operator) : - + * / 등 (5) 구분자(delimiter) : ( [ ; : 등 단어를 구분하는기호 어휘 분석기 설계 토큰표 토큰이름 토큰번호 토큰값 BEGIN 1 CONST 2 END 3 식별자 4 기호표의 포인터 상수 5 기호표의 포인터 = 6 ; 7 b PASCAL-S 1 l/d start l 예약어표 not found 2 3 식별자 not l/d 검 색 d found d not d 4 예약어 32 33 숫자 A < > 39 = 52 38 = ( 43 49 not >,= ) 42 50 + > = 40 34 53 not = 35 41 * 36 : = 54 44 / not = 37 46 ,.. 47 55 51. 45 A not. ; 45 48 식별자 분석 b=blank b l =letter d=digit 1 l/d 식별자 l 예약어표 not found 2 검 색 3 not l/d found 4 d 예약어 d not d 32 33 숫자 A 56 57 N 58 D 15 start R R A Y 예약어표 59 60 61 7 B E 63 G 64 I 65 N 18 검 색 62 C A S E 66 67 68 23 O N S T 69 70 71 5 D I V 72 73 13 O W N T O 25 74 75 76 29 E L S E 31 77 78 22 N 79 D 10 F R 80 O 81 28 U N C T I O N 82 83 84 85 86 87 17 I F 88 20 M O D 89 90 14 N O T 91 92 19 A A 예약어표 O F 93 8 검 색 R 16 P R O C E 94 95 9698 D 99 U 100 R 101 E 12 97 G 102 R 103 A 104 M 4 R E 106 C 107 O 108 R 109 D 9 105 P 110 E 111 A 112 T 26 T 113 H E 115 N 21 114 O 30 Y 116 P 117 E 6 U 118 N 119 T 120 I 121 L 27 V A 123 R 122 11 W 124 H 125 I 126 L 127 E 24 b 식별자 분석 1 start l/d l 예약어표 not found 2 3 식별자 not l/d 검 색 d not d found 4 예약어 d 32 33 숫자 A < > 39 = 52 38 = ( 43 49 not >,= ) 42 50 + 34 > = 40 53 not = 35 41 * 36 : = 54 44 / 37 not = , 46 47... 55 51 45 A not. ; 45 48 동치관계 정규문법 정규표현 유한오토마타 어휘분석기 어휘분석기 구현 어휘분석기 구현 고려사항 문법이 명확히 정의되어야 한다. 상태전이도 순서가 중요하다: 많이 사용되는 토큰을 구별해야(확률개념) 구문분석기와 어휘분석기의 호출순서 실수의 내부표현 문제 문자 검사와 분석 시간 단축 문제 컴파일러 구현 언어와 목적기계(하드웨어)가 발달할수록 많은 컴파일러가 필요하다. 예를 들어, N개의 언어를 M개의 컴퓨터에서 구현하려면 N*M개의 컴파일러가 필요하다. 컴파일러 구현 ▶ 2개의 언어 : Java, C ▶ 3개의 목적기계 : VAX, IBM, Intel 80586 다음과 같은 6개의 컴파일러가 필요하다. Java-to-VAX Java-to-IBM Java-to-Intel 80586 C-to-VAX C-to-IBM C-to-Intel 80586 어휘분석기 구현방법 프로그래밍 언어를 이용하여 직접 구현 컴파일러 자동화 도구를 이용하여 구현 어휘분석기 생성기 종류 - LEX - FLEX - ScanGen - PCLEX - JLEX 어휘분석기 생성기 LEX : 1975년에 M.E.Lesk가 고안. 토큰을 구분하는 프로그램 작성도구. 원시프로그램 토큰구조 (정규표현) LEX 어휘분석기 (Scanner) 일련의 토큰. LEX의 기능 LEX의 기능 http://www.abxsoft.com/ 정규표현(*.l) LEX 어휘분석용 소스프로그램 (lex.yy.c) 컴파일 원시프로그램 어휘분석기 일련의 토큰 LEX의 형식 { 정의부분 } %% //규칙시작표시, 생략불가능 { 규칙부분 } //규칙부분 ::= 정규표현 + 수행코드 %% { 사용자 부프로그램 } 정의부분 파일명: test.l %{ #include #include enum tnumber {TEOF, TIDEN, TNUM, TASSIGN, TADD, TPOINT, TMUL, TDIV, TSEMI, TDOT, TBEGIN, TEND, TERROR}; %} letter [a-zA-Z] digit [0-9] 규칙부분 파일명: test.l %% begin return(TBEGIN); end return(TEND); {letter}({letter}|{digit})* return(TIDEN); “:=” return(TASSIGN); “+” return(TADD); “*” return(TMUL); “/” return(TDIV); {digit}+ return(TNUM); : 사용자 부프로그램 부분 파일명: test.l %% main() { enum tnumber tn; / * token number */ printf(“ Start of LEX \ n”); while ((tn = yylex() != TEOF) switch (tn) { case TBEGIN: printf(“Begin \ n”); break; case TEND : printf(“End \ n”); break; case TIDEN : printf(“Identifier : %s\ n”, yytext); break; : [ ] 문자들의 classes 정의 - (dash) : 구간 표시. [a-z0-9] 모든 소문자와 숫자 표시. ^ (hat) : negate 또는 complement. [^a-zA-Z] letter가 아닌 어떤 문자. \ (backslash) : escape. * , + 반복 표현 a* a를 0번 이상 {letter}({letter}|{digit})* a+ a를 1번 이상 {digit}+ LEX 수행코드 정규표현이 매칭되면 즉, 토큰이 인식되었을 때 실행해야 할 행동을 C언어로 기술하는 부분 수행코드 구성 – 전역변수 – 함수 – I/O 루틴 (입출력함수) 전역변수 yytext 정규표현과 매칭된 실제 문자열 보관 변수 [a-z]+ printf(“%s”, yytext); yyleng 매칭된 문자열의 길이를 저장하는 변수 yytext[yyleng-1] 매칭된 스트링의 마지막 문자. LEX의 활용 사례 LEX 예제1 원시프로그램(data1) ABC := E * 3.14 + ABC/E; 결과 : 토큰 List(10개) ABC + := ABC E / * E 3.14 ; 정의부분 파일명: test.l %{ #include #include enum tnumber {TEOF, TIDEN, TNUM, TASSIGN, TADD, TPOINT, TMUL, TDIV, TSEMI, TDOT, TBEGIN, TEND, TERROR}; %} letter [a-zA-Z] digit [0-9] 규칙부분 파일명: test.l %% begin return(TBEGIN); end return(TEND); {letter}({letter}|{digit})* return(TIDEN); “:=” return(TASSIGN); “+” return(TADD); “*” return(TMUL); “/” return(TDIV); {digit}+ return(TNUM); “;” return(TSEMI); \. return(TDOT); [ \t\n] ;. return(TERROR); 사용자 부프로그램 부분 파일명: test.l %% main() { enum tnumber tn; printf(“ Start of LEX \n”); while ((tn = yylex() != TEOF) switch (tn) { case TBEGIN: printf(“Begin \n”); break; case TEND : printf(“End \n”); break; case TIDEN : printf(“Identifier : %s\n”, yytext); break; case TASSIGN: printf(“Assign_op \n”); break; 사용자 부프로그램 부분 파일명: test.l case TADD : printf(“Add_op \n”); break; case TMUL : printf(“Mul_op \n”); break; case TDIV : printf(“Div_op \n”); break; case TNUM : printf(“Number: %s\n”, yytext); break; case TSEMI : printf(“Semicolon \n”); break; case TDOT : printf(“Dot \n”); break; case TERROR: printf(“Error \n”); break; } yywrap() {printf(“ End of LEX \n”); return 1; } } 실행절차 Compiler LEX명세 (test.l) LEX test.c C++ test.exe library PC환경에서 실행 C > PCL32 -i test.l C > 컴파일(C 언어) test.c C > test < data1 실행결과 ABC := E * 3.14 + ABC/E; 원시프로그램 data1 Start of LEX Identifier : ABC Assign_op Identifier : E MUL_op Number : 314 Add_op Identifier : ABC DIV_op Identifier : E Semicolon End of LEX LEX 예제2 원시프로그램 data2 This is a simple word counting program. 단어와 문자 줄의 수 계산 This is a simple word counting program. 출력결과: ▶줄1 ▶ 단어 7 ▶ 문자 39 정의부분 파일명:WordCount.l %{ unsigned charCount =0, wordCount = 0, lineCount = 1; %} word [^ \t\n]+ eol \n 규칙부분 파일명:WordCount.l %% {word} {wordCount++; charCount +=yyleng;} {eol} {charCount++; lineCount++;}. charCount++; 사용자 부프로그램 부분 파일명:WordCount.l %% main() { yylex(); printf("%d %d %d\n", lineCount, wordCount, charCount); } PC환경에서 실행 및 결과 C > PCL32 -i WordCount.l C > 컴파일(C 언어) WordCount.c C > WordCount < data2 ▶줄1 C > 1 7 39 ▶ 단어 7 ▶ 문자 39 원시프로그램 data2 This is a simple word counting program.. LEX 실습 요약 1 어휘분석기 설계 2 어휘분석기 구현 3 LEX의 기능 4 LEX의 활용사례 5 LEX 실습 다음시간안내 6강 학습내용 1 Context-free 문법의 효율화 2 유도트리와 모호성 3 불필요한 생성규칙 4 ε생성규칙 / 단일생성규칙 5 Left-factoring / Left-recursion 6 Push-Down Automata 6강 C
