(5) 프로그램의 번역

프로그램의 구성
- 프로그램은 문장(Statement)으로 구성
- 프로그램의 문장은 자연어의 문장(sentence)과 유사함
- 문장은 프로그램의 실행 단위임
 
문장은 표현식(Expression), 선언, 제어, 함수 호출 등으로 구성
- 표현식은 문법(Syntax)에 의해 값으로 계산됨
ex) result = 1 + 2; -> result, =, 1, +, 2 는 Lexeme 
*위 문장은 두 개의 표현식으로 구성: (1) 1+2, (2) result = 3
 
표현식은 변수, 연선자 등으로 구성
-프로그램의 최소 단위(Lexeme)인 어휘로 자연어의 단어와 유사
 
문법 (Grammar)
- 어휘 (Lexeme): 프로그램을 구성하는 가장 최소 단위로 문자를 조합하여 단어로 구성
- 구문 (Syntax): 문장, 표현식 등 프로그래밍 언어의 요소들에 대한 조합 규칙
    * 문법을 이용해 기술할 수 있음[Context-free Grammar, BNF(Backus-Naur-Form)]
- 의미 (Semantics): 문장, 표현식 등에 대한 의미(meaning)
   * 컴퓨터가 이해할 수 있도록 알고리즘이나 수학적으로 표현해야 함
 
ex)

 
프로그램의 번역 과정
문장에서 기계어까지 3~4개의 분석기를 통해 번역됨
1. 어휘분석 (Lexical Analysis)
- 입력 받은 문자열(소스코드)를 단어(토큰)로 구분
- 각 토큰에 대한 유효성 검사를 수행 후 분류됨
 
2. 구문분석 (Syntatic Analysis)
- 토큰들의 조합의 유효성 검사 후 구조화된 형태로 구성
- 파스 트리(Parse Tree)로 출력됨
 
3. 의미분석 (Semantc Analysis)
- 프로그램의 실행을 위한 의미 적용 및 오류 검사
- 자료형 검사 수행
- 상세한 정보가 추가된 파스 트리가 생성됨
 
4. 최적화를 위한 작업 수행하며 중간 코드 생성
 
5. 타겟 시스템에 맞는 기계어 생성 
 
문자열 -> 어휘 분석 -> 토큰 -> 구문 분석 -> 파스 트리 -> 의미 분석 -> 파스 트리(주석 추가) -> 중간 언어 생성 -> 중간 언어 -> 최적화 -> (최적화된) 중간 언어 -> 코드 생성 -> 기계어
 
어휘 분석 과정
- 어휘 분석기는 Lexer 또는 Scanner 라고 불림
- 연속된 문자로 이루어진 소스코드에서 프로그램의 최소 구성 단위를 추출하며, 해당 요소의 유효성 검사
* 프로그램의 가장 최소 단위를 어휘(Lexeme)라고 하며, 토큰(Token)으로도 부름
 
if(i==j)
    z = 0;
else          ->  \tif(i==j)\n\t\tz=0;\n\telse\n\t\tz=1; (연속된 문자열)
    z =1;
 
위 과정을 상태기계(State Machine)이나 정규식(Regular Expression)을 사용하여 토큰을 추출
 
<어휘 분석 결과: 연속된 문자열에서 나온 토큰>
(Whitespace, "\t")
(Keyword, "if")
(OpenPar, "(")
(Identifier, "i")
(Relation, "==")
etc
 
ex) 실수를 인식하기 위한 어휘 분석기
다음과 같이 다양한 경우 고려
- 0으로 시작되는 경우: 00000032, 0000.73
- 의미 없는 0이 소수점 자리에 오는 경우: 3.43400000
- 양수 기호가 있는 경우: +32.394
- 소수점에서 0을 생략하는 경우: .43
 
-> 실수(floating point)를 인식하기 위한 상태 기계(state machine)

 
 
구문 분석
- 구문 분석기는 파서(Parser)라고도 불림
- 구문 분석기는 어휘 분석기의 결과인 토큰 그룹을 입력으로 받음
- 토큰들을 조합하여 문장으로 구성하고, 구성된 문장은 파스 트리(Parse Tree)의 형태로 출력됨
 

 
문법 규칙의 기술
- 프로그래밍 언어의 문법을 기술하기 위한 문법이 필요함
- 자연어에서의 문법과 유사하지만 문맥(의미)를 표현할 수 없음
 
1. 문맥-자유 문법 (Context-Free Grammar)
   - 1950년대 중반 노암 촘스키의 언어 분류 방법에 따라 정의됨
   - 오늘날의 프로그래밍 언어에 많이 사용됨
 
2. BNF (Backus-Naur Form, 1959)
   - John Backus 와 Peter Naur가 설계한 표기법
   - Context-free grammars를 표현할 수 있음
 
코드 생성기에 의한 기계어 출력
- 특정 대상 기계에 대한 기계어 코드 생성
- C언어의 경우 대상 기계의 어셈블리(Assembly)언어 코드를 만들고 어셈블러(Assembler)를 사용하여 기계어로 번역하여 실행

최적화
- 비효율적인 코드를 컴파일러가 개선하는 작업
1. 사용하지 않는 변수 
2. 불필요한 조건
3. 반복되는 변수 생성
4. 프로그램 실행에 영향을 주지 않는 코드