추상 또는 구체적인 구문 트리를 사용하는 경우는 언제입니까?

Question

저는 컴파일러에 대한 연구를 해왔습니다. 렉서는 매우 직설적 인 것처럼 보입니다. "문장"을 가지고 단어 (또는 토큰)로 나눕니다. 올바른 문법을 보장하려면 파서가 필요합니다. 파서는 일반적으로 토큰을 가져 와서 루트 노드 (문장, 단락, 페이지 등의 단어)를 생성하는 트리를 만듭니다.

this question에서 파서가 AST를 작성하는 것처럼 보일 수 있습니다. AST에는 코드를 실행하는 데 필요한 것이 포함되어 있으므로 연산자 우선 순위가 AST에 내장되어 있으므로 괄호와 같은 요소는 필요하지 않습니다. AST는 아마도 모든 컴파일러가 필요합니다.

그러나 한 언어에서 다른 언어로 코드를 변환하는 것은 어떨까요? 구성된 언어 (문법) 또는 기존 문법을 사용하고 연산자 우선 순위 규칙이 다를 수도 있고 다를 수도있는 다른 언어로 변환 할 수 있습니까? CST에도 연산자 우선 순위가 "내장"되어 있습니까?

예를 들어 내가 언어를 구성하고이를 PHP 코드로 변환하려고한다고 가정 해 보겠습니다. 대부분의 언어에서 삼항 연산자는 오른쪽에서 왼쪽으로 연결됩니다. PHP는 left-to-right 연관성 (see more about this here)을 잘못 사용합니다. "내 언어"가 오른쪽에서 왼쪽으로 쓰길 원하지만 결과 PHP 코드는 괄호를 적용하여 PHP에서 올바른 결과를 얻을 수 있습니다 (link to Wikipedia, 결과는 "말"대신 "열차"가되어야 함).

그래서 언어 변환에 CST가 더 좋을까요? 일반적으로 운영자 우선 순위는 CST에 내장됩니까? 그 사이에 어떤 것이 있습니까? 두 대수를 간단한 대수 방정식과 비교하는 예제가 있습니까? 삼항 연산자를 보여주는 예제가 있습니까? 경우가 더 적절한 하나를 사용 :

는

내가 알아 내려고 노력하고있어입니다 (?. "트랜스" "프로그래밍 언어 번역"에 대한 올바른 용어 구글 검색 미디어 변환납니다입니다) 다른 것보다?

Answer 1

원본 언어의 모든 의미 론적 세부 사항을 모델링 한 AST 만 있으면됩니다. 정의에 따라 의미론을 올바르게 모델링하고 언어에 3 진수 연산자가 포함 된 경우 연산자가 적용되는 특정 순서 (예 : 괄호와 같은 미리 정의 된 모듈러스 재정의 결과)도 올바르게 모델링됩니다.

그래서 문제는 AST에 없습니다. 우선 순위가 다른 유사한 (3 진) 연산자를 사용하여 다른 언어로 생성 중입니다.

이것은 코드 생성에서 오래된 문제입니다. 대상의 연산자가 소스 연산자와 완전히 일치하지 않으므로 출력이 일대일이 될 수 없습니다. 귀하의 경우에는 괄호가있는 PHP 삼항 연산자를 생성하여 문제를 해결할 수 있어야 원래의 의미를 달성하는 순서를 제어 할 수 있으므로 큰 문제는 아닙니다.

일반적으로 원하는 결과를 얻는 코드 생성 시퀀스는 매우 복잡 할 수 있으며이를 수행하는 방법이 많이 있습니다. 그래서 컴파일러 책은 얇은 것이 아니라 두꺼운 책입니다. 당신은 암시 적으로 "AST 얻기, AST 걷기, 코드 침뱉기"에 정착 한 것처럼 보입니다. 이것은 거의 on-the-fly 코드 생성기입니다. 그리고 생성 된 코드가 특히 좋고 대상 언어가 원본 언어에 매우 가깝다면 신경 쓰지 않으면 적절하게 작동합니다.

코드 생성 문제가 더 복잡하면 일반적으로 AST를 사용하여 계산의 데이터 흐름 모델에 해당하는 것을 생성하고 결과를 생성하고 이전 연산자의 결과를 소비하는 연산자 변수 값과 상수를 가져 오는 "연산자"에서.그런 다음 데이터 흐름 표현을 탐색하여 코드를 생성합니다. 데이터 흐름 표현에서 연산자를 선택하고 대상 언어로 일치하는 코드 시퀀스를 찾아서 생성 한 다음 피연산자를 수집하는 방법에 대해 걱정할 수 있다는 이점이 있습니다. 더 나은 스키마는 생성 된 데이터 흐름 그래프에 데이터 흐름 하위 그래프 (동등한 복합 대상 언어 구문을 나타냄)를 일치시킵니다. 이것은 상당히 우수한 코드를 생성 할 수 있습니다. 종종 더 나은 코드를 생성하기 위해 원시 코드 생성 후에 타겟 언어 별 최적화를 적용 할 수 있습니다. 두 경우 모두 운영자 결과 관리에 대해 걱정해야합니다. 다음 대상 언어 운영자에게 직접 제공되거나 일종의 임시 저장 장치에 들어가야합니까 (기계 코드의 경우 다른 레지스터 또는 메모리 위치 일 수 있음). 이 모든 것을하는 것은 쉽지 않습니다. 다시 말하자면, 컴파일러 책이 얇지 않은 이유입니다.

이 아이디어의 변형은 소스에서 소스 프로그램으로의 변환입니다. 이 코드는 소스 코드의 구문을 "직접"대상 코드에 매핑합니다. 비록 구문 분석되지 않은 프로그래밍 언어 텍스트가 일치하기 어렵 기 때문에 대개 AST를 사용하여 장면 뒤에서 수행됩니다. 우리의 DMS Software Reengineering Toolkit은 이러한 종류의 시스템의 예입니다. 이러한 도구를 사용하면 소스 언어 (암시 적으로 구문 분석 트리와 일치) 및 대상 언어의 일치하는 패턴 (암시 적으로 대상 언어 AST를 생성)으로 패턴을 작성합니다. 위와 일치하는 데이터 흐름 그래프의 효과를 많이 제공하는 복잡한 원본 또는 대상 구성을 작성할 수 있습니다. 후 세대 최적화는 대상 코드를 대상 코드로 변환하는 더 많은 다시 쓰기 규칙으로 구성됩니다.

결론 : 귀하의 번역이 정말로 사소한 경우를 제외하고는 AST가 충분하지 않습니다. 이 SO 대답에 필요한 것에 대해 자세히 알아볼 수 있습니다. https://stackoverflow.com/a/3460977/120163

경고 : 큰 소리로 의견을 말합니다.

"트랜스 코더": 나는 "컴파일", "번역"또는 "소스 - 투 - 소스"컴파일러를 선호합니다. 저는 거의 40 년간 프로그램 분석 및 조작 도구를 개발해 왔습니다. 나는이 "질문"을 접할 때까지 "트랜스 코더"라는 용어를 들어 본 적이 없었습니다. Experience migrating legacy Cobol/PL1 to Java과 IMHO에 대한 응답으로 NACA라는 정말 끔찍한 코드 변환 체계가 있습니다. 나는이 용어가 힘을 얻고 있기 때문에 들었습니다. 나는 왜 우리가 완벽하게 적절한 용어를 만들었을 때 다른 용어를 만들어야하는지 알지 못합니다. 보통 이것은 신권을 창안하는 사람의 표징입니다. "사람들이 우리가하는 일을 정말로 이해하지 못하도록 반짝이는 새 용어를 만들어 봅시다." 정말 끔찍한 번역에 그 용어를 기쁘게 생각합니다.