랄뚜기의 코딩일기

Automata Automata를 분류하는데 2가지 방법이 있다. 1. 현재 state에서 다음 state의 갯수에 따른 분류 - Deterministic automata : 하나의 입력을 받았을 때 다음 state는 유일 - Non-deterministic automata : 하나의 입력을 받았을 때 다음 state가 2개 이상 2. 기능적인 측면에서의 분류 - 인식기(accepter) : 입력된 결과에 대해 accept/reject 등을 표시 - 변환기(transducer) : 주어진 입력에 대응하는 새로운 문자열 출력 Finite Automata 어떤 알파벳 ∑로 부터 만들어지는 문자열의 특별한 것들을 받아들이는 시스템의 수학적 모델로서, 그 시스템에서 변화할 수 있는 상태가 유한개인 것. 컴파일러..

Chomsky hierarchy 1번 유형을 CSL(context-sensitive language), 2번 유형을 CFL(context-free language) 마지막으로 3번 유형을 RL(regular language) Regualr expression Regular expression은 union,star,concatenation 모두 가능하다. regular expression을 할 때 주의 할 점은 concatenation은 교환법칙이 성립하지 않는다는 것이다. Syntax chart BNF(Backus-Naur Form) EBNF(Extended BNF)

Alphabet Alphabet : 공집합이 아닌 기호들의 유한 집합, 시그마로 나타낸다. C언어의 알파벳은 영문 소문자, 대문자,0~9,특수문자 +,* ... String String 문자열 : 알파벳에 있는 기호들을 나열한 finite sequence이다. String Length, Concatenation of string String length는 문자열의 길이: string을 이루는 기호의 개수를 의미한다. Concatenation은 두 개의 문자열을 연결하여 새로운 문자열을 만드는 연산이다. Empty string Empty string : 공문자열이란 뜻으로 length가 0인 문자열을 의미한다. Prefix, Suffix 시그마대거 = 시그마스타 - 엡실론 Language Union of ..

컴파일러 구조 컴파일러는 위와 같은 순서로 돌아간다. 1. Scanning = Lexical Analysis(어휘 분석) - 주어진 문장이 어떤 단어를 포함하고 있는지 확인한다. 가장 작은 의미있는 단어를 'token'이라고 하는데 이를 구분한다. 2. Parsing = Syntax Analysis(구문 분석) - 추출된 token들이 문장의 구성 요소 가운데 어디에 해당하는지 확인한다. 확인하면서 Parse tree 또는 Syntax tree(구문 트리)를 생성한다. 3. Semantic Analysis(의미 분석) - 의미 분석을 수행하는 단계지만 형식 언어는 의미를 가지고 있지 않기 때문에 주로 type을 검사한다. 검사한 내용을 tree에 추가해준다. 4. Intermediate Code Gene..

배커스-나우르 표기법(Backus–Naur form), 약칭 BNF는 문맥 자유 문법을 나타내기 위해 만들어진 표기법이다. 여기에서 기호는 말단 기호가 될 수 없고, 표현식은 다른 기호의 조합, 또는 여러 가지의 표현식 중 하나를 사용한다는 의미로 |를 사용한다. 다른 표현식으로 정의되지 않은 기호는 자동적으로 말단 기호가 된다. 또한, 기호가 아닌 상수에는 따옴표를 붙여서 구별한다. Assembly 언어는 Label, OP, Operand 이렇게 3가지로 구성되어 있다. ① Label : 데이터를 기억할 기억장소, 또는 분기할 위치, 기호 상수 등에 대한 기호(Symbol)를 기술하는 부분으로 생략할 수 있다. ② OP : 명령어(OP-code)를 기술하는 부분 ③ Operand : OP-code가 연..