Chapter 02 간단한컴파일러의구조
01 컴파일러의논리적구조 02 컴파일러의물리적구조
컴파일러의논리적구조를이해할수있다. 간단한컴파일러의예를통하여컴파일러의전체구조를이해할수있다. 컴파일러의물리적구조를이해할수있다.
영어를한글로번역 4
문장이어떤요소로구성되어있는지파악하기위해문장에사용된단어를검사. 그래서이문장에는 I, am, a, boy 라는네가지단어가사용된것을알아내는데이를어휘분석이라한다. 다음으로 I, am, a, boy 가각각 8 품사인명사, 대명사, 동사, 형용사, 부사, 전치사, 접속사, 감탄사중어디에속하는지확인하고, 문장의 5 대요소인주어, 동사, 목적어, 보어, 수식어등으로구분할것이다. 그리고주어 + 동사, 주어 + 동사 + 보어, 주어 + 동사 + 목적어등문장의형식을검사하여이문장이주어 + 동사 + 보어로구성되었다는것을알아낸다. 이렇게문장의형식을알아내는것을구문분석이라한다. 그다음에는단어대단어의번역이아니라한글문법에맞게번역해야하는데이를의미분석이라한다. 그러고나서한글단어가운데더알맞은단어로번역하는코드최적화를거쳐마지막으로한글로번역하는것이다. 5
컴파일러도영어문장을한글로번역하는것과비슷한단계거쳐서번역 C 언어를기계어로번역 먼저주어진문장이어떤단어들을포함하고있는지확인한다. C 언어에서사용하는의미있는단어를 토큰 token 이라고한다. C 언어에서어떤토큰이사용되었는지구분하는것인데, 이를어휘분석. 두번째로는이러한단어가문장의구성요소가운데어디에맞는지확인해야한다. 즉문법을보면서토큰들이문법에맞는지검사하는데, 컴파일러에서는이를구문분석. 세번째로는한국어의의미를검사하는것, 즉의미분석을한다. 하지만형식언어는의미를가지고있지않기때문에이과정에서주로형 type 을검사한다. 의미분석으로생성된코드의실행시간을줄이거나기억장소를줄이기위한코드최적화 마지막으로목적기계 (target machine) 의특성을고려하여목적코드를생성. 6
컴파일러의구조에대한견해 : 분석 (Analysis)- 합성 (Synthesis) 모델 : 논리적인구성측면 전단부 (Front-end)- 후단부 (Back-end) : 기계독립 (machine independent) or 기계종속 (dependent), 구현측면 컴파일러의구체적구조 7
8
아주간단한 C 문법 9
생성규칙 ❶의 <Sub C> 는 <assign-st> 로치환된다는것을의미한다. 생성규칙 ❷의 <assign-st> 는 <lhs> 가먼저오고 = 가그다음으로오며 <exp> 가온뒤마지막으로 ; 이오는문법이다. [ 그림 2-4] 는 C 언어의치환문을표현하고있으며, 산술식에는산술연산자 +, -, *, / 등사칙연산을허용하는데우선순위는 * 와 / 가높고그다음이 +, -이며, 모든연산자가왼쪽결합법칙을취함을알수있다. 또한산술식에괄호를사용할수있으며, 식별자는첫글자가영문자나언더바로시작하고두번째글자부터는영문자, 숫자, 언더바가올수있으며길이의제한이없다. 그리고숫자는 0과양의정수를사용할수있으며, 영문자는소문자 a부터 z까지사용가능하다. 10
[ 예제 2-1] 치환문 ni = (po - 60); 이주어진문법에맞는문장인지확인해보자. 이를확인하는방법은크게두가지가있는데여기서는좌단유도 (leftmost derivation) 하는방법으로확인해본다. 유도는생성규칙의왼쪽을오른쪽으로대체하는것이며, 좌단유도는가장왼쪽기호부터유도하는것을말한다 [ 풀이 ] <Sub C> <assign-st> ( 생성규칙 ❶ 적용 ) <lhs> = <exp>; ( 생성규칙 ❷ 적용 ) <variable> = <exp>; ( 생성규칙 ❸ 적용 ) <ident> = <exp>; ( 생성규칙 ❼ 적용 ) (<letter> _){<letter> <digit> _} = <exp>; ( 생성규칙 ❽ 적용 ) n{<letter> <digit> _} = <exp>; ( 생성규칙 ❿ 적용 ) ni = <exp>; ( 생성규칙 ❿ 적용 ) ni = <term>; ( 생성규칙 ❹ 적용 ) 11
ni = <factor>; ( 생성규칙 ❺ 적용 ) ni = (<exp>); ( 생성규칙 ❻ 적용 ) ni = (<exp>-<term>); ( 생성규칙 ❹ 적용 ) ni = (<term>-<term>); ( 생성규칙 ❹ 적용 ) ni = (<factor>-<term>); ( 생성규칙 ❺ 적용 ) ni = (<variable>-<term>); ( 생성규칙 ❻ 적용 ) ni = (<ident>-<term>); ( 생성규칙 ❼ 적용 ) ni = ((<letter> _){<letter> <digit> _}-<term>); ( 생성규칙 ❽ 적용 ) ni = (p{<letter> <digit> _}-<term>); ( 생성규칙 ❿ 적용 ) ni = (po - <term>); ( 생성규칙 ❿ 적용 ) ni = (po - <factor>); ( 생성규칙 ❺ 적용 ) ni = (po - <number>); ( 생성규칙 ❻ 적용 ) ni = (po - {<digit>}); ( 생성규칙 ❾ 적용 ) ni = (po - 60); ( 생성규칙 11 적용 ) 치환문 ni = (po - 60); 이주어진문법에맞는문장이다. 12
[ 예제 2-2] 치환문 ni = ba * po - 60 + ni / (abc + 50); 이 [ 그림 2-4] 의문법에맞는문장인지알아보자. [ 풀이 ] <Sub C> <assign-st> ( 생성규칙 ❶ 적용 ) <lhs> = <exp>; ( 생성규칙 ❷ 적용 ) <variable> = <exp>; ( 생성규칙 ❸ 적용 ) <ident> = <exp>; ( 생성규칙 ❼ 적용 ) (<letter> _){<letter> <digit> _} = <exp>; ( 생성규칙 ❽ 적용 ) n{<letter> <digit> _} = <exp>; ( 생성규칙 ❿ 적용 ) ni = <exp>; ( 생성규칙 ❿ 적용 ) ni = <exp>+<term>; ( 생성규칙 ❹ 적용 ) ni = <exp>-<term>+<term>; ( 생성규칙 ❹ 적용 ) ni = <term>-<term>+<term>; ( 생성규칙 ❹ 적용 ) ni = <term>*<factor>-<term>+<term>; ( 생성규칙 ❹ 적용 ) ni = <factor>*<factor>-<term>+<term>; ( 생성규칙 ❺ 적용 ) ni = <variable>*<factor>-<term>+<term>; ( 생성규칙 ❻ 적용 ) ni = <ident>*<factor>-<term>+<term>; ( 생성규칙 ❼ 적용 ) ni = (<letter> _){<letter> <digit> _}*<factor>-<term>+<term>; ( 생성규칙 ❽ 적용 ) 13
ni = b{<letter> <digit> _}*<factor>-<term>+<term>; ( 생성규칙❿ 적용 ) ni = ba * <factor>-<term>+<term>; ( 생성규칙 ❿ 적용 ) ni = ba * <variable>-<term>+<term>; ( 생성규칙 ❻ 적용 ) ni = ba * <ident>-<term>+<term>; ( 생성규칙 ❼ 적용 ) ni = ba * (<letter> _){<letter> <digit> _}-<term>+<term>; ( 생성규칙❽ 적용 ) ni = ba * p{<letter> <digit> _}-<term>+<term>; ( 생성규칙❿ 적용 ) ni = ba * po - <term>+<term>; ( 생성규칙 ❿ 적용 ) ni = ba * po - <factor>+<term>; ( 생성규칙 ❺ 적용 ) ni = ba * po - <number>+<term>; ( 생성규칙 ❻ 적용 ) ni = ba * po - {<digit>}+<term>; ( 생성규칙 ❾ 적용 ) ni = ba * po - 60 + <term>; ( 생성규칙 11 적용 ) ni = ba * po - 60 + <term>/<factor>; ( 생성규칙 ❺ 적용 ) ni = ba * po - 60 + <factor>/<factor>; ( 생성규칙 ❺ 적용 ) ni = ba * po - 60 + <variable>/<factor>; ( 생성규칙 ❻ 적용 ) ni = ba * po - 60 + <ident>/<factor>; ( 생성규칙 ❼ 적용 ) ni = ba * po - 60 + (<letter> _){<letter> <digit> _}/<factor>; ( 생성규칙❽ 적용 ) ni = ba * po - 60 + n{<letter> <digit> _}/<factor>; ( 생성규칙❿ 적용 ) ni = ba * po - 60 + ni /<factor>; ( 생성규칙 ❿ 적용 ) ni = ba * po - 60 + ni /(<exp>+<term>); ( 생성규칙 ❹ 적용 ) 14
ni = ba * po - 60 + ni /(<term>+<term>); ( 생성규칙 ❹ 적용 ) ni = ba * po - 60 + ni /(<factor>+<term>); ( 생성규칙 ❺ 적용 ) ni = ba * po - 60 + ni /(<variable>+<term>); ( 생성규칙 ❻ 적용 ) ni = ba * po - 60 + ni /(<ident>+<term>); ( 생성규칙 ❼ 적용 ) ni = ba * po - 60 + ni /((<letter> _){<letter> <digit> _}+<term>); ( 생성규칙 ❽ 적용 ) ni = ba * po - 60 + ni /(a{<letter> <digit> _}+<term>); ( 생성규칙 ❿ 적용 ) ni = ba * po - 60 + ni /(abc+<term>); ( 생성규칙 ❿ 적용 ) ni = ba * po - 60 + ni /(abc+<factor>); ( 생성규칙 ❺ 적용 ) ni = ba * po - 60 + ni /(abc+<number>); ( 생성규칙 ❻ 적용 ) ni = ba * po - 60 + ni /(abc+{<digit>}); ( 생성규칙 ❾ 적용 ) ni = ba * po - 60 + ni /(abc+50); ( 생성규칙 11 적용 ) 이와같이좌단유도에의해치환문 ni = ba * po - 60 + ni / (abc + 50); 은 [ 그림 2-4] 의문법에맞는문장임을알수있다. 15
치환문 ni = ba * po - 60 + ni / (abc + 50); 에대한컴파일러도식화 16
17
어휘분석 (lexical analysis, scanning) 원시프로그램을읽어들여토큰 (token) 이라는의미있는문법적단위 (syntactic entity) 로분리 어휘분석을담당하는도구 (tool) 를어휘분석기 (lexical analyzer) 혹은스캐너 (scanner) 라고부른다. 토큰 : 문법적으로의미있는최소단위로문법에서터미널기호임 position = initial + rate * 60 토큰의종류 식별자 (identifier) ( position, initial, rate,... ) 예약어 (key word) ( IF, WHILE,... ) : reserved word 상수 (constant) ( 60, KIM... ) : numerical, literal 연산자 (operator) ( +, *, %,... ) 구분자 (delimiter) ( [, ], ;... ) 18
[ 그림 2.4] 의문법에서예약어가허용되는지를확인한다, [ 그림 2.4] 에서는예약어를사용하지않는다. 상수를보면, 0 이나양의정수를허용한다. 연산자는 4 칙연산자인 +, -, *, / 를사용하고치환연산자인 = 를허용한다. 식별자도허용하고첫자는영문자나언더바로시작하고두번째자부터는영문자나숫자, 언더바를사용하고길이에는제한이없다. 구분자로는세미콜론만이사용된다. 이들을정규문법과정규표현으로나타내면다음과같다. 1) 식별자 : 정규문법 S la _A A la da _A ε 로부터정규표현으로나타내기위해서정규표현방정식은다음과같다. S = (l + _)A A = la da _A ε = (l + d +_ )A + ε = (l + d +_ )* 이것으로부터해를구하면 S = (l + _)A = (l + _)(l + d +_ )* 2) 상수 : S= (d) + 3) 연산자 : S = + - * / = 4) 구분자 : ;, (, ) 19
이들을받아들이는유한오토마타는다음과같다. 20
토큰에대한표현은 ( 토큰번호, 토큰값 ) 의순서쌍으로표현 주석 (comment) 도이과정에서처리 21
구문분석 (syntax-analysis, parsing) 어휘분석단계로부터토큰들을받아이토큰들이주어진문법 (grammar) 에맞는지를검사하고올바른문장에대해서는그문장에대한파스트리 (parse tree) 를출력하고올바르지못한문장에대해서는에러메시지 (error message) 를출력하는과정을구문분석 (syntax analysis) 혹은파싱 (parsing) 구문분석을담당하는도구 (tool) 를구문분석기 (syntax analyzer) 혹은파서 (parser) 라고부른다. 파스트리 (parse tree) 는토큰들을터미널노드 (terminal node) 로하는트리 (tree) 22
ni = ba * po 60 + ni / (abc + 50); 에대한파스트리 23
[ 그림 2-4] 의문법에대한 SLR 파싱표가 [ 표 2-1] 과같을때이파싱표를가지고구문분석을할수있다. 파스트리에대한구문트리 24
[ 그림 2-4] 의문법에대한 SLR 파싱표가 [ 표 2-1] 과같을때이파싱표를가지고구문분석을할수있다. 25
26
27
28
29
[ 표 2-2] 의파싱에서주어진문장에대해수락되었으므로치환문 ni = ba * po - 60 + ni / (abc + 50); 은주어진문법에맞는문장임을알수있다. 30
의미분석 (semantic-analysis, parsing) 원시프로그램의의미적오류를검사하고계속되는코드생성단계를위한정보를모으는일 의미분석을담당하는도구 (tool) 를의미분석기 (semantic analyzer) 의미분석단계에서가장중요한기능중의하나는형검사 (type checking) 각연산자들이원시프로그램규칙에의해서허용된피연산자를가졌는가를검사 ( 일반적연산 (generic operation) 과형고정연산 (Type specific operation)) 정수와실수의일반적연산을허용하는데이때의의미분석기는연산을수행하기전에정수를실수로바꾸어주는작업.( 언어정의시간 ) 예를들어 a+b 와같은산술식을생각해보자. a 와 b 의자료형을각각 int 형과 float 형이라면형고정연산에서는에러. 반면에일반적연산에서는 a 나 b 의형을변환하여연산을허용. 형변환 (type conversion) 이란주어진자료형의값을다른자료형의값으로변환하는것을의미, 이에는시스템에서자동으로형을변환하는묵시적형변환 (implicit type conversion) 과프로그래머가명시적으로형변환을요구하는명시적형변환 (explicit type conversion). 명시적변환은프로그래머가명령문으로요구한형변환으로캐스트 (cast) 연산. 묵시적형변환은시스템에서자동으로형을변환하는것으로자동변환 (automatic type conversion) 또는강제변환 (coercion) 31
[ 예 2-3] 어떤언어가일반적연산을허용하고정수형인 int 와실수형인 float 가있는경우, 언어정의시간에정수형을실수형으로변환하여계산한다고가정하고, 치환문 ni = ba * po - 60 + ni / (abc + 50); 에서나타난식별자 ni, ba, po, ni, abc 는모두실수형이라고가정한다. 이때 [ 그림 2-8] 의구문트리를가지고의미분석을해보자. [ 풀이 ] 의미분석하면 [ 그림 2.9] 과같다. 여기서 inttofloat 는정수형을실수형으로변환하는함수. 32
중간코드생성 (intermediate code generation) 구문분석단계에서만들어진구문트리를이용하여코드를생성하거나한문법규칙이감축될때마다문법지시적번역 (syntax-directed translation) 으로이루어짐 중간코드생성을담당하는도구를중간코드생성기 (intermediate code generator) 중간코드를생성하기위해서는중간언어가필요 중간언어 역폴란드식표기 (Fortran 의산술식, Basic 의 interpreter), 폴란드식표기 (prefix) 중간언어중 3- 주소코드는각명령어마다 3 개의피연산자를가진 A = B op C 형태의명령어의나열이다. 33
치환문 ni = ba * po - 60 + ni / (abc + 50); 에대해 3- 주소코드 (three-address code) 를이용한다면다음과같은중간코드가생성된다. temp1 = id2 * id3 temp2 = inttofloat(60) temp3 = temp1 - temp2 temp4 = inttofloat(50) temp5 = id4 + temp4 temp6 = id1 / temp5 temp7 = temp3 + temp6 id1 = temp7 여기서각명령어의계산된값을담고있을임시기억장소인 temp1, temp2, temp3, temp4, temp5, temp6, temp7 과같은임시변수를생성해야한다. 8 장에서중간언어와중간코드생성에대해자세히설명할것이다. 34
코드최적화 (code optimization) 같은기능을유지하면서코드를좀더효율적으로만들어코드수행시기억공간이나수행시간을절약하기위한단계 선택적인단계로서생략되는경우도있지만요즈음에와서는 RISC (Reduced Instruction Set Computer) 와같은컴퓨터구조의특성을활용하기위해서최적화단계를많이사용하고있다 최적화방법은최적화가적용되는프로그램의영역에따라서지역최적화 (local optimization), 전역최적화 (global optimization), 프로시저간최적화 (inter-procedural optimization), 기능적인측면으로서는실행시간최적화와메모리최적화로분류, 최적화가많이이루어지는부분에따라서는루프 (loop 혹은반복문 ) 최적화와단일문최적화로구분. 또한, 목적기계의의존성에따라서기계독립최적화 (machine independent optimization) 와기계종속최적화 (machine dependent optimization) 등이있다. 35
지역최적화 부분적인관점에서일련의비효율적인코드들을구분해내고좀더효율적인코드로수정하는방법으로코드가분기해나가거나분기해들어오는부분이없는기본블록 (basic block) 내에서최적화를수행하므로상대적으로쉽게수행할수있다. 기본블록은어떠한제어흐름도가지지않기때문에분석이거의필요없다. 이방법에는공통부분식제거 (common subexpression elimination), 복사전파 (copy propagation), 죽은코드제거 (dead-code elimination), 상수폴딩, 대수학적간소화등이있다. 전역최적화 기본블록을넘어서지만하나의프로시저내에서일련의비효율적인코드들을구분해내고좀더효율적인코드로만드는방법이다. 이방법을적용하기위해서는지역최적화보다더많은정보와많은비용을요구해서수행하기는어렵지만, 지역최적화보다효과가훨씬좋다. 전역최적화는일반적으로자료흐름분석 (data flow analysis) 이라는기법을사용하는데, 자료흐름분석은프로그램안에서사용되는변수의경로 (path) 에관한정보를수집해서처리하는과정이다. 이방법에는전역적공통부분식제거, 상수폴딩, 도달될수없는코드의제거등이있다. 36
최적화를수행하기위해서는주어진중간코드를기본블록 (basic block) 과흐름그래프 (flow graph) 가필요하다. 치환문 ni = ba * po - 60 + ni / (abc + 50); 에대해 3-주소코드로생성된중간코드를가지고간략한코드최적화를하면 [ 그림 2-10] 과같다. 37
목적코드생성 (code generation) 연산을수행할레지스터를선택하거나자료에기억장소의위치를정해주며실제로목적기계에대한코드를생성하는단계 레지스터두개를사용하는경우의예 : LOAD LOAD MULT R2, id2 R1, id3 R2, R1 SUBT R2, #60.0 LOAD R1, id4 ADD R1, #50.0 STORE LOAD DIV ADD W1, R1 R1, id1 R1, W1 R2, R1 STORE id1, R2 38
2.2 컴파일러의물리적구조 어떻게구현할것인가? One pass : 실행속도가빠르고, 효율성이좋다. Two pass : 각모듈단위로작성, 이식성, 기계독립적인최적화가능 컴파일러를설계할때고려사항 : 컴파일러의논리적구조 컴퓨터자원 사용자의요구사항 개발하는인적자원 39