Context free grammar(CFG) $G = (V_N, V_T, P,S)$ $V_N$ : non-terminal symbols들의 집합 $V_T$ : terminal symbols들의 집합 $V_N \cap V_T = \varnothing, V_N \cup V_T = V$ $P$ : productions $\alpha \rightarrow \beta, \alpha \in V^+, \beta \in V^*$ $\alpha \in V_N, \beta \in V^*$ $S$ : 시작 기호(non-terminal symbol) Context free language(CFL) context free grammar에 의해 생성된 언어 $L(G) = \{w|w \in V_T^*\space and\space..

Lex란? 어휘 분석기(Scanner)를 생성하는 프로그램 문자 입력 스트림의 어휘적 처리를 위해 디자인된 프로그램 생성기 입력 : 정규 표현, 일부 코드 출력 : 프로그램 source(정규표현, 일부 코드 조각) → lex → yylex(프로그램을 만드는 분석기) 입력 → yylex → 출력 어휘 분석 단계를 수행하기 위해 파서 생성기와 함께 사용됨 lex : 정규 표현만 인식 Yacc : context free grammar를 인식하는 parser 생성 입력 토큰을 인식하기 위한 저수준의 분석기가 필요 어휘 수준에서 변환, 분석, 통계정보 수집을 위해 단독으로 사용됨 Lex with Yacc 통계정보를 위한 Lex Lex의 일반적인 형식 {definitions} %% {rules} %% {user s..

어휘 분석(Lexical analysis, Scanning) 소스코드를 읽고 토큰으로 나누는 것 토큰 : 의미를 가지는 문자열 토큰은 파서에서 처리 토큰 종류 예약어 : if, then 특별한 기호 : +, -, ... integer, double, float, 구분자 입력된 문자열에서 토큰을 인식 lexeme : 토큰을 구성하는 실제 문자열 token : lexeme이 속하는 일반적인 클래스 에러가 거의 감지되지 않음 유효한 토큰 or 유효하지 않은 토큰 위치를 벗어난 토큰, 선언되지 않은 변수, 철자가 틀린 키워드 등을 찾을 수 없음 정규 표현의 확장 1번 이상 반복 $(0+1)(0+1)^* or (0|1)(0|1)^* \rightarrow (0|1)+$ 어떤 문자 메타문자 .(period) : 매칭..

Finite automata 유한오토마타(Finite automata) 정규 언어인지 아닌지 판단하는 인식기 유한 전이 그래프 유한개의 상태들 특정 상태에서 어떤 입력을 받으면 다른 상태로 전이하는 것을 표현 시작 상태에서 목표 상태까지 도달이 가능하면 인식이 가능한 언어이고, 도달할 수 없으면 인식 불가능한 언어 정규 언어를 인식하는 수학적 모델 어휘분석기 사용 Deterministic / Non-Deterministic finite automata Deterministic finite automata(DFA) $D = (Q,\Sigma, \delta, q_0, F)$ $Q$ : 상태들의 집합 $\Sigma$ : 입력 기호(알파벳)들의 집합 $\delta$ : 전이 함수, $\delta : Q \tim..

Regular expressions(정규표현) 정규표현(Regular expression) 정규언어를 표현하는 대수적인 방법 e가 정규표현이면 L(e)는 e를 정의하는 언어 정규표현의 정의 a가 어떤 기호이면, a는 정규표현이고, L(a) = {a} $\epsilon$은 정규 표현이고, L($\epsilon$) = {$\epsilon$} $\varnothing$은 정규 표현이고, L($\varnothing$) = $\varnothing$ 유도식 r과 s가 정규 표현이면, r+s도 정규 표현이고, $L(r+s) = L(r) + L(s)$ + 대신에 | 를 쓰기도 한다. L(r|s) = L(r) $\cup$ L(s) {r, s} r과 s가 정규 표현이면, rs도 정규 표현이고, $L(rs) = L(r)L(s..

Theory of Computation 계산 이론 Computability, Decidabillity, Undecidability 계산 가능한 함수인가? 함수가 종료 가능한가? 증명이 무엇인가? Languages and Automata 언어란 무엇인가? 언어를 어떻게 정의하는가? 언어 안의 단어를 어떻게 인식할 것인가? Complexity 공간과 시간을 너무 많이 사용하면 안 됨 P (polynomial time)= NP(non-deterministic polynomial time) 계산 가능성, 결정 가능성, 결정불가능성 함수가 모든 입력에 대해 정의되는지 결정하는 것은 어려움 3n + 1문제 오토마타 이론(Automata theory) 계산 능력이 있는 추상기계와 그 기계를 이용해서 풀 수 있는 문제..