14. 컴파일러 자동화 도구 스캐너 생성기 파서 생성기 코드 생성의 자동화

Presentation on theme: "14. 컴파일러 자동화 도구 스캐너 생성기 파서 생성기 코드 생성의 자동화"— Presentation transcript:

1 14. 컴파일러 자동화 도구 14-1. 스캐너 생성기 14-2. 파서 생성기 14-3. 코드 생성의 자동화
14-4. 컴파일러-컴파일러 시스템

2 14-1. 스캐너 생성기 컴파일러-컴파일러 프로그래밍 언어와 목적 기계에 대한 표현 또는 의미 표현을
이용하여 그 언어를 목적 기계의 코드로 번역해 주는 컴파일러를 생성 컴파일러 - 컴파일러 언어 표현 의미 표현 또는 기계표현 원시 프로그램 컴파일러 목적 코드  컴파일러-컴파일러의 기능

3 스캐너 생성기 모델 정규 표현과 정규 표현이 매칭되었을 때 처리를 나타내는 수행
코드를 입력으로 받아 테이블과 그 테이블을 이용하여 입력을 처리하는 구동 프로그램을 출력한다. 정규 표현 + 수행 코드 스캐너 생성기 테이블 입력프로그램 토큰 Driver Routine  스캐너 생성기 모델

4 스캐너 생성기에 대한 메타 언어는 입력 언어에 대한 토큰을 기술하는 정규 표현이다. 수행 프로그램은 컴파일 시간에 입력
프로그램을 일고 새로운 상태로의 전이를 위해 테이블 엔트리의 현재 상태를 참조한다. 테이블 [state, inputChar]의 엔트리는 새로운 상태와 새로운 상태로 전이가 발생하기 전에 수행되는 동작들로 구성되어 있다. 스캐너 생성기를 설계하는 단계 정규 표현의 인식 정규 표현은 정규 언어를 표현한기 위한 방법으로 정규 문법으로 부터 얻어지는 정규 표현식을 해결함으로써 얻을 수 있으며 토큰을 인식하는 유한 오토마타를 구성하는 데 사용된다.

5 정규 표현을 유한 오토마타로 변환 어휘 분석기를 고안하고 구현하는 방법으로 유한 오토마타를 사용한다. 오토마타는 그 형태에 따라 결정적 FA와 비결정적 FA로 나누어진다. 비결정적 유한 오토마타를 결정적 유한 오토마타로 변환 일반적으로 NFA는 언어의 구조를 쉽게 표현할 수 있는 반면에 DFA보다 프로그램을 구현하기가 어려운데 다행히도 DFA의 상태들은 NFA의 모든 상태 집합의 부분집합으로 표현함으로써 어떤 NFA에 대해서도 같은 언어 를 인식하는 DFA를 만들 수 있다. DFA의 간소화 DFA의 상태 수 최소화는 DFA를 이용하는 어휘 분석기의 상태 전이표의 크기를 줄임으로써 기억 공간을 적게 차지하도록 하고 또한 어휘 분석 프로그램을 간단히 하는데 도움을 준다. 상태 수를 최소하는 방법은 동치 관계를 이용하여 상태들을 합침으로써 상태 수를 최소화 한다.

6 14-2. 파서 생성기 정의 구문분석기를 자동으로 생성하는 도구
입력으로는 BNF나 EBNF로 기술된 context-free문법 표현을 사용 문법표현 파서 생성기 테이블 입력 파 서 출력  파서 생성기와 파서의 관계

7 YACC 파서를 제어하는 테이블을 생성한다. 파서는 이 테이블 정보를
이용하여 주어진 문장에 대한 문법적인 검사를 하며 다음 단계 에서 필요한 정보를 만든다. 모든 입력 언어에 대하여 파서 부분 은 같고 테이블만 다르므로 새로운 언어에 대한 파서를 만들기 위해서는 단지 문법 표현만 바꾸면 된다. YACC 문법 규칙과 수행 코드 YACC 토큰 원시 프로그램 스캐너 파 서 수행 코드에 의해 생성된 파서의 출력  YACC의 기능

8 개요 YACC의 사용자는 입력 자료들의 처리에 관한 명세를 제공해야
하는데, 입력 명세는 언어의 구조를 나타내는 생성 규칙과 규칙들이 인식 되었을 때 호출되는 의미 수행 코드들, 그리고 입력 언어를 처리 하는데 필요한 기본적인 프로그램들로 구성된다. 그러면 YACC는 입력 처리를 제어하는 기능을 가지는 프로그램을 생성한다. 파서라 불리는 이 프로그램은 입력 스트링으로부터 토큰을 구하기 위하여 사용자가 제공한 스캐너를 호출한다. 이러한 토큰들은 생성 규칙이라 하는 입력의 구조에 따라 구성되는데 이러한 생성 규칙이 인식되었을 때 사용자가 제공한 의미 수행코드인 행동이 호출된다. 행동은 임의의 값을 전달하거나 다른 행동에서 그 값을 사용 할 수 있게 하는 기능을 한다.

9 스탠포드 파서 제작 시스템 문법 규칙에 구문 트리를 자동으로 만들 수 있는 정보를 결합
시킬 수 있다. 파서 생성기의 출력으로는 문법 규칙에 대해 LALR(1)구문분석을 수행하여 파싱 테이블과 구문 트리에 대한 정보를 만들고, 스캐너로 사용자가 고쳐 쓴 parser skeleton을 이용하여 입력 원시 프로그램에 대한 구문 분석을 수행하고 구문 트리를 얻는다. 구조 pgstbl PASS-1 Pass.pgs PASS-2 Pgs2.1st *.cfg Pgs2.tbl Pgs1.1st  스탠포드 PGS의 구조

10 위스콘신 파서 제작 시스템 파서 생성기로 구문 분석을 위한 정보뿐만 아니라 에러 복구를 위한 정보도 출력한다. 구문 분석기는 이 정보를 이용하여 에러 발생시에 그에 대한 처리를 한다. 구조 및 동작 원리 토큰을 정의한 정규수식 SCANGEN 입력 정규 수식에 대한 전이 테이블 입력 문자열 Driver Routine 출력 문자열  SCANGEN 구조및 동작 원리

11 ECP(An Error Correcting Parser generator)
특징은 오류 수정이 실제로 구현되어 있어 오류 수정 파서를 생성한다. ECP와 FMQ의 차이는 LALR및 LL 파싱 방식의 차이에 따른 수용하는 입력 문법의 범위, 출력하는 파싱 테이블의 구조, 그리고 의미 분석기와 연결 부분이다. 구조 LALR(1) 문법을 기술한 화일 ECP 오류 수정 테이블 파싱 테이블 입력 프로그램 LRParser 출력 프로그램  ECP의 구조

12 14-3. 코드 생성의 자동화 정의 컴파일러 후단부에서 새로운 목적 기계에 대해 원시 프로그램의
중간 언어를 목적 기계 언어로 바꾸는 과정을 기계 정형화를 통하여 자동적으로 구성하는 것 목적 기계 표현 코드-생성기 생성기 테이블 중간 표현 코드 생성기 목적 코드  코드 생성기의 자동화 모델

13 해석적 코드 생성방식 가상 기계에 대한 코드를 생성하고 실제 목적 기계에 대한 코드의
생성은 마크로 확장이나 스키마를 이용한다. 이 기법에서는 코드 생성 방법과 목적 기계에 대한 특징이 혼합되어 있어 다른 목적 기계에 대한 코드 생성시에 코드 생성 부분의 수정과 동시에 목적 기계의 특징을 수정해야 하는 단점을 가지고 있다. 해석적 코드 생성 알고리즘 목적 기계 표현 중간 코드 가상 기계 코드 목적 기계 코드  해석적 코드 생성 시스템

14 패턴 매칭 코드 생성 이식성을 위한 코드 생성 연구로 코드 생성 알고리즘 자체로부터 기계 표현을 분리하는데 집중하였다. 장점
코드 선택 알고리즘이 목적 컴퓨터의 명령어 집합에 의존하기 때문 에 모든 가능한 명령어들은 코드 생성기에 의해 고려 될 수 있다. 명령어 집합을 조심스럽게 순서화 한다면 표준화하지 않은 명령어 들에 대한 특별한 경우도 코드 생성기에서 자동적으로 발견 가능하 다는 것이다. 새로운 기종에 대한 컴파일러를 재목적화하기 위해서는 단지 트리 구성기에 입력함으로써 새로운 명령어 집합으로 대치만 해주면 새로 운 패턴 트리를 만들어 같은 코드 생성기를 사용 할 수 있다.

15 단점을 보완하여 covering문제와 blocking문제 해결 방법
코드 생성기를 위해 최적화된 트리 구조의 생성과 사용이 어렵다. 대응되는 완전한 전체의 패턴이 제공되는지를 보장할 만한 충분한 조건의 부족이다. 일련의 충분한 조건이 갖추어 지지 않는다면 코드 생성기의 타당한 입력에 대해서 제대로 동작함을 보장할 방법도 없 을 것이다. 발생된 코드의 질은 명령어 패턴 구조에 너무 의존한다. 즉, 최적화 트리 구성의 중요성을 의미한다. 단점을 보완하여 covering문제와 blocking문제 해결 방법 트리 패턴의 중간 코드를 입력으로 받아 목적 코드를 생성하는 방법 을 사용하였다. 코드 생성기는 트리를 순회하면서 최적의 목적 기계 코드를 생성한다.

16 테이블을 이용한 코드 생성 방식 트리 재구성을 이용한 코드 생성 방법
효율적인 코드 생성을 위해 TWIG라 부르는 트리 조작 언어를 이용해서 목적 기계의 코드를 생성하는 방법. TWIG를 위한 컴파일러는 트리-매칭 방법을 이용하고 있으며 중복된 패턴 매칭이 발생하는 경우, 최적화된 코드 생성을 위해 Aho에 의해서 제안된 동적 프로그래밍기법을 이용한다. 테이블을 이용한 코드 생성 방식 테이블을 이용한 코드 생성기와 코드 생성기에 대한 목적 기계를 설명하는 테이블을 만드는 코드-생성기 생성기를 구현하였다. 코드 생성기는 목적 기계의 기능적인 특징을 나타낸 테이블을 이용하여 shift-reduce 파싱 알고리즘에 따라 코드를 생성한다.

17  Graham과 Glanville시스템
환경에 대한 가정 컴파일러의 구현자가 전단부를 제공해야 한다. 이 전단부는 원시 프로그램을 코드 생성기가 사용할 수 있는 중간 언어로 번역해야 한다. 즉, 기억 장소 할당, 바인딩, 그리고 최적화 단계는 컴파일러의 제작자에 의해 제공되어야 한다는 것이다. 목적 기계 표현 원시 프로그램 코드 생성기-생성기 전 단 부 목적 기계 테이블 중간 코드 코드 생성기 목적 기계 코드  Graham과 Glanville시스템

18 14-4. 컴파일러-컴파일러 시스템 PQCC 입력 언어와 목적 기계에 대해 목적 코드를 생성하여 최적화
하는 컴파일러를 생성하는 시스템 효율적인 코드 생성과 신뢰도 가 높으며 시행 속도나 기억 공간 사용면에서 비용을 절약할 수 있는 최적화 단계를 잘 정립하여 실질적인 컴파일러-컴파일러 시스템을 구성

19 ACK 이식성과 재목적성이 매우 높은 컴파일러를 만들기 위한 실질적인 도구이며 다양한 특성을 갖는 컴파일러를 구성하기
언어와 목적 기계에 대한 표현 PQCC 테이블 원시 프로그램의 중간형태 원시프로그램 파서 PQC 목적 프로그램 (TCOL)  PQCC 시스템 ACK 이식성과 재목적성이 매우 높은 컴파일러를 만들기 위한 실질적인 도구이며 다양한 특성을 갖는 컴파일러를 구성하기 위해 여러 단계의 조합으로 구성된다. UNCOL의 개념을 기본으로 둔다.

20 . . ACK의 부분별 특징과 기능 프리 프로세서 언어-1로 쓰여진 원시프로그램 언어-1 기계-1 기계-1에 대한
목적 프로그램 U N C O L 기계-2에 대한 목적 프로그램 언어-2로 쓰여진 원시프로그램 언어-2 기계-2 . . 기계-3에 대한 목적 프로그램 언어-3로 쓰여진 원시프로그램 언어-N 기계-N  UNCOL 모델 ACK의 부분별 특징과 기능 프리 프로세서 프로그래밍 언어에 유용한 기능을 추가시킴으로써 언어를 확장시켜 주는 역할을 담당 마크로를 정의하고 확장하는 마크로 치환기능 컴파일 시간 라이브러리를 포함할 수 있는 기능 프로그램의 일부분을 선택적으로 컴파일 할수 있게 해주는 조건부 컴파일을 가능

21 프리프로세서의 출력을 입력으로 받아 ACK의 중간 코드인 EM코드로
전단부 프리프로세서의 출력을 입력으로 받아 ACK의 중간 코드인 EM코드로 변환하는 일을 수행하며 입력되는 각각의 언어에 대해 전단부가 하나씩 존재 중간 코드 : EM 가상 스택 기계에 기반을 둔 EM 기계의 어셈블리 언어이다. EM 기계 의 기억공간은 word단위의 크기를 갖는 선형 배열 형태로 가장 작은 주소단위는 바이트이며 명령어 주소 공간과 자료 주소 공간부분으로 분류된다. 또한 기억 공간은 기본주소와 크기를 갖는 연속된 word 단위 로 이루어진 fragment로 구성 자료주소공간 지정방식 전역 자료 영역은 EM어셈블리 언어의 의사 명령어를 위해 할당되는 영역으로서 번역 시간에 결정되는 한 바이트 이상의 고정된 크기를 가지고 있다. 또한 절대 주소를 가지지만 하나의 프로그램이 여러 개의 모듈로 이루어진 경우에는 절대 주소를 부여하지 않고 레이블로써 전역자료 영역의 처음주소를 지정하게 된다. 레이블은 절대 주소로의 번역은 링커 / 로더를 통해서 이루어진다.1

22 스택으로 이용되는 지역 자료 영역은 프로그램의 실행동안에
동적으로 변하는 특성을 가지며 프레임이라 부르는 현재 활동중인 프로시저의 자료를 저장하는 영역이다. 지역 자료 영역은 각각 증가 함에 따라 상위주소에서 하위 주소를 증가하며 스택 포인터인 SP가 이 영역을 가리킨다. 프레임은 프로시저의 호출에 의해 생성되고 프로시저 복귀 명령에 의해 소멸되는데 프레임에 대한 위치는 LB(Local Base)가 가리킨다. 하나의 프레임구조는 6부분으로 구성 1. 프로시저 매개 변수 저장부분 2. 리턴 상태 블록 3. 지역 변수와 컴파일러에서 생성된 임시 변수 저장부분 4. 레지스터 저장 블록 5. 동적 지역 생성자 6. 피연산자를 저장하는 스택 부분

23 연속적인 EM 명령어의 입력을 받아 의미적으로 같으면서 좀더 효율적인 EM명령어로 대치
핍홀 최적화 연속적인 EM 명령어의 입력을 받아 의미적으로 같으면서 좀더 효율적인 EM명령어로 대치 패턴 묘사 테이블 패턴 테이블 생성기 패턴 테이블 EM 명령어 부분 최적화기 최적화된 EM명령어 라이브러리  부분 최적화기 구성

24 전역 최적화 EM코드의 전체를 검사해서 효율적인 코드 생성하는 단계 다양한 전역 최적화를 위하여 프로그램 상에 존재하는 자료 흐름과 제어 흐름을 분석하여 자료 흐름 그래프와 제어 흐름 그래프의 구성 과 기본 블록의 구성을 통해서 다양한 최적화 기법을 수행 전역 최적화에서 수행하는 최적화 기법으로는 프로시저 호출 시에 발생하는 과부하를 감소시키기 위한 inlink substitution기법, 프로그램 의 수행 속도를 감소시키기 위해 연산자를 교환하는 연산 강도 경감 기법, 프로그램 상에 여러 번 공통으로 나타나는 부분식을 한 번만 계산 하여 사용할 수 있도록 하는 중복 수식 제거 기법, 프로시저 호출 시에 이용하는 스택의 이용에 있어 시간과 비용을 감소시키기 위한 stack pollution 기법, 코드들의 제어에 관한 분석기법

25 목적 기계에 대한 어셈블리 코드를 생성하는 단계 코드 생성 단계에서는 연산을 수행할 레지스터를 선택하거나
후단부 목적 기계에 대한 어셈블리 코드를 생성하는 단계 코드 생성 단계에서는 연산을 수행할 레지스터를 선택하거나 기억 장치에서 데이터의 위치를 결정하여 실제로 목적 기계에 대한 코드를 생성하는 단계 목적 기계 최적화 기계 종속적인 특성을 갖는 최적화로서 목적 기계의 코드에 대한 최적화를 수행 목적 기계 최적화 프로그램은 목적기계의 어셈블리 코드를 처리 하므로 서로 다른 목적 기계마다 별도의 최적화 프로그램이 필요 하다. 코드-생성기 생성기 목적 기계 표현 테이블 Table.h table.c 목적 기계 코드 EM 명령어 코드 생성기  코드 생성기의 구성

26 목적 기계 독립적인 부분과 목적 기계 의존적인 부분을 설명하는 테이블로부터 최적화 프로그램을 손쉽게 생성할 수 있는데 이러한
기능은 목적 기계 최적화기-생성기에 의해 수행 패턴 매칭 과정 현재 윈도에 존재하는 기호명령어와 일치하는 패턴을 찾는다. 현재 윈도에 존재하는 명령어의 피연산자가 패턴으로 들어오는 명령어의 피연산자와 일치하는지를 검사한다. 명령어가 제한 사항을 가지는 경우에 대해 검사함으로써 하나의 패턴 매칭 과정을 완료 목적 기계 독립적인 구동 루틴 목적 기계 의존적인 코드 + 테이블 목적 기계 최적화기 생성기 목적 기계 표현 테이블 <목적 기계 최적화기>  목적 기계 최적화기의 구성

27 범용 어셈블러와 링커 최적화된 목적 기계 어셈블리 코드를 입력으로 받아 실행 가능한 실행 형태로 출력한다. 범용 어셈블러는 바이트 단위의 크기를 갖는 목적 기계에 대한 어셈블러를 쉽게 생성할 수 있도록 해주는 도구이다. 이런 도구는 레이블의 사용, 기억장소의 사용과 초기화, 수식 계산의 순서에 관한 의사 명령어를 가지고 잇다. 링크-에디터는 여러 개의 목적 프로그램을 하나로 결합하고 외부 참조 와 같은 문제를 해결한다 응용 패키지 전단부와 후단부의 구현에 유용한 여러 가지 테스트 프로그램, EM 코드에 대한 인터프리터, EM 라이브러리, 변화 프로그램, 그리고, 구현자와 사용자에게 유용한 여러 가지 프로그램들로 구성된다.