[시스템 프로그래밍] 5강 어셈블러 개요, 이중 패스 어셈블러, 이중 패스 어셈블러의 설계, 다중 패스 어셈블러, 테이블 처리

* 어셈블러 개요

어셈블러는 어셈블리어 명령에 의해 쓰여진 원시 프로그램을 입력받아 목적 프로그램을 생성해 주는 역할을 한다

기계어와 일대일 대응으로 번역하며, 작업과정이 컴파일러보다 간단

어셈블리 소스 프로그램은 입력으로 목적 코드 파일은 출력이 된다

 

어셀블러의 기능, cross assembler

어셈블러의 역할을 어셈블리 원시 프로그램 모듈을 입력받아 독립적으로 번역하여 목적 프로그램 모듈 생성한다

링커와 로더에 의해 필요한 형식에 맞추어 목적 모듈을 생성

 

2. 어셈블러의 입력과 출력

어셈블러는 어셈블리어로 쓰여진 원시 프로그램을 입력받아 목적 프로그램 생성

어셈블러의 입력은 어셈블리어로 쓰여진 원시 프로그램

원시프로그램은 보조기억장치에 저장

어셈블러의 출력은 목적 프로그램이 된다.

목적 프로그램 역시 보조 기억장치에 출력되어 저장되게 된다.

 

* 이중 패스 어셈블러

 

이중 패스의 필요성

어셈블리 프로그램에서 변수 및 상수, 그리고 프로시저에 대한 전향 참조를 허용해야 하기 때문에 이중 패스 처리가 필요하다.

 

2. 어셈블리 과정

어셈블 과정은 원시 프로그램이 패스 1에 의해 기호표를 작성하고 어셈블리 명령어에 상응하는 기계어 코드를 생성하고 기호를 주소값으로 변환

어셈블리 지시어는 지시어표에 나타난 지시대로 처리한다

 

3. 패스 1과 패스 2의 기능

우선 패스 1에서는 원시 프로그램을 각 명령어나 데이터들의 크기를 파악하여 상대주소를 정한다

각 기호표를 만들어 각 기호의 값을 기록하게 된다.

재배치해야 할 기호들을 결정하여 재배치 여부를 표시

패스 2에서는 명령어표에서 각 명령어의 2진 코드를 찾아 기계어 코드로 만들고 기호의 전향 참조가 있을 때에는 기호표에서 기호의 값을 찾아 기호 대신 기호의 값을 기입하는 기능을 한다

주소를 변경하는 것을 재배치라고 한다.

재배치 작업은 링커와 로더가 하기 때문에 어셈블러는 링커와 로더에게 어느 기호의 값을 재배치할 것인가를 알려준다.

 

* 이중 패스 어셈블러의 설계

 

패스 1의 알고리즘

 

패스 2의 알고리즘

 

자료구조

패스 1에 관련된 자료구조 (데이터 구조) : 패스 1에서 필요한 입력될 데이터 구조로는 원시 프로그램, 명령어표, 어셈블러 지시어표이며, 출력 데이터베이스로는 기호표이다.

패스 2에 관련된 데이터 구조 : 패스 2에서 데이터베이스로는 원시 프로그램 입력, 명령어표 입력, 어셈블러 지시어표 입력, 기호표입력이 있으며, 출력 데이터베이스로는 목적 프로그램이 있다.

 

* 단일 패스 어셈블러

단일 패스는 어셈블리 명령어 번역과 기호에 대한 정보수집을 동시에 수행하는 것을 의미

 

전향 참조

 

2. 알고리즘

어셈블할 때 전형 참조 문제를 해결하기 위해서 이중 패스 어셈블러를 이용

단일패스를 통해서 전향 참조 문제를 해결 가능

 

* 다중 패스 어셈블러

패스 하나로는 처리가 어려운 작업을 여러 개의 패스로 나누어서 이 각각의 패스가 공통의 데이터를 처리함으로ㅆ 전체적인 작업을 해내는 방식의 어셈블러

 

* 테이블 처리

 

심벌 테이블 (symbol table)

심벌 테이블이란 어셈블러나 컴파일러에 의해 어휘단계에서 만들어지는 테이블

 

2. 선형 탐색, 이진 탐색

선형 탐색 (Linear search) : 선형 검색은 순차 검색이라고도 하며 주어진 자료파일에서 특정한 원소를 첫 번째 레코드로부터 순차적으로 비교해 가면서 해당 키 값을 가진 레코드를 찾아내는 가장 간단한 검색 방법

이진 탐색 : 선형 탐색의 단점을 어느정도 해결한 것, 정렬된 데이터에서만 사용가능하다

 

3. 정렬

이진 탐색은 선형 탐색보다 검색효율이 좋기는 하지만 검색대상이 되는 data배열은 반드시 정렬되어있어야한다

 

4. Hashing

해싱은 산술적인 연산을 이용하여 키가 있는 위치를 계산하여 바로 찾아가는 계산 검색 방식

일종의 데이터 관리 기법

 

5. Hashing 함수, 테이블, 오버플로우

해싱은 산술적인 연산을 이용하여 키가 있는 위치를 계산하여 바로 찾아가는 계산검색 방식을 말하며 해시함수는 데이터를 자르고 치환하거나 위치를 바꾸는 등의 방법을 사용해 결과를 만들어 내는 것으로 결과를 흔히 해시 값이라 한다.

* 정리 후기

- 범위 이내의 최소한의 시간으로 최대한의 효과를 내야할듯. 매우 어렵다.