공부정리

본 내용은 아래의 출처에서 본것이고 허락을 맡고 포스트한다. 출처 : https://talkingaboutme.tistory.com/category/About%20Study/Compiler 저번 시간에 Context Free Grammar를 보았다. CFG는 Regular Expression으로 표현하기 힘든 문법들을 표현하기 위한 대체 방안으로 Syntax Tree를 그렸었다. 여기서 Left Recursive 문제가 발생하여 이를 위해 Left Factoring, 터미널을 오른쪽으로 배치해서 해결할 수 있다. 이제 아래 내용을 살펴보자. 위의 그림은 Notational Convention 이라고 한다. 이것이 정의되어 있어야 어떤 부분을 Terminal로 할지 또는 NonTerminal로 할지를 정할..

본 내용은 아래의 출처에서 본것이고 허락을 맡고 포스트한다. 출처 : https://talkingaboutme.tistory.com/category/About%20Study/Compiler 이때까지 정규 표현을 통해 NFA -> DFA를 거치는 Lexical Analysys을 알아보았다. 이제 Syntax Analysis(구문분석)로 넘어간다. 그런데 '사용자가 넣는 모든 입력들을 Syntax Analysis를 처리할 수 있느냐' 이다. 이 궁금증을 짚고 넘어가자. 예를 들어, brace {()} 의 구문일때, 정규표현으로 뽑을 수 있는 경우의 수는 (() , ((((((), ())))))) ... 등이 있을텐데 이것이 정의되기 위해서는 '(' 과 ')'의 갯수가 같아야한다. 즉, 정규표현으로 표현할 수..

본 내용은 아래의 출처에서 본것이고 허락을 맡고 포스트한다. 출처 : https://talkingaboutme.tistory.com/category/About%20Study/Compiler 이전 시간에 NFA에서 DFA로 변환하는 과정을 알아보았다. 위 그림을 기억하는가?? 오류가 있는데 위 그림에서 e가 완료 상태이다. 이 그림에서 상태 a가 initial state로 정해져 있지만, a에서 입력으로 A, B로 받는것과 c에서 입력을 A,B로 받는 것이 결과가 같다. 시작 상태가 c여도 똑같을 것이다. 이처럼 Subset Construction Algorithm은 표현할 수 있는 모든 경우의 수에 대해 DFA를 구한 것이기 때문에 불필요한 State Transition이 표현되기도 한다. 이 불필요한 ..

본 내용은 아래의 출처에서 본것이고 허락을 맡고 포스트한다. 출처 : https://talkingaboutme.tistory.com/category/About%20Study/Compiler 지난 시간, 정규 표현식을 NFA로 바꾸는 TCA(Thompson's Construction Algorithm) 에 대해 살펴보았다. NFA는 정답을 찾기 위한 모든 경우의 수를 표현한 것이라면, 여기서 확실한 정답을 찾기 위해 DFA로 바꿀 필요가 있다. 그렇다면, NFA를 DFA로 어떻게 바꿀 수 있을까?? 그것을 살펴보자. 그 전에 이때까지 우리의 과정을 나열하면 아래와 같다. NFA는 나올 수 있는 모든 Finite input set 인 '시그마' 에서 적절한 조합을 뽑아낸 것이고, DFA는 그것을 하나의 정답..

본 내용은 아래의 출처에서 본것이고 허락을 맡고 포스트한다. 출처 : https://talkingaboutme.tistory.com/category/About%20Study/Compiler 이전에 경로를 찾는데 모든 가능성을 주목한 방식이 NFA이고 진짜 정답을 찾는 것이 DFA였다. 우리는 Lexical Analysis를 통해 정규 표현식을 NFA로 거쳐 DFA를 거치는 것이다. 그렇다면 정규 표현식을 NFA 형식으로 바꾸는 방식이 있을텐데 이것이 TCA(Thompson's Construction Algorithm)이다. 정규 표현식을 가장 기본적인 단위로 쪼개어 NFA에서 정의한 방식대로 합치는 것이다. 여기서 가장 본적인 단위는 ϵ 와 'a 의 시그마' 이다. 처음 상태에서 포함된 요소를 선택하면 ..

본 내용은 아래의 출처에서 본것이고 허락을 맡고 포스트한다. 출처 : https://talkingaboutme.tistory.com/category/About%20Study/Compiler FA는 특정 문구를 뽑아내기 위한 Regular Expression이 나오면 이를 Finite State 형태로 구현하는 것 자체가 Finite Automata 라고 한다. 어떤 수식을 하나의 state Digram으로 변환해주는 과정 자체가 Finite Autoata를 구현하는 단계라고 생각하면 된다. EX) a∗b -> {b , ab, aab, aaab ...} 등이라는 것을 확인할 수 있다. 이 Finite Automata를 구성하는 요소는 처음 state와 나올 수 있는 state들도 있어야 표현가능, 각 st..

본 내용은 아래의 출처에서 본것이고 허락을 맡고 포스트한다. 출처 : https://talkingaboutme.tistory.com/category/About%20Study/Compiler Lexical Analyis에 대해 알아보고 정규 표현을 통해 코드상의 string을 뽑는 것을 알아보았다. 코드상에는 string뿐만 아니라, alphabet, keword 등 많은 요소들로 구성되어 있다. 이를 정규 표현식 방법으로 적용해 코드상에서 뽑아낼 수 있는 단어는 위의 요소들 중 하나이고 각각 정규 표현의 Union에는 포함되어 있을 것. Regulat Expression L(R) = L(keyword) | L(number) | L(identifier) | L(operator) | .... 예를 들어, e..

본 내용은 아래의 출처에서 본것이고 허락을 맡고 포스트한다. 출처 : https://talkingaboutme.tistory.com/category/About%20Study/Compiler Lexical Analysis(구문을 Token별로 잘라주는 방법)를 위한 특정 pattern이 필요 -> 정규식 방식을 사용해서 처리 구문이나 단어라고 하는 String을 나누는 예를 들어보자 ex) 'compiler' 접두사(prefix) : c로 시작하는 모든 String, -- {ε,c, co, com, ...} 접미사(suffix) : 마지막 단어를 포함하는 모든 부분 문자열, -- {ε,r, ler, compiler, ....} substring : {ε, com, omp, ...} subsequence :..

본 내용은 아래의 출처에서 본것이고 허락을 맡고 포스트한다. 출처 : https://talkingaboutme.tistory.com/category/About%20Study/Compiler 먼저, 컴파일의 단계를 정리하면, 어휘분석(스캐닝) -> 구문분석(파싱) -> 의미분석(타입검사) -> 중간코드생성기-> 최적화-> 코드생성-> 종속코드 최적화 위와 같다. 첫 번째 단계인 어휘분석에 대해 정리해보자 어휘 분석이란 컴파일러를 통해 어휘나 규칙을 정해, code stream을 구분하는 요소를 Lexeme(어휘소)라고함. 컴파일러가 기본적으로 수행하는 작업 중 하나 code stream -> Lexical Analysis -> Token stream 예시: #include int main(){ printf..

컴파일러란 어떤 특정 목적에 의해서 만든 코드를 컴퓨터가 인식할 수 있도록 컴퓨터 언어로 번역해 주는 것이다. 컴파일러 : 고급언어로 작성된 원시프로그램을 기계어로된 목적 프로그램을 출력하기 위한 번역 좀 더 설명을 하자면 컴파일이란 의미가 고급 프로그래밍언어에 쓰여진 프로그램으로 소스코드에서의 오브젝트로 변환 되는것이라고 정의한다. 오브젝트코드는 컴파일러에 의해 생성된 코드를 의미한다. 소스코드는 개발자가 사용하는 언어에 따른 명령어들의 조합 -> C/C++, Java 등 명령어 실행을 위해서 기계어로 저레벨 언어로 쓰여져여 하드웨어에서 제어가 가능하다. 고레벨언어란 개발자가 사용하는 C,C++ 등의 언어라고 생각하면 되고 저레벨 언어란 기계어 또는 어셈블리어를 의미한다. 다음은 컴파일의 과정이다. 원..