구문 지향 번역의 의미는 무엇입니까?

Question

"구문 지향 변환"이 의미하는 바는 누구나 간단히 설명 할 수 있습니까? 내가 드래곤 도서에서 주제를 읽기 시작했지만 이해할 수 없었다. Wiki article도 도움이되지 않았습니다.

Answer 1

'구문 직접 변환'은 구문 인식기 (파서)를 사용하여 전체 컴파일 (번역) 프로세스를 구동하는 것을 의미합니다.

개념적으로 프로그램을 컴파일 (소스 코드에서 기계어로 변환)하는 프로세스는 구문 분석 트리를 생성하는 파서로 시작한 다음 트리 또는 그래프 변환 시퀀스를 통해 해당 구문 분석 트리를 변환합니다. 는 크게 독립적이므로 최종 단순화 된 트리 또는 그래프가 기계 코드를 생성하기 위해 통과합니다.

이보기는 이론상 좋지만, 직접 구현하려고하면 전체 트리 또는 그래프의 복사본을 2 개 이상 보유 할만큼 충분한 메모리가 필요하다는 단점이 있습니다. 드래곤 북이 쓰여졌을 때 (그리고이 이론이 많이 파헤쳐 졌을 때), 컴퓨터 기억 장치는 킬로바이트로 측정되었고, 64K는 많이 보였습니다. 그래서 큰 프로그램을 컴파일하는 것은 까다로울 수 있습니다.

구문 지정 변환을 사용하면 구문 분석기가 구문 분석 트리를 인식하는 순서대로 모든 그래프 변환을 구성 할 수 있습니다. 파서 트리 전체를 생성하는 대신 파서는 비트를 거의 생성하지 않고 컴파일러의 다음 단계로 전달하여 궁극적으로 작은 조각의 기계어를 생성 한 다음 파싱 프로세스를 계속 진행하여 다음 번 구문 분석을 작성합니다 나무. 파스 트리 (또는 후속 그래프)는 언제든지 소량 만 존재하기 때문에 훨씬 적은 메모리가 필요합니다. 구문 인식기는이 모든 것을 제어하는 ​​마스터 시퀀서이므로 (일이 일어나는 순서를 결정),이를 구문 직접 변환이라고합니다.

메모리 사용을 유지하는 효과적인 방법이기 때문에 사람들은 더 쉽게 할 수있는 언어를 재 설계했습니다. 실제로 구문 분석을 통해 전체 프로세스를 수행 할 수있는 "단일 패스"컴파일러가 이상적입니다. 한 번에 코드 생성을 기계화 할 수 있습니다.

요즘 메모리는 그다지 프리미엄이 아니므로 모든 것을 한 번에 강제해야한다는 부담이 적습니다. 대신 프론트 엔드 용 구문 직접 변환 (Syntax Direct Translation)을 사용하고, 구문 분석, 형식 검사 및 기타 의미 검사, 파서에서 간단한 변환을 비롯하여 내부 양식 (세 가지 주소 코드, 나무 또는 일종의 대그) 그리고 독립적 인 최적화와 백엔드 패스를가집니다. 이 경우에도 컴파일러는 입력 (예 : 전체 기능 또는 모듈)의 큰 부분을 조작하고 모든 단계를 계속 진행하기 전에 모든 통과 과정을 거치기 위해 구성 될 수 있으므로이 나중에 패스가 적어도 부분적으로 구문을 지시한다고 주장 할 수 있습니다. 다음 입력 부분

yacc와 같은 도구는 구문 직접 변환이라는 개념을 바탕으로 설계되었습니다.이 도구는 제작 (파스 트리의 조각)이 인식되면서 코드 조각 (도구 구문에서 '동작')을 직접 실행하는 구문 인식기를 생성합니다 실제 '나무'를 만들지 않고. 이러한 동작은 나중에 컴파일러에서 논리적으로 전달되는 것을 직접 호출 할 수 있으며 구문 분석을 계속하기 위해 돌아갑니다. 이 모든 것을 구동하는 명령형 루프는 구문 분석기의 토큰 읽기 상태 머신입니다.

Answer 2

드래곤 북 앞에는 구문 지향 컴파일러 컴파일러가있었습니다. META II 및 TREE META는 1960 년대에 개발되었습니다. 메타 언어 컴파일러 (메타 컴파일러)입니다. 그것들은 실제로 실패의 성공을 리턴하는 함수 인 분석 규칙 세트를 취하는 하향식 파서입니다. 각 규칙은 논리 구문 분석 식입니다. 최상위 주행 규칙은 소스 파일 내용을 정의했습니다. 예를 들어, 프로그래밍 언어는 일련의 선언으로 구성 될 수 있습니다.따라서 최고 주행 규칙은 다음과 같이 보입니다.

program = $declarations; 

$는 0 개 이상을 의미합니다. $ declarations는 컴파일되는 소스가 몇 가지 선언으로 구성되도록 지정합니다. 그런 다음 선언은 선언의 유형을 정의합니다. 외부 연결 선언, 데이터 선언, 함수 또는 프로 시저 선언이 필요할 수 있습니다.

declarations = linkage_decl | data_decl | code_decl; 

선언 유형이 각각 별도의 규칙입니다. 구문은 코드 생성이 발생할 때 제어합니다. 메타 컴파일러는 구문 규칙에서 의미 론적 처리를 제어했습니다. 처음에는 규칙에 따라 자아입니다. 나중에 그들은 소스를 나무와 목록 구조로 변형시키고 출력을 생산하는 의미 규칙에 전달했습니다. 예를 들어 산술 할당 문이 변형되어 의미 규칙에 전달 될 수 있습니다.

asign = id '=' expr ';' :ASSIGN!2 arith_gen(*1); 
expr = term $(('+':ADD | '-':SUB) term !2); 
term = factor $(('*':MPY | '//' :REM | '/':DIV) factor!2); 
factor = id | number | '(' expr ')'; 

이들 언어는 bnf와 유사하다고합니다. 하지만 그렇지 않습니다. 이들은 분석적 하향식 구문 분석기입니다. 그런 다음 arith_gen은 임베디드 트리 ':'및 '!'에 의해 생성 된 트리 구조를 인식하도록 코딩됩니다. 연산자. 사용 된 트리 표기법은 '['와 ']'로 묶고 ','로 구분 된 나뭇 가지가 뒤 따르는 노드입니다. 위의 분석 구문은 표현식의 수학적 계층 구조를 정의하는 것입니다. 곱셈, 나눗셈 및 나머지가 더하기 또는 빼기 전에 수행됩니다. 기능 목록 표현식으로 변환 된 산술 할당 표현식입니다. 구문은 입력 변환을 기능 표기법으로 안내합니다. ASSIGN [X, ADD [A, DIV [SUB [B, C]]] D]

이 된 metacompilers 정확히 현재의 용어를 일치하지 않는 :

x = a + (b - c)/d; 

는 함수 표기 트리를 생성합니다.

참조 위키 metacompiler META II 및 TREE META 주제와 좀 더 정보