번역기 4) 종류
프리프로세서 지시문 src (고급언어)-> 프리프로세서 -> 지시문이 처리된 src(고급언어) -> 컴파일러 -> target program
1) 매크로 처리기능
2) 조건부 컴파일 기능
3) 헤더 파일이 포함된 파일 포함 기능
src -> 컴파일러 -> 어셈블리어/기계어프로그램= object program = assembly 언어 = machine 언어 -> Loader -> executable program (.exe)-> Computer
1) 어떤 특정한 컴퓨터에서 직접 실행가능한 형태의 프로그램으로 번역해주는 컴퓨터 프로그램
2) frontend = 언어 의존적임 backend = 기계 의존적임
3) cross compiler : 소스프로그램을 다른 기종에대한 기계어로 번역하는 컴파일러
4) bytecode compiler : java src -> compiler -> bytecode program(중간 코드) -> interpreter
(jvm에서)-> output
어셈블리어(LOAD R1,a)로 작성된 프로그램 -> 어셈블러 -> 기계어 프로그램(.o)
참고) p12 링커-> 하나의 재배치 가능 기계 코드(.o)
src -> 인터프리터 -> 실행결과
1) 번역과 동시에 실행함
2) 대화용 언어 구현
3) 한줄단위로 번역/실행하므로 반복문에서 실행시간이 많이 늘어남
4) 한줄단위로 번역/실행해서 매번 같은 메모리를 사용하므로 메모리를 줄임
sp -> 어휘분석 -tokens-> 구문분석 -tree->의미분석-tree-> 중간코드생성 -i.c -> 코드최적화 -o.c-> 목적코드생성
lexical analyzer (scanner)
sp를 토큰들로 분리
syntax analyzer (parser) 구문분석기
correct) program structure 출력
incorrect) error message 출력
semantic analyzer
구문 분석 결과(트리)를 이용하여 소스프로그램이 언어 정의에 의미적으로 일치하는지 검사
중간코드생성에 이용하기위한 자료형 정보를 수집하여 저장
intermediate code generator
code optimizer
효율적인 코드로 바꾸어준다
메모리나 실행시간을 절약하기위한 단계
중간코드 -> precode optimzer -> optimized intermediate code
기계코드 -> postcode optimzer -> optimized machine code
target code generator
중간 코드로부터 machine instruction 을 생성한다
1) 목적코드 선택과 생성
2) 레지스터 운영
3) 기억장소 할당
4) 코드 최적화 기계의존적 최적화
error recovery
error handling 1) detection 2) recovery 3) reporting
1) syntax error 2) semantic error 3) run time error 4) logic error
컴파일러 자동화 도구
1) lexical analyzer generator (lex)
입력 스트림에서 정규표현으로 기술된 토큰들을 찾아내는 프로그램을 작성하는데 유용한 도구
2) parser generator -
stanford pgs :파스칼언어 by 존 , 구문구조를 AST형태로 얻음, AST 정보를 포함한 파싱 테이블을 출력
wisconsin pgs : 파스칼언어 by fisher , error recovery
yacc : unix , c언어
형식언어란?
alphabet : 공집합이 아님 T1 = {A,B,...,Z}
String : T = {0}, string = 0,00,000,...
Length : 문자열이루는 기호개수 |w|
|uv| = |u| + |v| 4 = 2+2
a^n = a가 n개 접속된 문자열
W^R 문자열의 역
empty string: 입실론(1로 생각하기) , 람다 , a^0 는 1이아니라 입실론 즉 empty string임!
언어는 문자열의 집합, 구문구조만 고려함, 의미개념은 포함x
L^0 = {입실론}
terminal : 정의된 언어의 알파벳, 대문자
non terminal : 중간과정의 기호 , 소문자
G = (Vn, Vt, P, S) 생성규칙, sentence symbol
문법의 분류
type 0 : unrestricted grammer/ recursively enumerable set / turing machine
type 1 : context sensitive grammer / context sensitive language / linear bounded automata
type 2 : context free grammer / context free language / push down automata
type 3 : regular grammer / regular language / finite automata
Symbol table : identifier에 관한 정보를 관리하고 운영하는데 사용되는 자료구조
어휘 + 구문 : identifier에 관한 정보를 수집하여 저장
의미 : symbol table에 수집된 속성과 참조된 명칭의 사용이 타당한지 검사
코드 생성 : 속성을 이용하여 올바른 코드를 생성하도록 함
int a; insert
a = 5; search
symbol table 의 효율적인 구성이 중요하며 compilation time 에 영향을 미침
unordered symbol table : symbol 정의된 순서대로 insert / linear search (n+1)/2
ordered symbol table: 알파벳순서대로 insert search / binary search logn
hash symbol table : hash bucket + symbol table
hash function : 심볼에 대한 주소를 계산하기위한 함수 : 제산법, 제곱값 중간법, 폴딩법
collision : 서로 다른 심볼이 같은 해시값을 갖게 되는 현상 : 전방법 후방법
정규표현 : re rg fa - type 3
rlg (right linear grammer) : A -> tB
llg
rlg 와 llg 의 규칙이 혼합되어있으면 정규문법이 아님
A -> aB , A -> a
S -> 입실론 ( P , S는 rhs에 appear 하지않는다
컴파일러 전반부를 모듈러하게 나누어 구성할 수 있따
효율적인 인식기를 구현할 수 있다
+ < concatenation < * closure