추상 구문 트리는 정확히 어떻게 생성됩니까?

간단한 대답은 스택을 사용한다는 것입니다. 이 는 좋은 예이지만 AST에 적용하겠습니다.

참고로 Edsger Dijkstra의

Shunting-Yard 알고리즘 .

이 경우 연산자 스택과 표현식 스택을 사용합니다. 숫자는 대부분의 언어에서 표현식으로 간주되므로 표현식 스택을 사용하여 저장합니다.

 class ExprNode: char c ExprNode operand1 ExprNode operand2 ExprNode(char num): c = num operand1 = operand2 = nil Expr(char op, ExprNode e1, ExprNode e2): c = op operand1 = e1 operand2 = e2 # Parser ExprNode parse(string input): char c while (c = input.getNextChar()): if (c == "("): operatorStack.push(c) else if (c.isDigit()): exprStack.push(ExprNode(c)) else if (c.isOperator()): while(operatorStack.top().precedence >= c.precedence): operator = operatorStack.pop() # Careful! The second operand was pushed last. e2 = exprStack.pop() e1 = exprStack.pop() exprStack.push(ExprNode(operator, e1, e2)) operatorStack.push(c) else if (c == ")"): while (operatorStack.top() != "("): operator = operatorStack.pop() # Careful! The second operand was pushed last. e2 = exprStack.pop() e1 = exprStack.pop() exprStack.push(ExprNode(operator, e1, e2)) # Pop the "(" off the operator stack. operatorStack.pop() else: error() return nil # There should only be one item on exprStack. # It"s the root node, so we return it. return exprStack.pop()  

(내 코드에 대해 친절하게 설명해주세요. 강력하지 않다는 것을 알고 있습니다. 단지 의사 코드 여야합니다.)

어쨌든 코드에서 알 수 있듯이 임의의 표현식은 다른 표현식에 대한 피연산자가 될 수 있습니다. 다음 입력이있는 경우 :

5 * 3 + (4 + 2 % 2 * 8) 

내가 작성한 코드가이 AST를 생성합니다.

 + / \ / \ * + / \ / \ 5 3 4 * / \ % 8 / \ 2 2 

그런 다음 해당 AST에 대한 코드를 생성하려면 주문 후 트리 탐색 을 수행합니다. 리프 노드 (숫자 포함)를 방문하면 컴파일러가 피연산자 값을 알아야하므로 상수를 생성합니다. 연산자를 사용하여 노드를 방문하면 연산자에서 적절한 명령어를 생성합니다 (예 : “+”). 연산자는 “추가”지침을 제공합니다.

댓글

• r 연산자는 오른쪽에서 왼쪽이 아닌 왼쪽에서 오른쪽으로 연결됩니다.
• @Simon, 오른쪽에서 왼쪽으로 쓰는 연산자에 대한 기능을 추가하는 것은 매우 간단합니다. 가장 간단한 방법은 조회 테이블을 추가하는 것입니다. 연산자가 오른쪽에서 왼쪽이면 피연산자의 순서를 반대로하면됩니다.
• @Simon 둘 다 지원하려면 ‘ shunting yard 알고리즘 을 전체적으로 검색하는 것이 좋습니다. 알고리즘이 진행됨에 따라 ‘ 절대 크래커입니다.

AST가 일반적으로 테스트에서 표시되는 방식 (리프 노드에 숫자 / 변수가있는 트리 및 내부 노드에 기호가있는 트리)과 실제로 구현되는 방식 간에는 상당한 차이가 있습니다.

일반적인 AST (OO 언어로) 구현은 다형성을 많이 사용합니다. AST의 노드는 일반적으로 다양한 클래스로 구현되며 모두 공통 ASTNode 클래스에서 파생됩니다. 처리중인 언어의 각 구문 구조에 대해 ConstantNode ( 또는 42), VariableNode (변수 이름 용), AssignmentNode (할당 연산 용), ExpressionNode (일반 표현 식용) 등
각각의 특정 노드 유형은 해당 노드에 자식이 있는지 여부, 그 수 및 가능한 유형을 지정합니다. ConstantNode에는 일반적으로 자식이없고, AssignmentNode에는 2 개, ExpressionBlockNode에는 자식 수에 제한이 없습니다.

AST는 방금 파싱 한 구문을 알고있는 파서에 의해 빌드되므로 올바른 종류의 AST 노드를 구성 할 수 있습니다.

순회 할 때 AST, 노드의 다형성이 실제로 작용합니다. 기본 ASTNode는 노드에서 수행 할 수있는 작업을 정의하고 각 특정 노드 유형은 해당 특정 언어 구조에 대한 특정 방식으로 이러한 작업을 구현합니다.

소스 텍스트에서 AST를 빌드하는 것은 ” 간단히 ” 파싱 . 정확히 수행되는 방법은 구문 분석 된 형식 언어와 구현에 따라 다릅니다. menhir (Ocaml 용) , GNU bison with flex 또는 ANTLR 등. 종종 수행됩니다. ” 수동으로 ” 일부 재귀 하강 파서 를 코딩하여 (이 답변 이 이유를 설명합니다). 구문 분석의 컨텍스트 측면은 종종 다른 곳에서 수행됩니다 (기호 테이블, 속성, ….).

그러나 실제로 AST는 사용자가 생각하는 것보다 훨씬 더 복잡합니다. 예를 들어 GCC 와 같은 컴파일러에서 AST는 소스 위치 정보와 일부 입력 정보를 유지합니다. GCC의 일반 나무 및 GIMPLE 에 대해 읽고 gcc / tree.def . C 또는 C ++ 또는 Fortran 또는 Ada를 처리하려면 고유 한 GCC 플러그인 을 작성하는 것이 좋습니다. BTW, 구식 GCC MELT (& 구현 설계) 내부도 살펴보십시오. 질문. Dragon 책 을 읽어보세요. 참조를 위해 이 초안 보고서, RefPerSys 프로젝트 및 많은 소스 코드를 참조하세요. 기타 오픈 소스 프로젝트 ( Ocaml 또는 또는 SBCL 또는 Jq ) ffb008b8ea “>

이 질문이 4 년 이상 된 것을 알고 있지만 더 자세한 답변을 추가해야한다고 생각합니다.

추상 구문 트리는 다른 트리와 다르지 않게 만들어집니다. 이 경우 더 진실한 진술은 구문 트리 노드가 필요에 따라 가변적 인 양의 노드를 갖는다는 것입니다.

예는 1 + 2와 같은 이진 표현식입니다. 숫자에 대한 데이터를 보유하는 오른쪽 및 왼쪽 노드를 보유하는 단일 루트 노드를 만듭니다.C 언어에서는 다음과 같이 표시됩니다.

struct ASTNode; union SyntaxNode { int64_t llVal; uint64_t ullVal; struct { struct ASTNode *left, *right; } BinaryExpr; }; enum SyntaxNodeType { AST_IntVal, AST_Add, AST_Sub, AST_Mul, AST_Div, AST_Mod, }; struct ASTNode { union SyntaxNode *Data; enum SyntaxNodeType Type; }; 

귀하의 질문은 횡단 방법이었습니다.이 경우 횡단은 방문 노드 . 각 노드를 방문하려면 각 노드 유형을 사용하여 각 구문 노드의 데이터를 평가하는 방법을 결정해야합니다.

다음은 각 노드의 내용을 간단히 인쇄하는 C의 또 다른 예입니다.

void AST_PrintNode(const ASTNode *node) { if( !node ) return; char *opername = NULL; switch( node->Type ) { case AST_IntVal: printf("AST Integer Literal - %lli\n", node->Data->llVal); break; case AST_Add: if( !opername ) opername = "+"; case AST_Sub: if( !opername ) opername = "-"; case AST_Mul: if( !opername ) opername = "*"; case AST_Div: if( !opername ) opername = "/"; case AST_Mod: if( !opername ) opername = "%"; printf("AST Binary Expr - Oper: \"%s\" Left:\"%p\" | Right:\"%p\"\n", opername, node->Data->BinaryExpr.left, node->Data->BinaryExpr.right); AST_PrintNode(node->Data->BinaryExpr.left); // NOTE: Recursively Visit each node. AST_PrintNode(node->Data->BinaryExpr.right); break; } } 

함수가 재귀 적으로 방문하는 방법을 확인합니다. 각 노드는 우리가 다루는 노드 유형에 따라 다릅니다.

더 복잡한 예제 인 if 문 구성을 추가하겠습니다. 선택 사항 인 else 절도 가질 수 있습니다. 원래 노드 구조에 if-else 문을 추가해 보겠습니다. if 문 자체도 if 문을 가질 수 있으므로 노드 시스템 내에서 일종의 재귀가 발생할 수 있습니다. Else 문은 선택 사항이므로 elsestmt 필드는 재귀 방문자 함수가 무시할 수있는 NULL이 될 수 있습니다.

struct ASTNode; union SyntaxNode { int64_t llVal; uint64_t ullVal; struct { struct ASTNode *left, *right; } BinaryExpr; struct { struct ASTNode *expr, *stmt, *elsestmt; } IfStmt; }; enum SyntaxNodeType { AST_IntVal, AST_Add, AST_Sub, AST_Mul, AST_Div, AST_Mod, AST_IfStmt, AST_ElseStmt, AST_Stmt }; struct ASTNode { union SyntaxNode *Data; enum SyntaxNodeType Type; }; 

back AST_PrintNode라는 노드 방문자 인쇄 함수에서 다음 C 코드를 추가하여 if 문 AST 구문을 수용 할 수 있습니다.

case AST_IfStmt: puts("AST If Statement\n"); AST_PrintNode(node->Data->IfStmt.expr); AST_PrintNode(node->Data->IfStmt.stmt); AST_PrintNode(node->Data->IfStmt.elsestmt); break; 

매우 간단합니다! 결론적으로 구문 트리는 트리와 데이터 자체의 태그 결합 트리에 불과합니다!