컴파일러 구축의 역사

History of compiler construction
컴퓨팅의 역사
Ordinateurs centraux 348-3-006.jpg
하드웨어
소프트웨어
컴퓨터 공학
현대 개념
국가별
컴퓨팅 스케줄
컴퓨터 과학 용어집

컴퓨팅에서 컴파일러는 프로그래밍 언어 또는 컴퓨터 언어(소스 언어)로 작성된 소스 코드를 다른 컴퓨터 언어(대상 언어, 종종 객체 코드 또는 기계 코드라고 알려진 이진 형식을 가지고 있음)로 변환하는 컴퓨터 프로그램입니다.소스 코드를 변환하는 가장 일반적인 이유는 실행 가능한 프로그램을 만드는 것입니다.

고급 프로그래밍 언어로 작성된 프로그램은 실행되기 전에 오브젝트 코드로 변환되어야 합니다.따라서 이러한 언어를 사용하는 모든 프로그래머는 컴파일러 또는 인터프리터를 사용합니다.따라서 컴파일러는 프로그래머에게 매우 중요합니다.컴파일러가 개선되면 실행 프로그램의 기능이 대폭 향상될 수 있습니다.

1970년대 후반에 Production Quality Compiler-Compiler는 오늘날에도 널리 사용되는 컴파일러 구성 원리(예: 프런트 엔드 핸들링 구문 및 의미론, 백 엔드 생성 머신 코드)를 도입했습니다.

최초의 컴파일러

초기 컴퓨터용 소프트웨어는 주로 어셈블리 언어로 작성되었으며, 그 이전에는 기계어로 직접 작성되었습니다.일반적으로 프로그래머는 고급 언어를 사용하는 것이 더 생산적이고 고급 언어로 작성된 프로그램은 다른 종류의 컴퓨터에서 재사용할 수 있습니다.그렇다고 해도 컴파일러가 확립되기까지는 시간이 걸렸습니다.왜냐하면 컴파일러는 손으로 쓴 어셈블러만큼 동작하지 않는 코드를 생성하기 때문에 개발 프로젝트 자체가 벅차고 초기 컴퓨터의 메모리 용량이 매우 한정되어 있기 때문에 실용적인 컴파일러 구현에 많은 기술적 문제가 발생했기 때문입니다.

최초의 실용적인 컴파일러는 1951년 Corrado Böhm에 의해 박사학위 논문을 위해 작성되었습니다.최초로 구현된 컴파일러는 그레이스 호퍼에 의해 작성되었으며, 그레이스 호퍼는 "컴파일러"[1][2]라는 용어를 만들었으며, 이는 컴파일러의 현대적인 개념이 아닌 로더 또는 링커로 기능하는 A-0 시스템을 가리켰다.현대적 의미의 최초의 오토코드 및 컴파일러는 1952년 맨체스터 대학의 Alick Glennie에 의해 Mark 1 컴퓨터를 [3][4]위해 개발되었습니다.IBM의 John W. Backus가 이끄는 FORTRAN 팀은 1957년에 상업적으로 이용 가능한 최초의 컴파일러를 선보였습니다. [5]이 컴파일러를 만드는 데 18명이 걸렸습니다.

최초의 ALGOL 58 컴파일러는 1958년 말까지 Friedrich L. Bauer, Hermann Bottenbruch, Heinz Rutishauser 및 Klaus Samelson에 의해 Z22 컴퓨터용으로 완성되었습니다.바우어 등님은 이전 몇 년 동안 Sequentielle Formelübersetzung(시퀀셜 공식 번역) 컴파일러 테크놀로지에 종사해 왔습니다.

1960년까지 확장 Fortran 컴파일러인 ALTAC가 Philco 2000에서 사용 가능했기 때문에 1960년 [6]중반에 IBM과 Philco 컴퓨터 아키텍처 모두를 위해 Fortran 프로그램이 컴파일되었을 가능성이 있습니다.최초로 입증된 크로스 플랫폼 고급 언어는 COBOL이었습니다.1960년 12월 시연에서 COBOL 프로그램은 UNIVAC II와 RCA 501 모두에서 [2]컴파일되어 실행되었습니다.

셀프호스팅 컴파일러

컴파일러 컴파일러와 혼동하기로 했다.

다른 소프트웨어처럼 아주 높은 수준의 언어로 만든 컴파일러는 현실에서 이점이 있다.– 그것은 특히 컴파일러, 그것을 편집하는 프로그래밍 언어로 쓰여져self-hosted 수 있다.언어로는 처음 컴파일러가 되어야 한다 어느 손 쓴 기계 코드 또는 컴파일러 또 다른 언어를 가르치거나 통역사의 컴파일러 실행에 의해 편집된으로 작성된 편집과 같은self-hosting 컴파일러를 짓는 것이 자동 처리 문제이다.

Corrado Böhm 박사 학위 논문

코르라도 뵘 언어를, 기계가 이 기계에 그의 박사 논문에서 해당 언어 1951년 데이트를 했고 종합 번역 방법을 개발했다.그는 뿐만 아니라 처음에 대해 정의된 완전한 컴파일러 설명한 자체 언어 컴파일러.과제가 성명의 모든 발언을(입력, 출력 정보와 제어 진술을 포함한)특별한 경우 그 언어 그 자체에 흥미로웠습니다.[표창 필요한]

NELIAC

는 알골 58프로그래밍 언어는 해군 전자 연구소가 1958년에 개발된 해군 전자 연구소 국제 알골 컴파일러 또는 NELIAC 방언과 컴파일러의 구현입니다.[7]

해리 Huskey의 NELIAC가 창안한 다음 회장 ACM의 Communications 지고 유명한 컴퓨터 과학자(니클라우스 워스의 나중에 학문적 상사)–, 모리 할스테드, NEL에 계산적 센터 대표가 논의된다.가장 초기의 버전은 실험실에 대한 프로토 타입 USQ-17 컴퓨터(그 Countess라고 불리는)에 실시되었다.컴파일러 먼저 언어를 어셈블리(는 부트 스트랩)에 약식, 그 다음에 자신의 언어에 부트 스트랩에 의해 컴파일되고 마침내 스스로, 부트 스트랩은 쓸모 없는 것을 만들고 re-compiled re-written으로 암호화 되었어 이것이 바로 세계 최초의self-compiling 컴파일러 –.

리스프

또 다른 초기self-hosting 컴파일러 Lisp에 팀 하트와 마이크 레빈 MIT에서 1962년에 쓰여졌다.[8]그들은 Lisp에, 기존 Lisp 통역사 안에 그걸 검사한 Lisp 컴파일러를 썼다.일단 그것은 자신의 소스 코드를 컴파일 수 있을 정도로 그 컴파일러를 개선해, self-hosting다.[9]

표준 컴파일러 테이프에 존재하는 컴파일러는 컴파일러의 S 표현 정의를 인터프리터를 통해 스스로 동작시킴으로써 얻은 기계어 프로그램입니다.(AI 메모 39)[9]

이 기술은 컴파일 대상과 동일한 언어를 지원하는 인터프리터가 이미 존재하는 경우에만 가능합니다.이것은 프로그램 자체를 입력으로 실행한다는 개념에서 직접 차용되며, 이는 정지 문제가 결정 불가능하다는 증거와 같은 이론 컴퓨터 과학에서의 다양한 증명에도 사용됩니다.

넷째

Fourth는 셀프호스팅 컴파일러의 예입니다.Forth의 자체 컴파일 및 교차 컴파일러 기능은 메타 컴파일러 및 메타 [10][11]컴파일러와 동의어입니다.리스프와 마찬가지로 포스도 확장 가능한 프로그래밍 언어입니다.Forth 및 Lisp의 확장 가능한 프로그래밍 언어 기능으로 새로운 버전의 자기 자신을 생성하거나 새로운 환경에 포팅할 수 있습니다.

문맥이 없는 문법 및 파서

파서는 컴파일러의 중요한 컴포넌트입니다.컴퓨터 프로그래밍 언어의 소스 코드를 해석하여 내부 표현의 형태를 만듭니다.프로그래밍 언어는 빠르고 효율적인 파서가 작성될 수 있기 때문에 문맥이 없는 문법으로 지정되는 경향이 있습니다.파서는 손으로 작성하거나 파서 생성기로 생성할 수 있습니다.문맥이 없는 문법은 프로그래밍 언어 구조가 더 작은 블록에서 어떻게 구축되는지를 기술하기 위한 간단하고 정확한 메커니즘을 제공한다.문맥이 없는 문법의 형식주의는 1950년대 중반 노암 촘스키에 [12]의해 개발되었다.

블록 구조는 ALGOL 프로젝트(1957–1960)에 의해 컴퓨터 프로그래밍 언어에 도입되었고, 결과적으로 ALGOL 구문을 설명하는 문맥 없는 문법을 특징으로 했다.

문맥이 없는 문법은 주어진 문자열에 대해 문법에 의해 생성될 수 있는지 여부와 방법을 결정하는 효율적인 구문 분석 알고리즘을 구성할 수 있을 정도로 단순합니다.프로그래밍 언어 디자이너가 문맥이 없는 문법의 일부 제한된 하위 집합 내에서 작업할 의향이 있다면 더 효율적인 파서가 가능합니다.

LR 해석

주요 기사: LR 파서

LR 파서(왼쪽에서 오른쪽으로)는 1965년 도널드 크누스에 의해 "왼쪽에서 오른쪽으로의 언어 번역에 대하여"라는 논문에서 발명되었습니다.LR 파서는 왼쪽에서 오른쪽으로 입력을 읽고(시각적으로 표시되는 경우 표시됨) 가장 오른쪽에서 파생되는 파서입니다.LR(k) 파서라는 용어도 사용됩니다.여기서 k는 파싱 결정에 사용되는 사용되지 않은 사전 예측 입력 기호 수를 나타냅니다.

Knuth는 LR(k) 문법이 프로그램의 길이에 본질적으로 비례하는 실행 시간으로 해석될 수 있고 k > 1에 대한 모든 LR(k) 문법이 같은 언어에 대한 LR(1) 문법으로 기계적으로 변환될 수 있다는 것을 증명했다.즉, deterministic context-free grammar(DCFG;[13] 결정론적 컨텍스트프리 문법)를 해석하려면 사전에 하나의 기호만 있으면 됩니다.

Korenjak(1969년)은 이 [14]기술을 이용해 프로그래밍 언어 파서를 제작할 수 있다는 것을 최초로 보여주었다.Frank DeRemer는 보다 [15][16]실용적인 단순 LR(SLR) 및 Look-Ahead LR(LALR) 기술을 고안하여 1969년 MIT 박사학위 논문에서 발표하였습니다.Donald Knuth가 정의한 LR(k) 번역기는 1960년대와 1970년대에 컴퓨터 시스템에 구현하기에는 너무 컸기 때문에 이것은 중요한 돌파구였습니다.

실제로 LALR은 좋은 솔루션을 제공합니다.SLR(1)파서에 대한 LALR(1)파서의 추가 파워(즉, LALR(1)는 SLR(1)보다 복잡한 문법을 해석할 수 있음)는 유용하며, LALR(1)은 LL(1)과는 비교가 되지 않습니다.LR(1) 문법은 LALR(1)보다 강력하지만 LR(1) 문법은 크기가 매우 크고 실용적이지 않은 표준 LR 파서가 필요합니다.많은 프로그래밍 언어의 구문은 LALR (1) 파서로 해석할 수 있는 문법에 의해 정의됩니다.이 때문에 LALR 파서는 소스 코드의 구문 분석을 수행하기 위해 컴파일러에 의해 자주 사용됩니다.

재귀 상승 파서는 테이블이 아닌 상호 재귀 함수를 사용하여 LALR 파서를 구현합니다.따라서 파서는 재귀적 하강과 유사하게 호스트 언어로 직접 인코딩됩니다.다이렉트 부호화에서는 보통 해석보다 컴파일이 빠르다는 것과 같은 이유로 테이블 구동형보다[17] 빠른 파서가 생성됩니다.(원칙적으로) 재귀 상승 파서를 손으로 편집할 수도 있지만, 표 형식의 구현은 일반인이 거의 읽을 수 없습니다.

재귀적 상승은 토마스 페넬로가 1986년 [17]그의 기사 "매우 빠른 LR 구문 분석"에서 처음 설명했습니다.이 기술은 후에 1988년 G.H. 로버츠에[18] 의해 설명되었고 1992년 이론 컴퓨터 과학 저널에 Leermakers, Augusteijn, Kruseman[19] Aretz의 기사에서 설명되었다.

LL 해석

주요 기사: LL 파서

LL 파서는 Left에서 Right로의 입력을 해석하고 문장의 Left derivation(LR이 아닌 LL)을 작성합니다.이렇게 파싱할 수 있는 문법의 클래스를 LL 문법이라고 합니다.LL 문법은 LR 문법에 비해 문맥이 없는 문법의 제한된 클래스입니다.그럼에도 불구하고 이러한 파서는 구현이 간단하고 효율적이기 때문에 컴파일러 라이터에게는 큰 관심사가 됩니다.

LL(k) 문법은 META II와 같은 표기법을 대신 사용할 수 있지만 일반적으로 손으로 코드화된 재귀 하강 파서로 구문 분석할 수 있습니다.

ALGOL의 설계는 ALGOL 언어 자체가 재귀적이었기 때문에 재귀적 하강 연구를 촉발시켰다.재귀 강하 해석의 개념은 A.A.의 개별 논문에서 ACM 통신 1961년 1월호에 논의되었다.그라우와 에드거 T. "네드"[20][21] 아이언.Richard Waychoff와 동료들은 또한 1961년 [22]3월에 Burroughs ALGOL 컴파일러에서 재귀 강하를 구현했고, 두 그룹은 다른 접근법을 사용했지만 적어도 비공식적인 [23]접촉을 했다.

LL (1) 문법의 개념은 루이스와 스턴스에 의해 도입되었다.[24][25]

재귀적 하강은 Niklaus Worth에 의해 1970년대에 [26]컴파일러 구조를 가르치는 데 사용된 교육용 프로그래밍 언어인 PL/0으로 대중화되었습니다.

LR 파싱은 LL 파싱보다 더 많은 범위의 언어를 처리할 수 있으며 오류 보고(이는 논란의 여지가 있으며 REFERENCE가 필요합니다)에도 더 뛰어납니다. 즉, 입력이 문법에 부합하지 않을 때 구문 오류를 가능한 한 빨리 탐지합니다.

얼리 파서

1970년에 제이 얼리는 얼리 파서로 알려진 것을 발명했다.얼리 파서는 문맥이 없는 모든 언어를 합리적으로 효율적으로 [27]해석할 수 있기 때문에 매력적입니다.

문법 기술 언어

존 배커스는 오늘날 ALGOL 58(1959)로 알려진 새로운 프로그래밍 언어 IAL의 구문을 설명하기 위해 "메탈링구이스트 공식"[28][29]을 제안했다.배커스의 연구는 Emil Post가 고안한 Post 표준 시스템에 기초했다.

ALGOL의 추가적인 발전은 ALGOL 60으로 이어졌다; 보고서(1963년)에서 피터 나우어는 백커스의 표기법 BNF(Backus normal form)를 명명하고 사용된 문자 집합을 최소화하기 위해 그것을 단순화했다.그러나 Donald Knuth는 BNF가 오히려 Backus-Naur [30]형식으로 읽혀져야 한다고 주장했고, 이는 일반적으로 받아들여지는 용법이 되었다.

Niklaus Worth는 1970년대 초에 PL/0에 대해 BNF의 정제된 버전인 확장 Backus-Naur 형식(EBNF)을 정의했다.증강 배커스-나우르 형식(ABNF)도 다른 변종입니다.EBNF와 ABNF는 모두 파서 생성기에 대한 입력으로서, 그리고 통신 프로토콜 정의와 같은 다른 분야에서 프로그래밍 언어의 문법을 지정하는데 널리 사용된다.

파서 생성기

LL, SLR, GLR 및 LR 파서 생성기도 포함하는 자세한 목록은 파서 생성기 비교를 참조하십시오.

파서 제너레이터는 컴파일러의 어휘 분석 부분을 생성한다.특정 프로그래밍 언어의 정식 문법에 대한 설명을 받아 해당 언어의 파서를 생성하는 프로그램입니다.이 파서는 특정 언어의 컴파일러에서 사용할 수 있습니다.파서는 텍스트 스트림에서 특정 언어의 예약된 단어와 기호를 검출하고 식별하여 구문 검증 및 객체 코드로 변환하는 코드에 토큰으로 반환합니다.컴파일러의 이 두 번째 부분은 컴파일러에 의해 생성될 수도 있습니다.이때 정식 우선 순위 구문 설명을 입력으로 사용합니다.

이 이름을 사용한 최초의 컴파일러는 1960년 토니 브루커에 의해 작성되었으며 아틀라스 오토코드 컴파일러를 포함한 맨체스터 대학의 아틀라스 컴퓨터용 컴파일러를 만드는 데 사용되었다.그러나 이것은 현대의 컴파일러와 다소 달랐고, 오늘날에는 아마도 매우 맞춤성이 높은 범용 컴파일러와 확장 가능한 구문 언어 사이의 어딘가에 있다고 설명될 것이다."컴파일러-컴파일러"라는 이름은 파서 생성기로 더 정확하게 묘사되는 대부분의 현대 컴파일러-컴파일러보다 브루커 시스템에 훨씬 더 적합했다.브루커의 연구가 [citation needed]기억되기보다는 야크 때문에 컴파일러-컴파일러라는 이름이 보편화 된 것이 거의 확실하다.

1960년대 초, Texas Instruments의 Robert McClure는 "transmogrification"[31][32][33][34]에서 따온 TMG라는 컴파일러를 발명했습니다.그 후 몇 년 동안 TMG는 여러 UNIVAC 및 IBM 메인프레임 컴퓨터에 이식되었습니다.

MIT와 Bell Labs가 합작한 Multics 프로젝트는 운영체제를 고급 언어로 개발한 최초의 프로젝트 중 하나입니다.언어로 PL/I가 선택되었지만 외부 공급업체에서 작동하는 [35]컴파일러를 제공할 수 없습니다.Multics 팀은 1964년에 구현 언어로 초기 PL/I(EPL)로 알려진 자체 PL/I 하위 집합을 개발했습니다.TMG는 GE-600 시리즈로 이식되어 더글라스 맥일로이, 로버트 모리스 등에 의해 EPL 개발에 사용되었다.

1969년 Ken Thompson이 PDP-7용 Unix의 첫 버전을 작성한 지 얼마 되지 않아 Douglas McIlroy는 새로운 시스템의 첫 번째 고급 언어를 개발했습니다.Mclue의 TMG [36]구현은 1970년 Ken Thompson이 자신의 PDP-7 언어용 컴파일러를 작성하기 위해 사용한 컴파일러 정의 도구이기도 했습니다.B는 C의 직계 조상이다.

초기 LALR 파서 제너레이터는 프랭크 드 레머와 톰 페넬로가 만든 "TWS"라고 불렸다.

XPL

XPL은 컴퓨터 언어용 컴파일러 개발에 사용되는 PL/I 프로그래밍 언어의 방언입니다.1967년에 William M과 함께 한 팀에 의해 설계되고 구현되었습니다. 맥키먼, 제임스 호닝, 데이비드 B. 스탠포드 대학과 캘리포니아 대학 산타크루즈 대학의 Wortman.그것은 [37][38]1968년 샌프란시스코에서 열린 가을 컴퓨터 회의에서 처음 발표되었다.

XPL은 MSP(혼합 전략 우선 순위)라고 불리는 상향식 컴파일러 우선 순위 해석 기술에 기반한 Analyzer라는 비교적 단순한 번역기 쓰기 시스템을 갖추고 있습니다.XPL은 Burroughs Algol을 통해 IBM System/360 컴퓨터로 부팅 스트랩되었습니다.(토론토 대학 내부 프로젝트에서 사용된 일부 후속 버전의 XPL은 SLR(1) 파서를 사용했지만, 이러한 구현은 배포된 적이 없습니다.)

야카

Yacc는 파서 제너레이터(loose, compiler-compiler)로, Yacc가 1단계로 자주 사용하는 어휘 분석기인 lex와 혼동하지 않습니다.Yacc는 Stephen C에 의해 개발되었다. Unix [39]운영체제용 AT&T의 Johnson씨.이 이름은 "Yet Another Compiler"의 약자입니다.이것은 Backus-Naur 형식과 유사한 표기로 작성된 문법에 따라 LALR(1) 컴파일러를 생성합니다.

Johnson은 1970년대 초에 [40]Bell Labs에서 Yacc에 대해 연구했습니다.그는 TMG에 익숙했고, 그 영향은 Yacc와 C 프로그래밍 언어의 설계에서 확인할 수 있다.Yacc는 대부분의 Unix 시스템에서 기본 컴파일러 생성기였기 때문에 널리 배포되어 사용되었습니다.GNU Bison과 같은 파생상품은 여전히 사용되고 있습니다.

Yacc에 의해 생성된 컴파일러에는 어휘 분석기가 필요합니다.렉스나 플렉스와 같은 어휘 분석기 생성기를 널리 사용할 수 있습니다.IEEE POSIX P1003.2 표준은 Lex와 Yacc의 기능과 요건을 정의합니다.

코코/R

Coco/R은 EBNF의 변형으로 작성된 입력 문법에서 Modula-2(다른 언어용 플러그인 포함)의 LL(1) 파서를 생성하는 파서 제너레이터입니다.그것은 1985년 취리히에 있는 스위스 연방공과대학(ETHZ)의 한스페터 뫼센뵈크에 의해 개발되었다.

앤티엘

ANTLR은 EBNF의 변형으로 작성된 입력 문법에서 Java의 LL(*) 파서를 생성하는 파서 생성기입니다.1990년대 초 샌프란시스코 대학의 Terence Parr에 의해 PCCTS라고 불리는 초기 발전기의 후속 기종으로 개발되었습니다.

메타 컴파일러

주요 기사: 메타 컴파일러

메타 컴파일러는 파서 생성기와 다르며 메타 언어로 작성된 프로그램을 입력으로 사용합니다.입력은 추상 구문 트리를 구성하거나 단순히 스택 머신 코드일 수 있는 포맷된 텍스트 문자열을 출력하는 내장된 변환 연산과 결합된 문법 분석 공식으로 구성됩니다.

대부분은 자체 메타 언어로 프로그래밍할 수 있으며, 이를 통해 자체 컴파일러를 확장 가능한 언어 컴파일러를 스스로 호스트할 수 있습니다.

많은 메타 컴파일러가 듀이 발 쇼레의 작품을 기반으로 한다.1964년에 처음 출시된 그의 META II 컴파일러는 최초의 문서화된 메타 컴파일러였다.META II는 독자적인 언어 등을 정의할 수 있기 때문에 출력(코드 생성)이 내장된 구문식을 받아들였습니다.또한 가상 머신의 초기 인스턴스 중 하나로 변환되었습니다.어휘 분석은 토큰 인식 함수를 빌드하여 수행되었습니다. :ID, .STRING 및.NUMBER. 구문 수식의 따옴표로 둘러싸인 문자열은 [41]유지되지 않는 어휘소를 인식합니다.

2세대 쇼레 메타 컴파일러인 TREE-META는 1968년경에 등장했습니다.META II의 기능을 확장하여 코드 생성과 문법 분석을 분리하는 비파스 규칙을 추가하였다.구문 수식의 트리 변환 작업은 구문 분석 규칙이 작동하는 추상 구문 트리를 생성합니다.unparse tree 패턴 매칭은 peephole 최적화 기능을 제공하였습니다.

1970년 ACM 출판물에 기술된 CWIC는 문법 분석에 어휘 규칙과 역추적 연산자를 추가한 제3세대 쇼레 메타 컴파일러입니다.LISP 2는 CWIC 제너레이터 언어로 TREEMETA의 언파스 규칙과 결합되었습니다.LISP 2 처리를 통해 CWIC는 완전히 최적화된 코드를 생성할 수 있습니다.CWIC는 또한 명명된 코드 섹션에 바이너리 코드 생성을 제공했습니다.싱글패스 컴파일과 멀티패스 컴파일은 CWIC를 사용하여 구현할 수 있습니다.

주로 IBM System/360 코드를 생성하도록 설계된 8비트 바이트 주소 지정 가능한 기계 코드 명령으로 컴파일된 CWIC.

후세대는 공개적으로 기록되지 않는다.하나의 중요한 기능은 타깃 프로세서 명령어 세트를 추상화하여 개별 정의 또는 실제 머신의 명령에 매핑할 수 있는 의사 머신 명령어 세트, 매크로로 생성하는 것입니다.순차 명령에 적용되는 최적화는 대상 기계 코드로 확장되기 전에 의사 명령에 적용될 수 있습니다.

교차 컴파일

크로스 컴파일러는 한 환경에서 실행되지만 다른 환경에서는 객체 코드를 생성합니다.크로스 컴파일러는 대상 컴퓨터의 기능이 제한된 임베디드 개발에 사용됩니다.

교차 컴파일의 초기 예는 AIMICO로, UNIVAC II의 FLOW-MATIC 프로그램을 사용하여 IBM 705용 어셈블리 언어를 생성하고 IBM [2]컴퓨터에서 어셈블리했습니다.

ALGOL 68C 컴파일러는 ZCODE 출력을 생성하여 ZCODE 변환기에 의해 로컬머신 코드로 컴파일 하거나 인터프리터를 실행할 수 있습니다.ZCODE는 레지스터 기반의 중간 언어입니다.ZCODE를 해석하거나 컴파일하는 이러한 기능은 ALGOL 68C를 수많은 다른 컴퓨터 플랫폼으로 이식하는 것을 장려했습니다.

컴파일러 최적화

컴파일러 최적화란 오브젝트코드가 생성하는 결과를 변경하지 않고 오브젝트코드의 품질을 향상시키는 프로세스입니다.

최초의 FORTRAN 컴파일러의 개발자는, 고객이 실제로 제품을 사용할 수 있도록, 평균적인 손으로 코딩된 어셈블러보다 뛰어난 코드를 생성하는 것을 목표로 하고 있었습니다.최초의 실제 컴파일러 중 하나에서 그들은 [42]종종 성공했다.

IBM의 Fortran IV 컴파일러와 같은 이후 컴파일러는 객체 코드 최적화를 희생시키면서 우수한 진단과 보다 빠른 실행에 더 많은 우선순위를 두었다.IBM System/360 시리즈가 되어서야 IBM은 두 개의 개별 컴파일러, 즉 빠른 실행 코드 검사기와 느린 최적화 컴파일러를 제공했습니다.

프랜시스 E. Allen은 John Cocke와 단독으로 공동으로 작업하면서 최적화를 위한 많은 개념을 소개했습니다.앨런의 1966년 논문인 프로그램 최적화(Program Optimization)[43]는 최적화를 [44]위한 프로그램 콘텐츠를 인코딩하기 위해 그래프 데이터 구조를 사용하는 방법을 소개했습니다.1970년 논문인 Control Flow[45] Analysis와 A Basis for Program[46] Optimization은 효율적이고 효과적인 데이터 흐름 분석 및 최적화를 위한 컨텍스트로서 간격을 확립했습니다.1971년 Cocke와 함께 작성한 A Catalogue of Optimizing [47]Transformations는 변환 최적화에 대한 첫 번째 설명과 체계화를 제시했습니다.1973년과 1974년 그녀의 절차 간 데이터 흐름 분석에 대한 논문은 분석을 전체 [48][49]프로그램으로 확장했다.1976년 Cocke와의 논문에서 오늘날 [50]컴파일러 최적화에 사용되는 두 가지 주요 분석 전략 중 하나를 설명합니다.

Allen은 IBM 7030 Stretch-Harvest 및 실험용 Advanced Computing System용 컴파일러의 일부로 자신의 방법을 개발하고 구현했습니다.이 연구는 현대 기계 및 언어 독립적 최적기의 실현 가능성과 구조를 확립했다.그녀는 계속해서 포트란 프로그램의 자동 병렬 [51]실행에 관한 PTRAN 프로젝트를 수립하고 이끌었습니다.그녀의 PTRAN 팀은 새로운 병렬 검출 방식을 개발하고 대부분의 병렬 컴파일러에서 사용되는 주요 구조 방법인 프로그램 의존성 그래프의 개념을 만들었습니다.

John Coke와 Jacob T의 프로그래밍 언어 및 컴파일러. 1970년 초에 출판된 Schwartz는 최적화 알고리즘에 200페이지 이상을 할애했습니다.여기에는 중복 코드 제거 및 강도 [52]감소와 같이 현재 친숙한 많은 기술이 포함되어 있습니다.

핍홀 최적화

핍홀 최적화는 간단하지만 효과적인 최적화 기법이다.그것은 윌리엄 M.에 의해 발명되었다. 1965년 CACM에서 [53]출판된 McKeeman.McKeeman이 개발을 도운 XPL 컴파일러에서 사용되었습니다.

자본비용 COBOL 최적화 도구

Capex Corporation은 1970년대 중반에 COBOL용 "COBOL 옵티마이저"를 개발했습니다.이 경우, 이러한 유형의 최적화 도구는 표준 IBM COBOL 컴파일러의 "약점"에 대한 지식에 의존하여 실제로 객체 코드의 섹션을 보다 효율적인 코드로 대체(또는 패치 적용)했습니다.치환 코드는 예를 들어 선형 테이블 검색을 바이너리 검색으로 대체하거나, 경우에 따라서는 단순히 비교적 "느린" 명령을 컨텍스트 내에서 기능적으로 동등한 알려진 더 빠른 명령으로 대체할 수 있습니다.이 기술은 현재 "강도 감소"로 알려져 있습니다.예를 들어 IBM System/360 하드웨어에서 CLI 명령은 특정 모델에 따라 단일 바이트 [54][55]비교를 위한 CLC 명령보다 두 배에서 다섯 배 더 빨랐습니다.

최신 컴파일러는 일반적으로 최적화 옵션을 제공하여 프로그래머가 최적화 패스를 실행할지 여부를 선택할 수 있도록 합니다.

진단

컴파일러에 구문적으로 올바르지 않은 프로그램이 표시될 경우 양호하고 명확한 오류 메시지가 나타납니다.컴파일러 라이터의 관점에서 보면 달성하기 어려운 경우가 많습니다.

WATFIV Fortran 컴파일러는 1960년대 후반 캐나다 워털루 대학에서 개발되었습니다.이는 당시 IBM의 Fortran 컴파일러보다 더 나은 오류 메시지를 제공하도록 설계되었습니다.또한 WATFIV는 컴파일, 링크 및 실행을 한 단계로 통합한 반면 IBM의 컴파일러는 3개의 개별 구성 요소를 실행했기 때문에 훨씬 더 유용했습니다.

PL/C

PL/C는 1970년대 초 코넬 대학에서 개발된 컴퓨터 프로그래밍 언어입니다.PL/C는 IBM의 PL/I 언어의 하위 집합이었지만 프로그래밍 교육에 사용되도록 특별히 설계되었습니다.PL/C를 설계한 두 명의 연구원과 교사는 Richard W. Conway와 Thomas R.였다.윌콕스.그들은 1973년 [56]3월 ACM 통신지에 실린 유명한 기사 "PL/I 진단 컴파일러의 설계와 구현"을 제출했다.

PL/C는 PL/I의 보다 복잡한 기능을 일부 배제하고 광범위한 디버깅 및 오류 복구 기능을 추가했습니다.PL/C 컴파일러는 많은 구문 오류를 자동으로 수정하고 나머지 구문 오류를 출력문으로 변환함으로써 어떤 프로그램도 컴파일하지 못하는 특이한 기능을 가지고 있었습니다.

적시 컴파일

주요 기사:적시 컴파일

JIT(Just-in-Time) 컴파일은 런타임 메트릭 또는 기타 성능 향상 옵션을 활용하기 위해 실행 가능한 코드를 즉시 또는 가능한 한 실제 실행에 가깝게 생성하는 것입니다.

중간 표현

주요 기사:중간 표현

대부분의 최신 컴파일러는 프로그램의 중간 표현을 생성하는 렉서 및 파서를 가지고 있습니다.중간 표현은 옵티마이저와 대상 프로세서의 기계어로 명령을 생성하는 코드 생성기가 사용할 수 있는 간단한 연산 시퀀스입니다.코드 생성기는 중간 표현을 사용하기 때문에 동일한 코드 생성기를 다양한 고급 언어에 사용할 수 있습니다.

중간 표현은 여러 가지 가능성이 있다.쿼드러플 또는 쿼드라고도 불리는 3주소 코드는 연산자, 2개의 오퍼랜드 및 결과가 있는 일반적인 형식입니다.3 주소 코드의 명시적 변수와 대조적으로, 2 주소 코드 또는 3개에는 결과가 기록되는 스택이 있습니다.

Static Single Assignment(SSA)는 Ron Cytron, Jeanne Ferrante, Barry K에 의해 개발되었습니다. 로젠, 마크 N Wegman과 F. 1980년대 [57]IBM의 연구원 케네스 자덱입니다.SSA에서는 변수는 1회만 값이 지정됩니다.기존 변수를 수정하지 않고 새 변수를 만듭니다.SSA는 최적화와 코드 생성을 단순화합니다.

코드 생성

주요 기사:코드 생성(컴파일러)

코드 생성기는 대상 프로세서에 대한 기계어 명령을 생성한다.

레지스터 할당

Sethi-Ullman 알고리즘 또는 Sethi-Ullman 번호는 변수를 유지하는 데 필요한 레지스터 수를 최소화하는 방법입니다.

주목할 만한 컴파일러

참고 항목: ALGOL 60: ALGOL 60 구현 일정 및 컴파일러 목록

「 」를 참조해 주세요.

레퍼런스

  1. ^ 모리스 5세 윌크스, 1968년그때나 지금이나.컴퓨터 기계 협회 저널, 15 (1):1-7, 1월 3일자 (편집자가 괄호 안에 덧붙인 코멘트) (저는 컴파일러라는 용어가 실제로는 그레이스 호퍼에 의해 도입되었지만 당시 일반적으로 사용되고 있다고는 생각하지 않습니다.)"
  2. ^ a b c [1] 세계 최초 COBOL 컴파일러 2011년 10월 13일 Wayback Machine에 아카이브
  3. ^ Knuth, Donald E.; Pardo, Luis Trabb. "Early development of programming languages". Encyclopedia of Computer Science and Technology. 7: 419–493.
  4. ^ Bentley, Peter J. (2012). Digitized: The Science of Computers and how it Shapes Our World. Oxford University Press. p. 87. ISBN 9780199693795. Archived from the original on 29 August 2016.
  5. ^ 백커스 등"포트란 자동 코딩 시스템", Proc.AFIPS 1957 Western Joint Computer Conf., Spartan Books, Baltimore 188-198
  6. ^ [2] 로젠, 사울ALTAC, FORTRAN 및 호환성.1961년 제16차 ACM 전국회의의 의사록
  7. ^ "Algol 58 implementations and dialects — Software Preservation Group".
  8. ^ T. 하트와 M. Levin "The New Compiler", AIM-39 CSAIL 디지털 아카이브 – 인공지능 연구소 시리즈
  9. ^ a b Hart, Tim; Levin, Mike. "AI Memo 39-The new compiler" (PDF). Archived from the original (PDF) on 13 December 2020. Retrieved 23 May 2008.
  10. ^ "Introduction to metacompilation in FORTH". 24 March 2021.
  11. ^ https://howerj.github.io/embed/meta.htm
  12. ^ Chomsky, Noam (September 1956). "Three models for the description of language". IEEE Transactions on Information Theory. 2 (3): 113–124. doi:10.1109/TIT.1956.1056813. S2CID 19519474.
  13. ^ Knuth, Donald. "On the Translation of Languages from Left to Right" (PDF). Archived from the original (PDF) on 15 March 2012. Retrieved 29 May 2011.
  14. ^ Korenjak, A. "LR(k) 프로세서 구축을 위한 실용적인 방법", ACM 통신, Vol. 12, No. 11, 1969
  15. ^ DeRemer, F. LR(k)언어 실용번역자박사학위 논문, MIT, 1969.
  16. ^ DeRemer, F. "Simple LR(k) Grammars", ACM 통신, Vol. 14, No. 7, 1971.
  17. ^ a b Thomas J Pennello (1986). "Very fast LR parsing". ACM SIGPLAN Notices. Vol. 21, no. 7.
  18. ^ G.H. Roberts (1988). "Recursive ascent: an LR analog to recursive descent". ACM SIGPLAN Notices. 23 (8): 23–29. doi:10.1145/47907.47909. S2CID 12740771.
  19. ^ Leermakers, Augusteijn, Kruseman Aretz (1992). "A functional LR parser". Theoretical Computer Science. 104 (2): 313–323. doi:10.1016/0304-3975(92)90128-3.{{cite journal}}: CS1 maint: 여러 이름: 작성자 목록(링크)
  20. ^ A.A. Grau, "재귀 프로세스 및 ALGOL 번역", ACM의 통신, 4, No. 1, 페이지 10-15.1961년 1월
  21. ^ 에드거 T. Irons, "ALGOL 60용 구문 지향 컴파일러", ACM 통신, 4, No.1, 1961, 페이지 51-55.
  22. ^ "Stories of the B5000 and People Who Were There" (PDF).
  23. ^ Waychoff, Richard; Turner, Lloyd; Rosin, Robert F.; Pearson, Ralph W.; Oliphint, G. Clark; MacKenzie, F. Brad; MacDonald, Ray W.; MacDonald, Duncan N.; Lonergan, William D.; Kreuder, Norman L.; King, Paul D.; Hootman, Joseph T.; Hauck, Erwin A.; Hale, John E.; Galler, Bernard A.; Ford, James; Eppert, Ray R.; Dent, Benjamin A.; Dahm, David M.; Creech, Bobby A.; Collins, George A.; Berce, Henri; Barton, Robert S. (6 September 1985). "The Burroughs B5000 Conference, Charles Babbage Institute". hdl:11299/107105. {{cite journal}}:Cite 저널 요구 사항 journal=(도움말)
  24. ^ P. M. Lewis, R. E. Stearns, "Syntax directed transformation", 초점, 페이지 21-35, 제7회 스위칭 및 오토마타 이론 심포지엄(SWAT 1966), 1966
  25. ^ Lewis, P. and Stearns, R. "Syntax-Directed Transdition", ACM 저널, 제15권, 제3호, 1968.
  26. ^ "The PL/0 compiler/interpreter". Archived from the original on 8 December 2008. Retrieved 7 July 2011.
  27. ^ J. Earley, "A efficient context-free parsing algorithm", Communications of the Association for Computing Machine, 13:2:94-102, 1970.
  28. ^ Backus, J. W. (1959). "The syntax and semantics of the proposed international algebraic language of the Zurich ACM-GAMM Conference". Proceedings of the International Conference on Information Processing: 125–132.
  29. ^ Farrell, James A. (August 1995). "Extended Backus Naur Form". Compiler Basics. Retrieved 11 May 2011.
  30. ^ 도날드 E. 크누스, "백커스 노멀 폼 vs.Backus Naur Form", ACM 통신, 7(12):735–736, 1964.
  31. ^ "TMG Meta Compiler". reocities.com. Archived from the original on 4 March 2016. Retrieved 30 June 2011.
  32. ^ "Archived copy". Archived from the original on 21 September 2007. Retrieved 30 June 2011.{{cite web}}: CS1 maint: 제목으로 아카이브된 복사(링크)
  33. ^ McClure, R. M. (1965). Programming languages for non-numeric processing—1. acm.org. pp. 262–274. doi:10.1145/800197.806050. ISBN 9781450374958. S2CID 44606611.
  34. ^ R. M. McClure, TMG—A Syntax Directed Compiler Proc. 20th ACM National Conf. (1965), 페이지 262~274.
  35. ^ "Multics PL/I". multicians.org.
  36. ^ : CS1 maint: 타이틀(링크) Dennis M으로 아카이브된 복사본"Archived copy". Archived from the original on 10 January 2015. Retrieved 3 August 2011.{{cite web}}.리치.C 언어의 발전
  37. ^ McKeeman, William Marshall, Horning, James J. 및 Wortman, David B., A 컴파일러 제너레이터(1971), ISBN 978-0-13-155077-3.
  38. ^ 토론토 대학교 컴퓨터 공학부, "XPL 프로그래밍 언어"
  39. ^ 존슨, S.C., "Yacc – Yet Another Compiler", 컴퓨팅 사이언스 테크니컬 리포트 32, AT&T Bell Labs, 1975
  40. ^ Hamilton, Naomi. "The A-Z of Programming Languages: YACC". TechWorld.
  41. ^ Schorre, D. V. (1964). "META II a syntax-oriented compiler writing language". Proceedings of the 1964 19th ACM national conference. acm.org. pp. 41.301–41.3011. doi:10.1145/800257.808896. ISBN 9781450379182. S2CID 43144779.
  42. ^ "Comp.compilers: Re: History and evolution of compilers". iecc.com.
  43. ^ 프랜시스 E. 알렌, 마크 I에 "프로그램 최적화"Halpern과 Christopher J. Shaw 편집자, 자동 프로그래밍 연차 리뷰, 제5권, 239~307쪽.1969년 뉴욕 퍼가몬 프레스
  44. ^ Allen, Frances E.; Cocke, John (11 July 1972). Graph-Theoretic Constructs for Program Control Flow Analysis (RC 3923) (PDF). Yorktown Heights, NY: IBM Thomas J. Watson Research Center. Retrieved 6 May 2021.
  45. ^ 프랜시스 E.앨런 "흐름 분석 제어"ACM SIGPLAN 통지, 5(7):1~19, 1970년 7월
  46. ^ 프랜시스 E.앨런. "프로그램 최적화의 기초"인프로그래프 IFIP Congress 71, 385~390페이지.노스홀랜드, 1972년
  47. ^ 프랜시스 E.알렌과 존 코크."변혁을 최적화하는 카탈로그"편집자 R. Rustin, 컴파일러 설계 및 최적화, 1 ~ 30페이지.프렌티스 홀, 1971년
  48. ^ 프랜시스 E.앨런 "절차간 데이터 흐름 분석"인프로그래프IFIP Congress 74, 398~402페이지.노스홀랜드, 1974년
  49. ^ 프랜시스 E.앨런. "프로그램 데이터 관계를 결정하는 방법"안드레이 어쇼프와 발레리 A에서요Nepomniaschy, 편집자, Proc. 이론 프로그래밍에 관한 국제 심포지엄, 노보시비르스크, 1972년 8월, 컴퓨터 과학 강의 노트 제5권, 299~308쪽.Springer-Verlag, 1974년
  50. ^ 프랜시스 E.알렌과 존 코크."프로그램 데이터 흐름 분석 절차", ACM 통신, 19(3):137–147, 1976년 3월.
  51. ^ Sarkar, Vivek (1991). "PTRAN—the IBM Parallel Translation System". Parallel Functional Languages and Compilers. New York, NY: Association for Computing Machinery. pp. 309–391. doi:10.1145/107214.129260. ISBN 0201522438. Retrieved 6 May 2021.
  52. ^ 존 코코와 제이콥 T.Schwartz, Programming Languages 및 그 컴파일러.1970년 4월 뉴욕대학교 Courant 수학과학연구소
  53. ^ 맥키먼, W.M. "피홀 최적화"ACM 8, 7(1965년 7월), 443~444의 통신
  54. ^ "System/360 Instruction Timing Information" (PDF). IBM Systems Reference Library. May 1964. Retrieved 6 May 2021.
  55. ^ Evans, Michael (1982). "Software engineering for the Cobol environment". Communications of the ACM. 25 (12): 874–882. doi:10.1145/358728.358732. S2CID 17268690.
  56. ^ CACM 1973년 3월 페이지 169–179.
  57. ^ Cytron, Ron; Ferrante, Jeanne; Rosen, Barry K.; Wegman, Mark N.; Zadeck, F. Kenneth (1991). "Efficiently Computing Static Single Assignment Form and the Control Dependence Graph" (PDF). ACM Transactions on Programming Languages and Systems. 13 (4): 451–490. CiteSeerX 10.1.1.100.6361. doi:10.1145/115372.115320. S2CID 13243943.

추가 정보

외부 링크