저는 인터프리터/컴파일러의 작동 방식에 대해 조금 읽었습니다. 혼란스러워지는 부분 중 하나는 AST와 CST의 차이입니다. 내 이해는 파서가 CST를 만들고이를 의미 분석기로 전달하여 구문 분석기를 AST로 만듭니다. 그러나 의미 론적 분석기는 단순히 규칙을 지키는 지 확인합니다. 실제로 콘크리트가 아닌 추상적으로 만드는 데 실제로 변경 사항이 적용되는 이유는 실제로 이해할 수 없습니다.추상 구문 트리와 구체적인 구문 트리의 차이점은 무엇입니까?
내가 의미 분석기에 대해 놓치고있는 것이 있습니까? 아니면 AST와 CST의 차이가 다소 인공적입니까?
This blog post이 도움이 될 수 있습니다.
AST는 의미에 영향을주지 않는 중간 문법/구조 정보를 "버려야"하는 것처럼 보입니다. 예를 들어 3이 원자라는 것을 신경 쓰지 않습니다. 하나의 요소는 하나의 요소입니다. .... 당신은 지수 형식을 구현할 때 3을 신경 써야합니다.
구체적인 구문 트리은 언어의 문법 규칙을 따릅니다. 문법에서 "표현의 목록은"일반적으로 두 가지 규칙
으로 정의된다,이 두 가지 규칙은 빗를 제공합니다 모양을 프로그램에 나타나는 모든 표현식 목록에 추가하십시오.
추상 구문 트리은 추가 조작에 편리한 형식입니다. 그것은 프로그램의 의미를 이해하는 사람에게만 의미가있는 방식으로 표현되며, 작성된 방식이 아닙니다. 함수의 인수 목록 일 수있는 위의 표현식 목록은 표현식의 벡터로 편리하게 표현 될 수 있습니다. 정적 분석이 총 표현식 수를 명시 적으로 사용할 수 있고 각 표현식에 액세스 할 수있는 것이 더 좋기 때문입니다. 색인.
구체적인 구문 트리는 원본 텍스트를 정확하게 구문 분석 된 형식으로 나타냅니다. 일반적으로 소스 언어를 정의하는 컨텍스트 프리 (context-free) 문법을 준수합니다.
그러나 구체적인 문법과 트리에는 원본 텍스트를 모호하지 않게 해석 할 수 있도록하는 데 필요한 많은 요소가 있지만 실제 의미에 기여하지는 않습니다. 예를 들어, 연산자 우선 순위를 구현하기 위해 CFG는 여러 수준의 표현 구성 요소 (용어, 요소 등)를 가지며 연산자는 서로 다른 수준에서 연결합니다 (조건을 추가하여 표현식을 얻고 용어는 선택적으로 곱하여집니다 , 등). 그러나 실제로 언어를 해석하거나 컴파일하려면이 작업이 필요하지 않습니다. 연산자와 피연산자가있는 표현식 노드 만 있으면됩니다. 추상 구문 트리는 구체적인 구문 트리를 프로그램의 의미를 나타 내기 위해 실제로 필요한 것으로 단순화 한 결과입니다. 이 트리는 훨씬 간단한 정의를 가지므로 실행의 후반 단계에서 처리하기 쉽습니다.
일반적으로 실제로 구체적인 구문 트리를 작성할 필요가 없습니다. YACC (또는 Antlr 또는 Menhir 등 ...) 문법에있는 작업 루틴은 추상 구문 트리를 직접 작성할 수 있으므로 구체적인 구문 트리는 원본 텍스트의 구문 분석 구조를 나타내는 개념적 엔터티로만 존재합니다.
구체적인 구문 트리에는 불필요한 괄호와 공백 및 주석과 같은 모든 정보가 들어 있으며 추상 구문 트리는이 정보에서 추상화되어 있습니다.
NB : 충분한 재미, 당신은 당신의 AST 다시 모든 구체적인 정보를 포함하는 리팩토링 엔진을 구현하지만 표준 용어에되기 때문에 당신은 AST로 언급하겠습니다 때 그 필드 (오래 전부터 원래의 의미를 잃어 버렸다고 말할 수 있도록).
글쎄, 모든 구체적인 정보가 없을 수도 있습니다. 필요한 것은 그 정보를 다시 생성 할 수 있어야한다는 것입니다. 내 대답을 보라. –
어제에 댓글을 달았습니까? 그래서 버그 또는 내가 알고있는 네크로맨서 배지를 적립해야하는 댓글이 있습니까? :) (추신 : 당신에게서 듣기 좋은데, 당신은 방금 DMS에 관한 귀하의 Google Tech 이야기를 우연히 발견했습니다 ...) – akuhn
구체적인 구문 트리은 문법 규칙에서 구문이 말하는 것과 일치합니다. 추상 구문 트리의 목적은 "구문 트리"에서 필수적인 것을 "단순하게"표현한 것입니다.
AST IMHO의 실제 가치는 중부 표준시보다 작은이며 처리하는 데 소요되는 시간이 짧습니다. (당신은 말할 수 있습니다, 누가 신경 쓰겠습니까? 그러나 우리는 수천만 노드가 한 번에 살고있는 도구로 작업합니다!).
구문 구조 트리 작성을 지원하는 대부분의 구문 분석기 생성기는 트리 노드가 CST보다 "더 간단"하다는 가정하에 직접 작성하는 방법을 사용자가 직접 지정하도록 요구합니다 (일반적으로, 프로그래머는 꽤 게으 르기 때문에). 논리적으로는 트리 방문자 기능을 더 적게 코딩해야한다는 것을 의미합니다. 엔지니어링 에너지를 최소화한다는 점에서 가치가 있습니다. 3500 개의 규칙 (예 : COBOL)이 있으면이 규칙이 중요합니다. 그리고이 "더 단순한"성질은 "작은 것"의 좋은 성질로 인도합니다.
그러나 이러한 AST를 사용하면 문법과 일치하지 않는 문제가 발생합니다. 이제는 문법을 매칭하지 않아도됩니다. 그리고 3500 개의 규칙 문법에 1,500 개의 AST 노드가있을 때 이것은 중요합니다. 그리고 문법이 진화하면 (그들은 항상 그렇습니다!), 이제는 두 가지 거대한 것들을 동기화 할 수 있습니다.
또 다른 해결책은 파서가 단순히 CST 노드를 만들고이를 사용하는 것입니다. 이것은 문법을 구축 할 때 큰 이점입니다. 3500 개의 문법 규칙을 모델링하기 위해 1500 개의 특수 AST 노드를 만들 필요가 없습니다. 트리가 문법과 동형이라고 생각하십시오. 문법 엔지니어의 관점에서 볼 때 이것은 완전히 무절제하기 때문에 문법을 올바르게하고 해킹하는 데 집중할 수 있습니다. 아마도 노드 방문자 규칙을 더 작성해야하지만이를 관리 할 수 있습니다. 나중에 이것에 대한 자세한 내용.
DMS Software Reengineering Toolkit과 함께하는 작업은 (GLR) 구문 분석 프로세스의 결과에 따라 자동으로 CST를 작성하는 것입니다. DMS는 자동있는 문법 규칙 쌍 목록 단자 (키워드 punctation) 의미 쓸모 단항 제작물 반송 아닌 값을 제거하고 형성함으로써, 공간 효율성의 이유에 대해 "압축"CST를 구성 목록 같은
L = e ;
L = L e ;
L2 = e2 ;
L2 = L2 ',' e2 ;
및 이러한 형태의 다양한 변형이있다. 문법 규칙과 가상 CST의 관점에서 생각해보십시오. 도구는 압축 된 표현에서 작동합니다. 당신의 두뇌에서 쉽고, 더 빠르거나 작습니다.
이 방법으로 만들어진 압축 된 CST는 수동으로 설계 한 AST가 많이 보입니다 (끝 부분의 링크 참조). 특히 압축 된 CST는 구체적인 구문 인 노드를 포함하지 않습니다. 부작용이 있습니다. 예를 들어 '('및 ')에 대한 콘크리트 노드가 표현식 하위 문법에서 고전적으로 발견되는 반면에 "괄호 노드"은이 압축 CST로 나타나야합니다. 처리. 진정한 대서양 표준시는 이것을 가지지 못할 것입니다. 이것은 대서양 표준시 건설을 지정하지 않아도되는 편리함에 대해 지불하는 아주 작은 가격과 같습니다. 트리에 대한 문서는 항상 사용 가능하고 정확합니다. 문법 은입니다.
"추가 방문자"는 어떻게 피합니까? 우리는 전체적으로는 아니지만 DMS는 AST를 처리하고 CST와 AST 간의 차이점을 투명하게 처리하는 AST 라이브러리를 제공합니다. 또한 DMS는 트리를 위아래로 계산 한 값을 전달하는 방법 인 "속성 문법"평가 기 (AGE)를 제공합니다. AGE는 모든 트리 표현 문제를 처리하므로 툴 엔지니어는 문법 규칙 자체에 직접 효과적으로 계산을 쓰는 것에 대해서만 우려하고 있습니다. 마지막으로, DMS는 문법의 코드 조각을 사용하여 관련된 노드 유형의 대부분을 모른 채 특정 유형의 하위 트리를 찾는 데 사용할 수있는 "표면 구문"패턴도 제공합니다.
다른 답변 중 하나는 원본을 재생성 할 수있는 도구를 작성하려는 경우 AST가 CST와 일치해야한다는 것입니다. 그다지 좋지는 않지만 CST 노드가있는 경우 소스를 다시 생성하는 것이 훨씬 쉽습니다. DMS generates most of the prettyprinter automatically 두 가지 모두에 액세스 할 수 있기 때문에 : -
결론 : 대서양 횡단은 기저귀 및 개념 모두에 적합합니다. CST에서 자동화 된 AST 구성은 두 가지를 제공하며 두 개의 다른 세트를 추적하는 문제를 피할 수 있습니다.
편집 년 3 월 2015 Link to examples of CST vs. "AST" built this way
그것은 변화를하지 않는 차이입니다.
AST 보통 어휘 콘텐츠 버리는 의해 프로그래밍 언어 표현의 의미를 근사하는 방법으로 설명된다. 대서양 표준시 경우에만 적절한 산술 연산을 표현 mul_rule 및 div_rule를 사용하는 반면, 예를 들어 문맥 자유 문법에 다음과 같은 EBNF 규칙을
term: atom (('*' | '/') term)*
을 작성할 수 있습니다.
처음부터 문법에 이러한 규칙을 적용 할 수 없습니까? 당연하지. 이제
term: mul_rule | div_rule
mul_rule: atom ('*' term)*
div_rule: atom ('/' term)*
, 그런 다음 구문 분석 하향식 (top-down)의 관점에서 생각 : 당신은 언급 AST 노드를 모방하는 데 사용보다 콘크리트 규칙으로 그것을 파괴함으로써 위의 소형 추상적 규칙을 다시 작성할 수 있습니다 두 번째 용어은 mul_rule과 div_rule LL (1) 파서가 처리 할 수없는 것 사이의 첫 번째/첫 번째 충돌을 발생시킵니다. 첫 번째 규칙 형태는 효과적으로 구조를 제거한 두 번째 요소의 왼쪽 인수 분해 버전이었습니다. 여기 LL (1) 사용에 대한 상금을 지불해야합니다.
그래서하는 AST는 문법과 구문 분석기의 결함을 해결하는 데 사용되는 임시 보충입니다. CST -> AST 변환은 리팩토링 움직임이다. 추가 쉼표 또는 콜론 구문 트리에 저장 될 때 아무도는 이제까지 방해하지 않습니다. 반대로 일부 저자는 동시에 여러 트리를 유지 관리하는 대신 리팩터링을 수행하거나 AST를 사용하여 추가 추론 엔진을 작성하기 때문에 AST에 추가 할 수 있습니다.프로그래머들은 좋은 이유로 게으르다. 사실 그들은 오류보고를 위해 AST에서 어휘 분석으로 수집 한 라인 및 컬럼 정보를 저장합니다. 참으로 초록.
이것은 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에 없습니다.
EDIT
들어 더욱 설명을 통해 Compilers and Compiler Generators 페이지 참조. 23
단순히 AST에는 코드의 의미론 만 포함되어 있으며 구문 분석 트리/CST에는 코드 작성 방법에 대한 정보가 포함되어 있습니다.
AST는 CST의 단순화 된 버전입니다. 둘 다 파서로 만들 수 있습니다. 누구나 명확한 설명이 필요한 경우 : http://eli.thegreenplace.net/2009/02/16/abstract-vs-concrete-syntax-trees#id6
그래서 코드에 실제 AST를 만들 수 있습니까? – Joey