구문 분석 트리와 추상 구문 트리의 차이점은 무엇입니까?

Question

컴파일러 디자인 서적에서이 두 용어를 찾았습니다. 각각의 의미와 그 차이점을 알고 싶습니다.

인터넷에서 검색 한 결과 파스 트리가 구체적인 구문 트리 (CST)라고도합니다.

Answer 1

이것은 Terrence Parr의 Expression Evaluator 문법을 기반으로합니다. 이 예

문법 :

grammar Expr002; 

options 
{ 
    output=AST; 
    ASTLabelType=CommonTree; // type of $stat.tree ref etc... 
} 

prog : (stat)+ ; 

stat : expr NEWLINE  -> expr 
     | ID '=' expr NEWLINE -> ^('=' ID expr) 
     | NEWLINE    -> 
     ; 

expr : multExpr (('+'^ | '-'^) multExpr)* 
     ; 

multExpr 
     : atom ('*'^ atom)* 
     ; 

atom : INT 
     | ID 
     | '('! expr ')'! 
     ; 

ID  : ('a'..'z' | 'A'..'Z')+ ; 
INT  : '0'..'9'+ ; 
NEWLINE : '\r'? '\n' ; 
WS  : (' ' | '\t')+ { skip(); } ; 

입력

x=1 
y=2 
3*(x+y) 

파스 트리

구문 분석 트리 입력의 구체적인 표현이다. 구문 분석 트리에는 입력 정보가 ​​모두 유지됩니다. 빈 상자는 공백, 즉 줄의 끝을 나타냅니다.

AST

AST 입력의 추상적 인 표현이다. 연결은 트리 구조에서 파생 될 수 있으므로 괄호는 AST에 없습니다. 설명을 통해 자세한 내용

편집

경찰국에 의해 Compilers and Compiler Generators 참조 Terry pg. 23. 저자 인 home page에 소스 코드와 같은 항목이 더 있습니다.

Answer 2

AST는 일부 소스 코드 (중괄호, 키워드, 괄호 등)을 분석하는 데 필요한 모든 구문 요소를 포함 할 필요가 없습니다, 개념적으로 소스 코드를 설명합니다.

파스 트리는 소스 코드를보다 자세히 나타냅니다. 대서양 표준시에서

IF 문에 대한 노드가 포함 할 수 단지 세 어린이 :

• 조건
• 하면 케이스
• 는 C와 같은 언어 구문 분석에 대한 경우 다른

트리는 'if'키워드, 괄호, 중괄호에 대한 노드를 포함해야합니다.

Answer 3

여기 컴파일러 건설의 맥락에서 구문 분석 나무 (콘크리트 구문 트리, CST)과와 추상 구문 나무 (하는 AST)에 대한 설명,입니다. 그것들은 비슷한 데이터 구조이지만, 다르게 구성되어 다른 작업에 사용됩니다.

구문 분석 나무

구문 분석 나무는 일반적으로 (문자 단지 순서에 반대되는 의미있는 단위로 볼 수있다 일련의 토큰으로 소스 코드를 전환) 어휘 분석 후 다음 단계로 생성된다 .

이들은 터미널의 입력 문자열 (소스 코드 토큰)이 해당 언어의 문법에 의해 어떻게 생성되었는지를 보여주는 트리 같은 데이터 구조입니다. 구문 분석 트리의 루트는 문법의 가장 일반적인 기호 인 시작 기호 (예 : 문)이며 내부 노드는 시작 기호가 확장되는 (시작 기호 자체를 포함 할 수 있음) 비 터미널 기호를 나타냅니다. 표현식은, 문은, 은, 은입니다. 잎은 문법의 말단, 언어/입력 문자열의 식별자, 키워드 및 상수로 나타나는 실제 기호입니다. 및 및 구문 오류 보고서 파서 코드에 임베드 될 수있다 -위한 , 9, 경우 등

컴파일러 분석하는 동안은 구문의 정확성을 보장하기 위해 여러 검사를 수행한다.

중위어 표현식을 후위어 식으로 변환하는 것과 같은 간단한 작업을 위해 구문 지향 정의 또는 번역 스키마를 통해 구문 지향 변환에 사용할 수 있습니다.

추상 구문 트리

: 여기

는 표현 9 - 5 + 2에 대한 파스 트리의 그래픽 표현 (트리의 단자와 표현 문자열의 실제 문자의 위치를주의)이다

AST는 일부 코드의 구문 구조를 나타냅니다. 표현식, 흐름 제어문 등과 같은 프로그래밍 구조의 트리는 연산자 (내부 노드)와 피연산자 (잎)로 그룹화됩니다. 예를 들어 표현식 i + 9의 구문 트리에는 + 루트가 있고 변수 i은 운영자의 왼쪽 하위 노드로, 숫자 9은 올바른 하위 노드로 사용됩니다.

차이점은 비대칭과 터미널은 역할을하지 않는다는 것입니다. AST는 문법과 문자열 생성을 다루지 않지만 프로그래밍 구조를 다루지 않으므로 구문과 구문 간의 관계를 나타냅니다. 문법에 의해 생성됩니다.

연산자 자체는 주어진 언어로 프로그래밍 구성 요소이며 실제 계산 연산자 (예 : +) 일 필요는 없습니다. for 루프도 이와 같이 처리됩니다. 예를 들어, for [ expr, expr, expr, stmnt ] (인라인으로 표시)과 같은 구문 트리를 가질 수 있습니다. 여기에서 for은 연산자이고 대괄호 안의 요소는 자식 (C의 for 구문)을 나타내며 연산자 등으로 구성됩니다.

AST는 일반적으로 구문 분석 (구문 분석) 단계의 컴파일러에서 생성되며 나중에 의미 론적 분석, 중간 표현, 코드 생성 등에 사용됩니다.

Answer 4

나는 웹에서 이걸 발견, 어쩌면 도움 :

은 구문 분석 트리 규칙 (와 토큰)의 기록이다 여기

는 AST의 그래픽 표현입니다 일부 입력 텍스트와 일치하는 데 사용되는 반면 구문 트리는 입력 의 구조를 기록하고이를 생성 한 문법에 영향을받지 않습니다. 여기서 은 단일 언어에 대한 문법의 수가 제한되어 있으므로 모든 문법은 모든 다른 중간 규칙 때문에 주어진 입력 문장에 대해 다른 구문 분석 트리 형식이됩니다. 추상 구문 트리는 문법이 아닌 언어의 구조를 강조하므로이 무감각 때문에 정확히 보다 훨씬 뛰어난 중간 형식입니다.