KidCat

Lex Yacc What is Lex & Yacc Write Lex Operator character What is Lex & Yacc Lex Lex 는 Lexical Analyzer ( Scanner ) 생성기이다. input 으로 RE로 구성된 source specification 과 Program fragements 를 받아서 Output 으로 Program 이 나온다. 쉽게 말해서 어떤 형식에 따라 RE를 기술해주면, 그것에 맞는 C코드 파일이 Output 으로 나온다. RE 에 대한 것이 Output으로 나오므로, 스캐너를 만들어준다고 생각하면 편하다. Yacc Lex 가 Scanner 를 만들어준다면 Yacc 은 parser 를 만들어준다. Scanner 에 의해서 만들어진..

Lexical analysis Translation process Extension to Regular Expression Optional Ambiguity White Space Lexical analysis Extension to Regular Expression Lexical analysis Scanning - Input 된 소스 코드를 스캔한다. - 토큰 단위로 나눈다. ※ Token (토큰) - 의미를 가진 character (문자) 들의 집합 - Token categories : 예약어 ( Reserved words ) , Special Symbols ( operation ) , Int, double, float, delimiter (구분자) 등.. Lexical analys..

Pumping Lemma FSM ( Finite State Machine ) Pumping Length 임의의 언어 L 이 R.L 임을 어떻게 증명할 것인가 How do we prove that a Language is NOT Regular R.L 은 반드시 가져야 하는 특성 ( property ) 가 존재한다. 이 특성을 만족하지 않는다면, 그 언어는 R.L 이 아니다. 단, 이 특성을 만족한다고 해서 R.L 이 되는 것도 아니다. (필요,충분 조건에 대한 것을 배웠다면 무슨 말 인지 이해할 것이다 ) Pumping lemma 는 " 어떤 언어가 형식 언어의 규칙을 따르지 않을 때 언어가 ' 불완전하다 ' 라는 것을 보여주는 방법 " 이라고 정의 되어있다. 어떤 언어가 형식 언어의 어떤 집..

Finite Automata Accept, Reject, Target , Start state Regular Expression ( RE ) Transition Function DFA, NFA , Minimal DFA Sombrero Construction Finite Automata DFA ( Deterministic finite automata ) NFA ( Non Deterministic finite automata ) Draw DFA, NFA ( NFA -> DFA -> Minimal DFA ) Regular expression to NFA ( RE -> NFA ) Question Finite Automata ( 유한 오토마타 ) Finite automata - 간선이 alph..

계산 이론, 오토마타 이론 형식 언어 ( Formal Language ) 문법 계산 이론, 오토마타 이론 계산 이론 ( Theory of Compuation ) : 컴퓨터 과학에서 어떤 문제를 컴퓨터로 풀 수 있는지, 얼마나 효율적으로 풀 수 있는지를 탐구하는 이론 오토마타 이론 ( Theory of Automata ) : 계산 능력이 있는 추상 기계와 그 기계를 이용해서 풀 수 있는 문제들을 연구하는 컴퓨터 과학 여기서 "계산 능력이 있는 추상 기계들" 을 Automata 라고 한다. Automata 자체가 복수 표현이고 단수 표현은 Automation 이다. Automata 도 모델이 다양한데, 다른 모델의 기계가 할 수 있는 것과 없는 것을 구분하는 것이 컴퓨터 과학의 근본적인 의문중에 하나이다. ..