JJING_LOG

Top-down parsing (하향식 구문 분석) input string이 있으면, leftmost derivation을 통해 parse tree를 그린다. Recursive descent parsing Predictive parsers 하나 이상의 lookahead tokens을 사용해 input string의 다음 구성을 예측한다. LL(1), LL(k) 잘 안쓰인다. 보통 bottom-up parser를 사용하지만 이를 알기 위해선 top-down을 알아야 한다. Recursive descent parsing top-level의 non-terminal에서 시작한다. start symbol에 대한 rule을 순서대로 시도 각 단계에서, 사용할 다양한 production 선택 잘못된 선택 시 back..

Pushdown automata (PDA) context-free language (CFL)은 Pushdown automata가 허용하는 language이다. Roughly speaking : PDA == [ε-NFA + "a stack"] - FSM 과 pushdown Schematic Finite state machine Pushdown automata Stack이 왜 필요할까? L = {(0^n)(1^n) | n >= 1}이 있다고 가정, CFL language이다. 이 때 몇 번까지 읽었는지 counting을 해주는 것이 stack의 역할이다. Regular Language는 몇 번까지 읽었는지 counting을 할 수 없다. Pushdown automata (PDA) PDA는 7-tuple P ..

Why normal forms? 만약 모든 grammar의 productions이 같은 형식으로 표현된다면 grammar를 사용하는 알고리즘 디자인 용이 증명 및 특성 표시 용이 대표적인 NF 2개 Chomsky Normal Form (CNF) (춈스키 정규 형태) Greibach Normal Form (그레이바하 정규 형태) Chomsky normal form (CNF) context-free grammar G는 production이 아래와 같이 표현되는 경우 Chomsky normal form이다. A -> BC // 2개의 non-terminal로 이루어진 경우 A -> a // 하나의 terminal로 이루어진 경우 S -> ε // start symbol이 ε로 가는 경우 A, B, C ∈ VN..

Context Free Grammar (CFG) context free grammar G = (VN, VT, P, S)로 구성되어있다. V_N : non-terminal symbol의 유한개 집합 V_T : terminal symbol의 유한개 집합 VN ∩ VT = ø VN ∪ VT = V P : productions 유한 집합 a -> v, a ∈ V+, b ∈ V* a ∈ VN, b ∈ V* S : start symbol Context free language (CFL) grammar로부터 생성된 Language context free grammar G=(VN, VT, P, S)가 주어졌을 때, G에 의해 생성된 언어는 집합이다. L(G) = {w | w ∈ VT* and S =*> w} => S에..

Lex Lexical Analyzer(Scanner) Generator 스캐너 프로그램을 만드는 프로그램이다. 문장 입력 stream의 lexical processing을 위해 설계된 프로그램 생성기 Input 문자열 정규표현식에 대한 High-level specification 정규식과 관련된 프로그램 조각 Output 범용 언어로 된 프로그램 입력 스트림의 식을 인식한다. 입력 스트림을 이 식과 일치하는 문자열로 분할한다. 엄밀히 C 코드가 생성된다. An overview of Lex Source에 C 코드 추가 가능 Lex lexical analysis 단계를 수행하기 위해 parser 생성기와 함께 사용한다. Scanner : Lex가 만든다. Parser : yacc이 만든다. lexical l..

Lexical analysis (Scanning) source code를 읽고 token으로 나눈다. token : 집합적 의미를 갖는 문자 sequence token은 컴파일러의 parser에 의해 처리된다. - Token categories Reserved words : IF, THEN 등 Special symbols : +, - 등 Integers, doubles, floats, delimiters 등 - 입력 문자열에서 token을 식별한다. lexeme(string value) : token을 구성하는 실제 문자 시퀀스 token의 실제 text : "137", "int" 등 token : lexeme이 속한 general class - 오류가 거의 감지되지 않는다. 유효한 토큰, 잘못된 토큰 ..

Convert an ε-NFA to a DFA Regular expression을 -> NFA automata로 만들고 -> DFA automata로 변환 ex) - Regular expression : (a + b)*abb - ε-NFA : 1. start symbol의 ε-closure를 구해라 ε-closure(0) = {0, 1, 2, 4, 7, 8} -> A라는 state라고 하겠다. Ds = {A} -> Ds라는 곳에다가(queue라고 생각) A를 추가 아래 처럼 그림 그리기 2. Ds에 있는 element를 pop 한다. -> A 나온다. A는 {0, 1, 2, 3, 7, 8}이라는 state다. {0, 1, 2, 3, 7, 8}에서 a로 갈 수 있는 state를 찾는다. : {0, 1, 2..

Finite automata (유한 오토마타) 유한 오토마타는 edges가 다음과 같은 유한 전이 그래프다. 비공식적 표현 입력 기호의 스트림 또는 sequence에 응답하는 동안, 기계가 취할 수 있는 모든 가능한 state 및 transitions(전환)을 캡처하는 상태 다이어그램 (상태 전의도) A state에서 a 마킹시 B state가 된다. A에서 a 입력시 B로 transition한다. 이러한 state들이 유한개 있다. Recognizer for "Regular Languages" 정규 언어를 인식하는 수학적 모델 어휘 분석기 종류 2개 Deterministic finite automata Non-Deterministic finite automata Deterministic finite a..

Regular expressions (정규표현) 정규 표현은 언어(regular languages)를 설명하는 대수적 방법이다. e가 정규식이면 L(e)가 정의하는 언어다. Definition of regular expressions Basic 1 : a가 기호라면, a는 Regular expression이고, L(a) = {a} a를 regular expression으로 표현시 bold 체로 정의 Basic 2 : ε은 regular expression, L(ε) = {ε} Basic 3 : ø은 regular expression, L(ø) = ø Induction 1 : r, s가 regular expression이라면, r+s도 regular expression L(r+s) = L(r|s) = L(..

Computability, Decidability, Undecidability 모든 입력에 대해 함수가 정의되어 있는지 결정 Automata theory 계산 능력이 있는 추상 기계와 그 기계를 이용해서 풀 수 있는 문제들을 연구하는 컴퓨터 과학 "장치"는 물리적 하드웨어일 필요가 없다. 컴퓨터 과학의 근본적인 질문은 다양한 모델의 기계가 할 수 있는 것과 없는 것을 알아본다. Motivations ex) 문자열을 입력하고 다음 두 가지 가능한 답변을 반환하는 일종의 black box를 가정 Black box에 input으로 문자열 w를 입력했을 때 YES -> w는 언어에 속한다. NO -> w는 언어에 속하지 않는다. Language로부터 유효한걸 어떻게 기술할 것인가? Automaton : 언어를 ..