SYDev

경희대학교 허선영 교수님의 컴파일러 수업을 기반으로 정리한 글입니다. 0. BackgroundsProcess in MemoryMemory LayoutText section: 프로그램 코드Data section: (uninitialized and initialized) 전역 변수Stack section: 일시적 데이터함수 파라미터, 리턴 어드레스, 지역 변수Heap section: 런타임에 동적으로 할당되는 메모리ELF File FormatExcecutable and Linkable Formatsource program -> compiler -> target binarytarget binary의 포맷 중 하나가 ELF컴파일 결과를 sections 나누어서 저장단순히 machine codes만 저장하는 것이..

경희대학교 한치근 교수님의 알고리즘 수업을 기반으로 정리한 글입니다. Dynamic Programmingdivide-and-conquer(분할정복식, 재귀): top-down 해결법Dynamic Programming: bottom-up 해결법작은 문제 해결 먼저 -> 결과를 큰 문제의 해결로 확산재귀 관계식(recursive property) 정립작은 사례를 먼저 해결하는 상향식 방법으로 진행 1. 이항계수 구하기문제: 이항계수를 계산입력: 음수가 아닌 정수 n과 k, 여기서 k 출력: bin, nCk- 시간복잡도(분할정복식 접근방법)귀납증명에 따라, nCk를 구하기 위해서 알고리즘이 계산하는 항(term)의 개수는 2*nCk - 1 - 동적계획법 알고리즘 설계전략recursive property 정립n..

경희대학교 한치근 교수님의 알고리즘 수업을 기반으로 정리한 글입니다. 분할정복(Divide-and-Conquer)식 설계 전략분할(Divide): 해결하기 쉽도록 문제를 여러 개의 작은 부분으로 나눔정복(Conquer): 나눈 작은 문제를 각각 해결통합(Combine): (필요하다면) 해결된 해답을 모음-> 이런 문제 해결 방법을 하향식(top-down) 접근방법이라 함 1. 이분검색(binary search): 재귀식 방식설계 전략x가 배열의 중간에 위치한 항목과 같으면 stop, 그렇지 않으면Divide: 배열을 반으로 나누어 x와 중앙값을 비교하여 배열 반쪽을 선택Conquer: 선택된 반쪽 배열에서 x를 찾음def bs(data, item, low, high): # item 존재 X i..

경희대학교 허선영 교수님의 컴파일러 수업을 기반으로 정리한 글입니다. 0. IntroductionUnderstanding the meaning of a sentence -> 문장의 의미를 유추Check ambiguity & typeex) Jack and Jack left her homework at home잭은 몇 명?jack과 her의 미스매치 1. Semantic Analysiseach expression이 correct type을 가지는지x + y -> x는 int, y는 string이면 errortranslate Abstract Syntax Tree -> Intermediate Representation(IR) TreesSemantic analyzer also can checkAll identif..

경희대학교 한치근 교수님의 알고리즘 수업을 기반으로 정리한 글입니다. 1. 알고리즘문제를 해결할 수 있는 잘 정의된(well defined) 유한(finite) 시간 내에 종료되는 계산적인(computational) 절차(prodcedure)input -> output: 일련의 계산 절차- 알고리즘과 Method의 차이Algorithm: 유한 시간 내에 종료Method: 유한 시간 내에 종료하는지 모름 문제의 표기 방법문제: 답을 찾고자 던지는 질문Parameter: 문제에서 특정 값이 주어지지 않은 변수 - 매개변수Instance(입력): 파라미터에 특정 값을 지정한 것Solution(출력): 주어진 사례에 관한 질문에 대한 답 수학적 귀납법(mathematical induction)귀납 출발점(bas..

경희대학교 허선영 교수님의 컴파일러 수업을 기반으로 정리한 글입니다. 1. Shift-Reduce Parsing - LR(k) Parsingpredictive parser: 어떤 production이 사용될지 예측오른쪽 항 전체에 해당하는 입력 토큰을 볼 때까지 결정을 미룲LR(k)Left-to-right parseRightmost derivationk-token lookaheadpredictive parsing(LL aprsing)보다 더 많은 grammars에 대해서 parsing 가능- 동작 방식parser는 stack & input을 가짐stack contents & next input token에 의해서, 2가지 동작 중 하나가 결정됨Shift: top of stack에 next input을 p..

경희대학교 허선영 교수님의 컴파일러 수업을 기반으로 정리한 글입니다. 1. Front-end Compilation- Lexical Analysis문장을 토큰 단위로 분류하는 과정정규 표현식을 사용하여 문장을 의미 단위로 구분- Syntax AnalysisLexical Analysis 과정에서 생성된 토큰을 기반으로 parse tree를 생성- Semantic Analysis프로그램의 선언과 진술이 의미론적으로 정확한지 확인하는 작업syntax analysis와 달리 type checking 진행 2. Syntax AnalysisAbstract Syntax Tree(AST)를 빌드 -> token stream이 valid한지 체크if the token stream is not valid -> syntax ..

경희대학교 허선영 교수님의 컴파일러 수업을 기반으로 정리한 글입니다. Goals of this AssignmentBuild a lexical analyzer for a new language, using a lexer generator for OCaml(ocamllex)know how to write a regular expression to represent a given set of stringsUnderstand how to write and debug ocamllex specification ocamllexocamllex: lexer generator for OCamlocamllex specification consists of three parts as shown in the example in..