C에서 추상 구문 트리 표현

C에서 추상 구문 트리 표현

저는 C에서 간단한 장난감 언어를 위한 컴파일러를 구현하고 있습니다.저는 AST의 개념적인 기능/구성에 대한 합리적인 배경을 가지고 있는 스캐너와 파서를 가지고 있습니다.제 질문은 C에서 AST를 표현하는 구체적인 방법과 관련된 것입니다.저는 온라인에서 다양한 텍스트/자료에서 세 가지 스타일을 자주 접했습니다.

노드 유형당 하나의 구조입니다.

모든 자식 구조의 첫 번째 필드인 기본 노드 "class"(구조)가 있습니다.기본 노드에는 노드 유형(상수, 이진 연산자, 할당 등)을 저장하는 열거형이 포함되어 있습니다.구조의 구성원은 구조당 하나의 집합이 있는 매크로 집합을 사용하여 액세스합니다.다음과 같습니다.

struct ast_node_base {
    enum {CONSTANT, ADD, SUB, ASSIGNMENT} class;
};

struct ast_node_constant {
    struct ast_node_base *base;
    int value;
};

struct ast_node_add {
    struct ast_node_base *base;
    struct ast_node_base *left;
    struct ast_node_base *right;
};

struct ast_node_assign {
    struct ast_node_base *base;
    struct ast_node_base *left;
    struct ast_node_base *right;
};

#define CLASS(node) ((ast_node_base*)node)->class;

#define ADD_LEFT(node) ((ast_node_add*)node)->left;
#define ADD_RIGHT(node) ((ast_node_add*)node)->right;

#define ASSIGN_LEFT(node) ((ast_node_assign*)node)->left;
#define ASSIGN_RIGHT(node) ((ast_node_assign*)node)->right;

노드 레이아웃당 하나의 구조물.

두 구조의 레이아웃이 같고 base-> class의 내용만 다르기 때문에 ast_node_add와 ast_node_assign 대신 ast_node_binary를 사용하여 두 구조를 모두 나타내는 것을 제외하면 이는 위 레이아웃과 거의 동일한 것으로 보입니다.장점은 매크로 쌍이 아닌 왼쪽과 오른쪽이 있는 모든 노드에 대해 더 균일한 매크로 집합(LEFT(노드))인 것처럼 보이지만 단점은 C 유형 검사가 유용하지 않을 것으로 보입니다(예를 들어 ast_node_add만 있어야 하는 경우 ast_node_assign을 탐지할 수 있는 방법은 없습니다).

서로 다른 유형의 노드 데이터를 보유할 수 있는 조합이 있는 하나의 구조 총계.

내가 말할 수 있는 것보다 이것에 대한 더 좋은 설명은 여기에서 찾을 수 있습니다.이전 예의 유형을 사용하면 다음과 같습니다.

struct ast_node {
  enum { CONSTANT, ADD, SUB, ASSIGNMENT } class;
  union { int                                 value;
          struct { struct ast_node* left;    
                   struct ast_node* right;  } op;
};

저는 세 번째 옵션을 가장 좋아하는 경향이 있는데, 그것은 재귀적 순회를 훨씬 쉽게 해주기 때문입니다. (많은 포인터 캐스팅이 조합에 유리하게 방지된다는 점에서) 하지만, 그것은 또한 C 타입 검사의 이점을 이용하지 않습니다.첫 번째 옵션은 노드의 멤버에 액세스하기 위해 캐스트되는 구조물에 대한 포인터에 의존한다는 점에서 가장 위험해 보이지만(같은 노드의 다른 멤버라도 액세스하기 위해 다른 경우(베이스 대 왼쪽)가 필요함), 이러한 캐스트는 형식 검사이므로 무트일 수 있습니다.제게 두 번째 선택지는 두 세계 중 최악으로 보이지만, 제가 뭔가를 놓치고 있는 것 같습니다.

이 세 가지 계획 중에서 가장 좋은 것은 무엇이며, 그 이유는 무엇입니까? 제가 아직 보지 못한 네 번째 옵션이 더 있을까요?모든 솔루션이 "모든 것에 맞는" 솔루션이 아니라고 가정합니다. 따라서 구현하는 언어가 정적으로 입력된 명령형 언어, 거의 C의 작은 부분 집합입니다.

세 번째 (조합) 배치에 대해 궁금한 점이 있습니다.value 필드만 사용할 경우 op가 기록될 가능성을 수용하기 위해 value 뒤에 빈 공간이 발생합니까?

당신은 이 중 어떤 것이든 만들 수 있습니다.

저는 모든 노드가 "동일한" 레이아웃을 가지고 있기 때문에 유니언 레이아웃을 선호합니다.

[왼쪽 또는 오른쪽으로 기울어진 목록 대신 "자녀 하위 목록" 옵션과 임의로 큰 동적 자녀 배열을 사용하는 것이 유용할 수 있습니다.]

이 문제가 컴파일러를 어렵게 만드는 문제가 아니라는 것을 알게 될 것입니다.오히려 심볼 테이블을 가지고 있고, 다양한 종류의 분석을 수행하고, 기계 수준 IR을 선택하고, 코드 생성기를 구축하고, 코드 최적화를 수행하고 있습니다.그러면 실제 사용자를 만나게 되고 실제로 무엇을 잘못했는지 알게 될 것입니다 :-}

다른 문제들에 접근할 수 있는 기회를 마련해 드릴 테니 제가 선택해서 다른 문제에 접근할 수 있도록 말이죠.

언급URL : https://stackoverflow.com/questions/21150454/representing-an-abstract-syntax-tree-in-c