code the world

register와 memoryCPU에서 어떤 값들을 저장하는 용도로 register와 memory가 있다.컴퓨터 구조론에서도 나오는 내용이지만 간단히 정리해보자. 먼저 CPU에서 연산을 할 때는 register의 내용을 사용한다.따라서 memory에 있는 내용은 먼저 register로 올린 후에 연산이 가능하다. memory 보다 register가 훨씬 빠른데, 대신 그만큼 용량은 적다.register allocation이전 글에서 IR에 대해 잠시 얘기했었다. 이때 기본적으로 깔려있는 가정이 있는데,"IR은 무한한 register를 가지고 있다" 그러나 실제로는 당연히 register의 개수에 8~16개 정도로 제한이 있는데, 이 글에서는 이것과 관련해 알아보자. 우리가 이론적으로 다뤘던 registe..

저번 글에서 dataflow analysis 를 알아봤었다.이번에는 프로그램의 분기 구조를 분석하는 control flow analysis를 알아보자. Dominator이전 글에서 CFG는 BB를 노드로 가지는 그래프라고 했었다.Entry 부터 어떤 노드 y까지 갈 수 있는 모든 길에 x노드가 있다면 x가 y를 dominate한다고 말한다.이 dominator에는 3가지 속성이 있다.1. 모든 BB는 자기자신을 dominate한다.2. x가 y를 dominate하고 y가 z를 dominate하면 x가 z도 dominate한다.3. x와 y가 둘다 z를 dominate하면, x와 y사이 dominate관계가 있다. Dominator TreeBB간의 dominate관계를 그래프로 나타낸 것이다. Domina..

컴파일러의 frontend에서는사람이 작성한 source code를 lexical, systax, semantic ayalys is를 통해 문법적으로 문제없는 코드라는 것을 보장했고,AST를 만들었다.front end와 back end를 연결하는 과정으로 이전글에서 봤던 code generation 과정이 있다.여기서 AST를 IR로 바꿔서 back end로 넘긴다.이번 글에서부턴 back end의 동작을 알아보자.이 back end에서는 최적화를 하는데 프로그램의 자원 효율성을 높이는 것이다.이 자원의 기준은 사람/프로그램 마다 다르다.어떤 프로그램은 공간을 많이 쓰더라도 시간을 줄이는게 효율성을 높이는 것일 수도 있고 그 반대일 수도 있다.그러나 어떤 방식으로 최적화를 하던지 프로그램의 결과는 바뀌면..

아래처럼 간단한 코드는 어셈블리 코드로 바꾸기 쉬울 것이다.하지만 함수 호출등 코드가 복잡해지면 어려워진다.Stack Machine위의 어려움을 조금 해소해주기 위해 만들어진 방법이 stack machine이다.일단 모든 데이터가 스택에 저장되어있다고 가정하고 진행해보자.이 가정이 없는 경우에 대해서는 바로 이어서 다룰 것이다. stack machine은 n개의 피연산자를 스택에서 pop하고 이 값들을 이용해 operation(명령어)를 계산한다.그 이후 그 결과를 다시 스택에 push한다. 간단한 설명이지만 약간 추상적이므로 예시를 보고 확실히 이해를 해보자.아래 예시는 7+5를 계산하는 예시이다.2번의 load(pop), 1번의 store(push)로 계산할 수 있다.그러나 덧셈 한번에 3번의 메모리..

이전 글에서도 몇 번 봤던 그림을 다시 보고 시작해보자.이전 글까지 총 7개의 글에 걸쳐 lexical → Syntax → Semantic 분석을 알아봤었다.이제는 Code Generation과정에 대해 알아보자. 컴파일러의 역할컴파일러는 단순히 사람이 작성한 코드를 아무생각없이 기계어로 바꿔주는 것이 아니다.데이터가 저장공간에 어떻게 저장되고 사용될지를 관리하기도 한다.또 더 효율적인 코드가 되도록 코드를 바꿀 수도 있다.데이터 저장 위치 결정소프트웨어적인 관점에서 CPU는 연산장치, 레지스터, 메모리로 나눠서 이해해볼 수 있다.여기서 우리는 데이터를 레지스터에 저장할지, 메모리에 저장할지 결정해야한다.일반적으로 전역 변수나 static변수는 메모리에 저장한다.로컬 변수들 중에서도 배열, 구조체 같은 ..

lexical analysis와 syntax analysis를 통과했다고 그 코드가 멀쩡한 것은 아니다. 예를 들면,a=3; 이런 코드는 문법상 문제가 없지만 이전에 a가 선언되지 않았다면 에러가 발생해야한다.또는 함수이름은 func(0);처럼 사용해야하지만 func=0;이라고 사용하는 에러도 있을 수 있다.문법상 func도 변수의 이름이 될 수 있기 때문에 이전 단계에서는 탐지할 수 없기 때문이다. 어쩃든 이제 이런 의미적인 부분을 따지는 Semantic Analysis를 알아보자. Semantic AnalysisSemantic Analysis에는 크게 두 종류가 있다. 1. 범위(scope)와 관련된 분석2. 타입(type)과 관련된 분석Scope코딩을 하면서 기본적으로 알고 있던 scope의 개념과..

LR grammar는 left-recursive, right-most derivation의 약자이다.이 문법을 사용해 만들어진 파서는 shift-reduce parser라고 부른다. Shift & Reducebottom-up parser는 derivation의 우변에 있는 내용을 좌변으로 되돌린다. 이 과정을 reduce라고 한다.즉 시작을 최종 식에서부터 하여 역으로 시작 심볼로 변환하는 방법이다. right-most derivation은 변환해야될 식에서 오른쪽부터 살펴보며 reduce를 한다는 뜻이다.int*int+int라는 에시에 대해 단계별로 parser가 동작하는 과정을 나타낸 것이다.shift는 당장 reduce가 될 수 없을 때 stack에 임시 저장해놓는 행동이다.Action Select..

이전글에 이어서 Parser를 계속 알아보자. 2025.11.23 - [컴파일러] - [컴파일러 이론] 3. Syntax analysis, Parser, CFG, Parse Tree, AST [컴파일러 이론] 3. Syntax analysis, Parser, CFG, Parse Tree, ASTSyntax analysis, Parser이번글은 syntax analysis에 대해 알아보자.코딩을 할때 개발자들을 괴롭히는 syntax error 라는 에러메세지는 많이 보았을 것이다. 이번글은 이와 관련된 것이다.이전글들에서 얘기한april2901.tistory.com이번 글의 목적은 CFG로부터 Parse Tree를 만드는 것이다. Top Down Parsing먼저 top down parsing이 뭔지 알..

Syntax analysis, Parser이번글은 syntax analysis에 대해 알아보자.코딩을 할때 개발자들을 괴롭히는 syntax error 라는 에러메세지는 많이 보았을 것이다. 이번글은 이와 관련된 것이다.이전글들에서 얘기한 lexical analysis를 수행하는 scanner는 코드를 토큰들로 나눠주는 역할을 했다.이번 syntax analysis는 이 토큰들을 활용해 문법에 맞는지를 판단한다. 이 분석을 하는 친구를 Parser라고 한다.이 Parser가 하는 일을 몇가지 예를 들어보면,1. 괄호를 열면 닫는 부분이 있는지2. C언어 같은 경우 뒤에 ;을 잘 썼는지3. while 뒤에 ( )가 있어 그 안에 반복에 대한 조건문이 있는지등등 많은 문법을 검증한다.Scanner는 각 토큰을..

2025.11.20 - [컴파일러] - [컴파일러] 1. lexical analysis, scanner, regular expression [컴파일러] 1. lexical analysis, scanner, regular expression보통 우리가 코딩을 하면 어셈블리어로 컴파일되어 기계가 알아들을 수 있게 변환된 다음 코드가 실행된다. 이 과정에서 분명 사람은 거의 영어에 가까운 언어로 코딩을 하는데, 기계가 이걸 어april2901.tistory.com 이전 글에서 RE를 사용해 각 token의 pattern을 만드는 것까지 알아봤었다.이번에는 이 pattern들을 인식하는 법을 알아보자.Finite State Automata(FSA)먼저 Finite State Automata(FSA)라는 개념에..