메타II
META II |
META II는 컴파일러를 쓰기 위한 도메인 고유의 프로그래밍 언어입니다.1963~1964년 UCLA의 Dewey Val Schorre에 의해 만들어졌습니다.META II는 쇼레가 말하는 구문 방정식을 사용합니다.동작은 다음과 같이 간단하게 설명됩니다.
각 구문 방정식은 입력 문자열을 특정 구문 구조에 대해 테스트하는 재귀 서브루틴으로 변환되며,[1] 검색된 경우 삭제됩니다.
Meta II 프로그램은 해석된 바이트 코드 언어로 컴파일됩니다.기능을 설명하는 VALGOL 및 SMALGOL 컴파일러는 META II [1][2]언어로 작성되었으며, VALGOL은 META II를 설명하기 위해 설계된 단순한 대수적 언어입니다. SMALGOL은 ALGOL 60의 상당히 큰 서브셋이었습니다.
표기법
META II는 META II의 수동 컴파일 버전인 META [3]I에서 처음 작성되었습니다.META I이 META II의 완전한 구현인지 아니면 완전한 META II 컴파일러를 컴파일하기 위해 필요한 META II 언어의 서브셋인지에 대해서는 역사가 불분명하다.
문서에서 META II는 BNF와 유사한 것으로 기술되어 있으며, 오늘날에는 생산 문법으로 설명되고 있습니다.META II는 분석적인 문법이다.TREE-META 문서에서는 이러한 언어를 환원 문법으로 기술했습니다.
예를 들어 BNF에서는 산술식을 다음과 같이 정의할 수 있습니다.
<expr> := <term> <expr> <addop> <term>BNF 규칙은 오늘날 유효한 언어 구성만 구성하기 위해 구성 부품을 조립하는 방법을 설명하는 생산 규칙입니다.파서는 언어구조를 분해하는 것과 정반대이다.META II는 출력 디렉티브를 포함하는 스택 기반 함수 파서 프로그래밍 언어입니다.META II에서는 다음 식에 따라 시험 순서를 정한다.META II는 다른 프로그래밍 언어와 마찬가지로 왼쪽 재귀를 시도하면 스택이 오버플로우됩니다.META II는 $(0 이상) 시퀀스 연산자를 사용합니다.META II에서 기술된 expr 해석식은 왼쪽에서 오른쪽으로 평가되는 조건식입니다.
expr= 용어 $( '+' 용어.나가.('더하다') / '-' 용어.나가.('후보선수')); 위의 expr 방정식은 '='의 오른쪽에 있는 식에 의해 정의됩니다.'='에서 왼쪽에서 오른쪽으로 평가할 때 가장 먼저 테스트해야 할 항목은 용어입니다.term이 returns하면 failure expr이 실패합니다.성공적인 항이 인식되면 무한 $0 또는 그 이상의 루프로 들어갑니다. 만약 이것이 실패하면 대체 "-"가 시도되고 마지막으로 "-"가 인식되지 않으면 루프는 종료되며 expr이 단일 항을 인식한 성공으로 반환됩니다.'+' 또는 '-'가 성공하면 용어를 호출합니다.그리고 성공하면 루프가 반복됩니다.expr 방정식은 중첩된 그룹화를 사용하여 다음과 같이 나타낼 수도 있습니다.
expr= 용어$(('+' / '-') 용어); 예를 단순화하기 위해 코드 생성 요소를 생략했습니다.초기 컴퓨터의 제한된 문자 집합 때문에 캐릭터는/대체 또는 연산자로 사용되었습니다.그$, loop 연산자는 다음 중 하나 이상을 일치시키기 위해 사용됩니다.
expr= 용어$( '+' 용어.나가.('더하다') / '-' 용어.나가.('후보선수') ); 위의 내용은 영어로 표현할 수 있습니다.expr은 0 이상의 용어(+항 또는 마이너스항) 뒤에 이어지는 용어입니다.쇼레는 이것을 효율성에 도움이 되는 것으로 설명하지만, 순진한 재귀 강하 컴파일러와는 달리 산술 연산의 연관성도 정확함을 보장합니다.
expr= 용어$('+' 용어.나가.('더하다') / '-' 용어.나가.('후보선수') ); 용어= 인자$( '*' 인자.나가.('MPY') / '/' 인자.나가.('DIV') ); 인자= ( .아이디 / .번호 / '(' expr')') ( '^' 인자.나가.('EXP') / .빈); 루프 또는 오른쪽("꼬리") 재귀로 시퀀스를 표현하는 기능을 사용하여 평가 순서를 제어할 수 있습니다.
구문 규칙은 선언적인 것처럼 보이지만 실제로는 의미 사양에 따라 필수적입니다.
작동
META II는 스택머신의 어셈블리 코드를 출력합니다.이것을 평가하는 것은 RPN 계산기를 사용하는 것과 같습니다.
expr= 용어 $('+' 용어.나가.('더하다') /'-' 용어.나가.('후보선수')); 용어= 인자 $('*' 인자.나가.('MPY') / '/' 인자.나가.('DIV')); 인자= (.아이디.나가.('LD' *) / .숫자.나가.('LDL' *) / '(' expr')') ( '^' 인자.나가.('XPN'/.빈); 상기의 경우.아이디와NUM은 내장된 토큰 인식자입니다.* 입니다.OUT 코드 생성은 마지막으로 인식된 토큰을 참조합니다.에서 번호를 인식하는 경우.NUM .OUT ('LDL' *)는 숫자 뒤에 로드 리터럴 명령을 출력합니다.표현:
- (3*a^2+5)/b
다음 항목이 생성됩니다.
LDL 3 LD a LDL 2 XPN MPY LDL 5 더하다 LD b DIV META II는 가상 시스템의 초기 인스턴스 중 하나에 대한 시스템 코드로 컴파일되므로 메타 컴파일러의 [notes 1]첫 번째 문서 버전입니다.
Meta II의 부트스트래핑 등 뛰어난 예가 다수 포함되어 있습니다(이 모든 것은 8K(6비트바이트) 1401!)."—Alan Kay
원본 논문은 자유롭게 구할 수 없지만, 닥터 돕스 저널(1980년 4월)에 전재되었다.변환된 소스 코드는 다양한 시기에 사용할 수 있게 되었습니다(CP/M 사용자 그룹에 의해 사용 가능).이 문서에는 Meta II에 대한 설명이 기재되어 있습니다.원칙적으로 수동으로 처리하여 가상 머신의 opcode에서 해석 가능한 프로그램을 생성할 수 있습니다.이것이 실행되어 동일한 출력이 생성되었다면 실장은 올바른 것입니다.
META II는 기본적으로 개념 증명입니다.일할 수 있는 기반입니다.
META II는 표준 언어가 아니라 사용자가 자신의 META "언어"[1]를 개발할 수 있는 출발점으로 제시됩니다.
많은 META "언어"가 뒤따랐다.Shorre는 System Development Corporation에서 근무했으며, CWIC(Compiler for Writing and Implementing Compiler) 프로젝트의 멤버였습니다.META II를 기반으로 구축된 CWIC의 SYNATS 언어는 백트랙 대체 연산자 양수 및 음수 예측 연산자 및 프로그래밍된 토큰 방정식을 추가합니다.그.OUT그리고..LABEL제거된 작업 및 스택 변환 작업:<node>그리고.!<number>추가된.LISP 2에 기반한 GENTERRER 언어는 구문 해석 언어에 의해 생성된 트리를 처리했습니다.코드를 생성하기 위해 생성기 함수에 대한 호출이 구문 방정식으로 이루어졌습니다.이 언어들은 L.A. 회원들에 의해 개발되었다.구문 다이렉트 컴파일러의 ACM SIGPLAN 서브그룹쇼레가 META II 언어에 대해 어떻게 생각했는지 주목할 만하다.
대문자로 META를 사용하는 META "언어"라는 용어는 이렇게 개발된 [1]컴파일러 쓰기 언어를 나타내기 위해 사용됩니다.
쇼레는 META II를 다른 META "언어"가 개발될 수 있는 기반으로서 설명한다.
「 」를 참조해 주세요.
메모들
- ^ META II 문서에서 전달 시에만 언급된 META I은 무시합니다.
레퍼런스
- ^ a b c d META II 구문 지향 컴파일러 언어 쓰기 (Dewey Val Schorre UCLA Computing Facility 1964)
- ^ Dewey, Val Schorre (1963). "A Syntax - Directed SMALGOL for the 1401,". ACM Natl. Conf., Denver, Colo.
- ^ Dewey, Val Schorre (1963). META II: a syntax-oriented compiler writing language (PDF). UCLA: UCLA Computing Facility.
