트리-메타

TREE-META
트리-메타
원본 작성자도널드 앤드루스, 제프 룰리프슨
초기 릴리즈1968?

TREE-META(또는 Tree Meta, TREEMETA) 번역기 쓰기 시스템은 1960년대에 개발된 문맥 없는 언어를 위한 컴파일러 컴파일러 시스템이다.금속구조의 구문 분석은 나무를 심는 지시문이 내장된 강화된 백커스-나우르 형태와 유사하다.해제[1] 규칙에는 광범위한 트리 스캔 및 코드 생성 구조가 포함된다.

역사

TREE-META는 oN-Line 시스템 개발에 중요한 역할을 하였으며 Univac 1108, GE 645, SDS-940, ICL 1906A, PERQ, UCSD p-시스템 등 많은 시스템에 포팅되었다.[2][3]

예

이것은 ICL 1900 TREE-META 매뉴얼의 부록 6의 더 완전한(선언서, 조건 및 블록) 예에서 추출(그리고 테스트되지 않은) TREE-META 프로그램의 완전한 예다.[4]또한 이 문서는 부록 3의 TREE-META에 TREE-META의 정의를 포함하고 있다.이 프로그램은 단순한 인식자가 아니라 입력에 대한 어셈블리 언어를 출력한다.트리 패턴 매칭인 TREE-META의 핵심 특징 중 하나를 보여준다.LHS(예: GET 및 VAL)와 RHS(ADD 및 SUB)에 모두 사용된다.

% 이 설명은 %로 구분된 ALGOL 형식의 설명임

%============================================================================= %.META PROG % 주행 규칙을 정의하는 프로그램이 필요하다.% 이 PROG 규칙은 전체 프로그램의 드라이버. % PROG = $STMT; % $는 0 이상 운영자. % PROG(프로그램)는 0 이상 STMT(상태)로 정의된다. % STMT = .ID ':=' AEXP :STORE[2]*; % 할당 문을 원본에서 트리로 구문 분석.% ':='는 문자열 상수로서, :STORE는 STORE 노드를 생성하며, % [2]는 이를 두 개의 분기(예: STORE[ID,AEXP])로 정의한다.% % * triggers a unparse of the tree, Starting with the last created % % tree i.e. the STORE[ID,AEXP] which is emitted as output and      % % removed from the tree.                                           %  AEXP = FACTOR $('+' FACTOR :ADD[2] / '-' FACTOR :SUB[2]); % Here we have the recognizer for arithmetic '+' :ADD and '-' :SUB % % tree b우들딩다시 [2]는 2-branch ADD 또는 SUB 트리를 생성한다.% 전체 문장이 구문 분석될 때까지 언파싱이 지연됨.% ADD[팩터,팩터] 또는 SUB[팩터,팩터] % Factor = '-' PRIME :MINUSS[1] / PRIME ; PRIME = .ID / .NUM / '(' AEXP ')' ?3? ; % ?3? is a hint for error messages.                                %      % ===================== OUTPUT UNPARSE RULES ===================== %  STORE[-,-] => GET[*2] 'STORE ' *1 ; % *1 is the left tree branch.*2는 오른쪽 % % GET[*2]에서 로드할 코드를 생성한다. % 'STORE' 문자열이 % 출력된 후 왼쪽 분기 *1 % 기호 %%*2 무엇이든 GET[*2]에서 로드한다.ID] => 'LOAD' *1 / []Num] => LOADI ' *1 / [MINUSS[]NUM] => 'LOADN ' *1:*1 / [-] => *1 ; % 여기 입니다.ID 또는 .NUM은 간단히 로드된다.를 포함하는 MINUS 노드 %.NUM은 이것을 사용할 것이며, *1:*1이라는 표기법은 첫 번째 가지(a)의 %를 의미한다."NUM의 첫번째 지점의(MINUSS).%%또 다른 사람을 위해 전달 될 것이다 노드 인식%%unparse 규칙 deconstruct 나무 outputing 코드입니다.%ADD[-,-]=>, SIMP[*2]GET[*1]'ADD의 VAL[*2]/SIMP[*1]GET[*2]'ADD의 VAL[*1]/GET[*1]'STORE T+의<>OUT[A], A;-A+1>/.     얻다T+의<>'ADD[*2];A;-A-1, OUT[A]>;%Chevrons<>,%%로 예를 들어 산술 연산을 나타낸다를 만들고 A기본 주소 T.%SUB[-,-]=>, SIMP[*2]GET[*1]'SUB의 VAL[*2]/SIMP[*1]GET[*2]'NEGATE'%'ADD의 VAL[*1]/GET[*2]'STORE T+의<>OUT[A], A;-A에 상대적인 오프셋.+1>/GET[*1] 'SUB T+' < A<-A-1; OUT[A] >; % 구문 분석 규칙의 A% 문자는 새로운 줄을 나타낸다. % SIMP[]ID] => .비어 있음 / [.NUM] => .비어 있음 / [MINUSS[.NUM] => .비어 있음; VAL[.ID] => ' *1 / []NUM] => 'I ' *1 / [MINUSS[]NUM] => N ' *1:*1; MINUSS[-] => GET[*1] 'NEGATE' ; .끝

참고 항목

참조

  1. ^ 도날드 1세앤드류스, J. F. 룰리프슨(1967년).트리 메타(작업 초안): 캘리포니아 멘로 파크에 있는 스탠포드 연구소의 SDS 940용 메타 컴파일러.엥겔바트 컬렉션, 스탠포드 대학교 아카이브, M 638, 박스 16, 폴더 3.
  2. ^ 보울스, K. L. 1978.마이크로 및 미니 컴퓨터를 위한 A(거의) 기계 독립 소프트웨어 시스템.SIGMINI Newsl, 4(1), 3–7. doi:10.1145/1041256.1041257
  3. ^ Bowles, K. L. (May 1978). "UCSD Pascal: A (nearly) machine independent software system for micro and mini computers". Byte. Vol. 3, no. 5. pp. 46, 170–173 – via Internet Archive.{{cite magazine}}: CS1 maint: 날짜 및 연도(링크)
  4. ^ 홉굿, F. R. A. 1974년, "TREE-META 설명서", 아틀라스 컴퓨터 연구소.

외부 링크