Computer Science/Compiler Design
[Compiler Design] Analysis and Optimization
[Compiler Design] Analysis and Optimization
2025.12.04Machine Dependent Processing에서는 가상의 코드를 실제 하드웨어에 맞춰서 매핑하는 작업을 수행함.Instruction Selection - Instruction Scheduling - Register Allocation Machine Independent Optimization에서는 특정 하드웨어와 상관없이 논리적으로 코드를 개선하는 작업을 수행함.Control Flow Analysis를 통해 프로그램의 분기 구조를 파악하고 최적화한다. 최적화의 목표는 실행 시간 단축 + 메모리 사용량 최소화.코드를 분석하고, 분석 결과를 통해 최적화를 수행해보자. Control Flow는 프로그램의 실행 순서를 의미함.그냥 위에서부터 순차적으로 쭉~ 실행되면 분석할거도 없는데, 분기문으..
[Compiler Design] Machine Dependent Processing
[Compiler Design] Machine Dependent Processing
2025.11.30이전까지는 IR을 어떻게 만드는지에 대해 다뤘으니, 이제 IR을 타겟 머신의 어셈블리 명령어로 매핑하고 명령어 순서를 재배치하는 작업에 대해 살펴보자. 즉, 컴파일러의 백엔드 부분에서는..Instruction Selection / Instruction Scheduling / Register Allocation을 수행함. Instruction Selection을 수행학시 위해 IR을 트리 구조로 표현한다. 좌측 트리는 e + c가 메모리에 있는 값을 나타내는 구조.MEM / BINOP / PLUS / CONST 등의 노드로 트리를 표현한다. MEM(e) - 주소 e에 있는 메모리의 값을 의미한다.SEQ(s1, s2) - s1을 수행한 후 s2를 수행한다.ESEQ(s, e) - s를 수행한 후 e의 ..
[Compiler Design] Semantic Analysis
[Compiler Design] Semantic Analysis
2025.11.25컴파일러의 궁극적인 목표는 기계어나 IR을 만드는 것.어쩌다 보니 IR에 대해 먼저 다뤘는데.. 최종 결과물이 어떻게 구성되는지 알면 Semantic Analysis를 왜 해야 하는지 알 수 있다. IR의 입장에서 x + y 를 번역할 때, 이게 정수 덧셈인지 실수 덧셈인지 알아야 코드를 작성할 수 있음.그러니 IR 전에 Semantic Analysis를 통해 타입을 설정해 줘야 한다. Semantic Analysis는 Syntax는 통과했지만, 실행하면 터질 수 있는 논리적 오류를 IR을 만들기 전에 미리 잡아내는 단계. Lexical Analysis와 Syntax Analysis로 코드를 토큰으로 쪼개고, 문법 구조를 파악해 AST를 생성했다.이제 만들어진 AST를 사용해 Symbol Ta..
[Compiler Design] Run-Time Storage Management
[Compiler Design] Run-Time Storage Management
2025.11.24IR 생성의 예시로 WebAssembly가 있다. C/C++/Rust 언어를 컴파일해서 .wasm 바이너리를 생성하고, 브라우저의 자바스크립트 엔진과 연동해서 실행한다.내부적으로는 스택 머신 기반의 IR을 사용함. 브라우저에서 고사양 작업을 수행할 수 있음. 운영체제에서 메모리 영역 다룰때랑 똑같다. Code/Data 영역은 하위 주소에 위치Stack은 높은 주소에서 낮은 주소로 자라남Heap은 낮은 주소에서 높은 주소로 자라남. WASM 에서도 메모리 경계를 넘어서 데이터를 쓸 수 있다. - StackOverFlow 사람이 읽기 쉬운 High Level IR을 기계가 읽기 쉬운 Low Level IR로 변환해보자.일단 단계별로 쪼개는 Divide-and-Conquer 적인 마인드가 중..
[Compiler Design] Intermediate Representation
[Compiler Design] Intermediate Representation
2025.11.24중간언어(IR)는 컴파일러 내부적으로 사용하는 경우가 많고, 대부분 트리 형태나 Intruction List(기계어 코드) 형태를 가진다. 자바 코드는 AST로 변환된 후, 중간 언어를 거친 다음에 Low Level 코드로 변환된다.중간 언어는 여러 종류가 있을 수 있다 - High Level, Low Level AST와 가까이 있다면 소스코드 정보를 최대한 활용해서 최적화에 사용하고, Low Level과 가까이 있다면 실제로 Low Level 언어로 변환하는 작업을 수행한다. High Level과 Low Level은 상대적인 개념이다. 당연히 3개 이상의 중간언어도 나올 수 있음. High Level IR은 AST의 변형이라고 생각하면 됨. 변수, 표현식, 문장, 함수 등 모든게 유지되니 변수 사..
[Compiler Design] SDD / AST
[Compiler Design] SDD / AST
2025.11.17Lexical Analysis와 Syntax Analysis가 끝나면 이제 Semantic Analysis를 수행해야 한다.어휘 분석 -> 구문 분석 -> 의미 분석 Syntax-Directed Definition일단 파싱은 제대로 된다고 가정하고, Production 규칙마다 해야 할 일을 적어놓는다. (Semantic Action)파서 생성기인 yacc 에서 정말 많이 사용된다. Semantic Action을 수행할 때는 메모리가 필요하다. E -> E + E 라는 규칙에서, 각 E를 구분해서 사용해야 함. E + E 의 결과가 되는 메모리가 있다 ($$) Yacc/Bison$1과 $3 값이 잘 계산되어있다고 할 때, 이 값을 가지고 $$를 채워넣는다. ANTLR$expr = $unary_exp..
[Compiler Design] LR(0) / SLR / LR(1) / LALR
[Compiler Design] LR(0) / SLR / LR(1) / LALR
2025.11.03LR(0) 파싱이란, lookahead 단 하나도 없이 파싱하는 Shift-Reduce 형태를 의미한다.파싱 테이블을 만들기 위해, LR(0) 아이템과 Closure를 활용해 파서 상태들 간의 상태 전이도를 만든다. LR(0) 아이템rhs 에 "." 심벌을 가진 생성 규칙을 의미한다.A -> XYZ 규칙이 있다면 [A -> .XYZ] [A -> X.YZ] [A -> XY.Z] [A -> XYZ.] 는 LR(0) 아이템이다.A -> null 이면 [A -> .] 가 LR(0) 아이템으로 추가된다. ClosureLR(0) 아이템들을 모아놓은 집합에서 집합 크기를 크게 불리는 개념이다. $$ \text{closure}(I) = I \cup \{[B \to \cdot g] \mid [A \to a \cdot..
[Compiler Design] Bottom-Up Parsing
[Compiler Design] Bottom-Up Parsing
2025.10.18Top-Down 방식은 내가 유도하는 방식 그대로 트리가 완성된다.Bottom-Up 방식은 들어오는 토큰마다 하나씩 처리하는 식이니 컴퓨터 입장에서는 좀 더 쉽게 처리할 수 있다. 생성규칙의 선택을 token이 더 많이 들어올 때 까지 미룰 수 있어 Top-Down 방식보다 더 강력하고, Left-Recursive 문법도 함께 파싱할 수 있다. $$\begin{aligned}& (1+2+(3+4))+5 \;\Leftarrow\; (T+2+(3+4))+5\\& \Leftarrow\; (E+2+(3+4))+5 \;\Leftarrow\; (E+T+(3+4))+5\\& \Leftarrow\; (E+(3+4))+5 \;\Leftarrow\; (E+(T+4))+5 \;\Leftarrow\; (E+(E+4))+5..
[Compiler Design] LL Parsing
[Compiler Design] LL Parsing
2025.09.30LL 파싱은 Top-Down 파싱을 구현하는 방법으로 입력 문자열을 왼쪽에서 오른쪽으로 차례차례 읽고, 문법 전개 시 좌측유도를 따르는 파싱 방법이다. 단순히 Top-Down 파싱만 사용한다면 어떤 규칙을 적용할지, 이 규칙을 적용했을 때 입력과 맞을지를 사람이 직접 고민해야 했는데,LL 파서는 FIRST / FOLLOW 집합을 계산하고 Parsing Table을 만들어 LOOKAHEAD를 하나만 보면 규칙이 자동으로 정해지도록 한다. 일반적인 Top-Down 파싱에서는 시작 심벌의 첫 번째 생성규칙에서 유도를 시작해 문자열을 생성한다. 유도 과정에서 생성된 문자열과 입력 문자열을 차례로 비교하고, 유도된 문자열과 입력된 문자열이 같으면 계속 비교를 이어가고,다르다면 직전 생성 규칙을 잘못 적용했다고..
[Compiler Design] Syntax Derivation
[Compiler Design] Syntax Derivation
2025.09.20Lexical Analysis의 결과로 lexeme을 얻고, 이걸 가져다가 문장을 이해하는게 구문분석기의 역할이다.문법이 제대로 작성했는지 확인하고, 각 단어의 역할을 확인하기 위해 트리를 구성한다. Lexical Analysis에서는 정규표현식으로 패턴을 기술했고, 그 패턴에 맞는 Lexeme을 찾아 Token을 만들었다.Syntax Analysis에서는 Lexical Analysis에서 넘겨준 토큰의 순서가 문법에 맞는지 검사하는데.. 우선 그걸 위해 문법을 기술해야 한다. Context Free Grammar를 사용한다.정규표현식은 상태 수가 유한할 때만 사용할 수 있는데, 상태가 몇 개인지 알 수 없다. 이건 무한하게 깊어지는 중첩 구조를 처리할 수 없는 유한상태머신의 한계이기도 하다. ex) 괄..
[Compiler Design] Lexical Analysis
[Compiler Design] Lexical Analysis
2025.09.11컴파일러는 어떤 언어로 쓰여진 프로그램을 읽어 다른 언어로 된 의미가 같은 프로그램으로 번역해주는 프로그램이다. 자바에서 애너테이션도 컴파일러가 처리하기도 하고, 애너테이션 프로세서를 통해 추가 작업을 수행하기도 한다.애너테이션을 만들 때 Retention을 설정하는데, 이 설정값에 따라서 컴파일러 및 애너테이션 프로세서가 어느 정도까지 애너테이션을 처리할 지 결정한다. 다만 자바에서는 Preprocessor를 사용하지 않는다.#include처럼 Preprocessor가 처리하고 소스코드로 변환하는 과정이 없으니, 컴파일러와 전처리기를 구분해서 생각하자. 컴파일러는 프로그램 실행 전 소스코드를 중간코드로 변환하고, 인터프리터는 실행 중 한줄씩 해석한다.실제로는 두 가지 해석 방식을 혼합해서 사용하는 ..