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..

printf 데이터를 특정한 형식에 맞춰 stdout에 출력하는 함수 int printf(const char* format, ...); 헤더 : return 출력한 문자의 개수 error : -1 형식 태그 형식 태그에 대응하는 인자를 형식 태그가 지정한 형태로 치환해 출력 format 다음으로 오는 인자들의 개수는 반드시 형식 태그의 개수보다 같거나 많아야 한다. %[flag][width][.정밀도][크기(length)]서식지정자 서식 지정자 서식 지정자 역할 자료형 %c 단일 문자 한 개 출력 char %s 문자열 출력 char * %p void * 형식의 포인터 인자(주소)를 16진수로 출력 void * %d 10진수 숫자를 출력 int %i 10진수 정수를 출력 int %u 부호 없는 10진수 숫..

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(..