[parsing] 추상 구문 트리와 구체적인 구문 트리의 차이점은 무엇입니까?

Question 1

나는 인터프리터 / 컴파일러가 어떻게 작동하는지에 대해 조금 읽었고, 내가 혼란스러워하는 한 영역은 AST와 CST의 차이입니다. 내 이해는 파서가 CST를 만들고이를 AST로 변환하는 의미 분석기에 전달한다는 것입니다. 그러나 내 이해는 시맨틱 분석기가 단순히 규칙을 따르도록 보장한다는 것입니다. 나는 그것이 구체적이 아니라 추상적으로 만들기 위해 실제로 변경하는 이유를 정말로 이해하지 못합니다.

시맨틱 분석기에 대해 누락 된 부분이 있습니까? 아니면 AST와 CST의 차이가 다소 인위적입니까?

Question 2

구체적인 구문 트리는 구문 분석 된 형식으로 소스 텍스트를 정확하게 나타냅니다. 일반적으로 소스 언어를 정의하는 문맥없는 문법을 따릅니다.

그러나 구체적인 문법과 트리에는 소스 텍스트를 모호하지 않게 구문 분석 할 수 있도록 만드는 데 필요한 많은 것들이 있지만 실제 의미에 기여하지는 않습니다. 예를 들어, 연산자 우선 순위를 구현하기 위해 CFG에는 일반적으로 여러 수준의 식 구성 요소 (용어, 요인 등)가 있으며 연산자는 서로 다른 수준에서 연결합니다 (표현식을 얻기 위해 용어를 추가하고 용어는 선택적으로 다중 요소로 구성됨). 등). 그러나 실제로 언어를 해석하거나 컴파일하려면 이것이 필요하지 않습니다. 연산자와 피연산자가있는 표현식 노드 만 있으면됩니다. 추상 구문 트리는 프로그램의 의미를 표현하는 데 실제로 필요한 것으로 구체적인 구문 트리를 단순화 한 결과입니다. 이 트리는 훨씬 더 간단한 정의를 가지므로 나중에 실행 단계에서 처리하기가 더 쉽습니다.

일반적으로 구체적인 구문 트리를 실제로 구축 할 필요는 없습니다. YACC (또는 Antlr, Menhir 등) 문법의 액션 루틴은 추상 구문 트리를 직접 빌드 할 수 있으므로 구체적인 구문 트리는 소스 텍스트의 구문 분석 구조를 나타내는 개념적 엔티티로만 존재합니다.

Question 3

구체적인 구문 트리 규칙이 말하는 문법 구문 무엇 일치합니다. 추상 구문 트리 의 목적은 “구문 트리”의 필수 요소를 “단순”으로 표현하는 것입니다.

AST IMHO의 실제 가치 는 CST보다 작기 때문에 처리하는 데 시간이 덜 걸린다는 것입니다. (누가 신경 쓰는가?하지만 저는 한 번에 수천만 개의 노드를 사용하는 도구로 작업합니다!).

구문 트리 구축을 지원하는 대부분의 파서 생성기는 트리 노드가 CST보다 “단순”하다는 가정하에 구축 방법을 정확히 지정해야한다고 주장합니다 (그리고 프로그래머가 예쁘기 때문에 일반적으로 옳습니다. 게으른). 아마도 나무 방문자 함수를 더 적게 코딩해야 함을 의미하며 엔지니어링 에너지를 최소화한다는 점에서도 가치가 있습니다. 3500 개의 규칙이있는 경우 (예 : COBOL의 경우) 이것이 중요합니다. 그리고이 “단순함”은 “작음”이라는 좋은 속성으로 이어집니다.

그러나 그러한 AST를 사용하면 거기에 없었던 문제가 발생합니다. 문법과 일치하지 않으며 이제 두 가지를 모두 정신적으로 추적해야합니다. 3500 규칙 문법에 대해 1500 개의 AST 노드가있는 경우 이는 매우 중요합니다. 그리고 문법이 진화한다면 (항상 그렇습니다!), 이제 동기화를 유지해야 할 두 가지 거대한 세트가 있습니다.

또 다른 해결책은 파서가 단순히 CST 노드를 빌드하고이를 사용하도록하는 것입니다. 이것은 문법을 구축 할 때 큰 이점입니다. 3500 개의 문법 규칙을 모델링하기 위해 1500 개의 특수 AST 노드를 발명 할 필요가 없습니다. 나무가 문법과 동형이라고 생각하십시오. 문법 엔지니어의 관점에서 이것은 완전히 두뇌가 없기 때문에 문법을 올바르게 이해하고 마음껏 해킹하는 데 집중할 수 있습니다. 더 많은 노드 방문자 규칙을 작성해야하지만 관리 할 수 있습니다. 이에 대해서는 나중에 자세히 설명합니다.

우리가 함께 할 DMS 소프트웨어 재 설계 툴킷은 자동으로 (GLR) 구문 분석 프로세스의 결과에 따라 CST를 구축하는 것입니다. 그런 다음 DMS는 값을 전달하지 않는 터미널 (키워드, 구두점), 의미 상 쓸모없는 단항 생성을 제거하고 다음과 같은 목록의 문법 규칙 쌍에 대한 목록을 형성하여 공간 효율성을 위해 “압축 된”CST를 자동으로 구성합니다.

    L = e ;
    L = L e ;
    L2 = e2 ;
    L2 = L2  ','  e2 ;

그리고 그러한 형태의 다양한 변형. 문법 규칙과 가상 CST의 관점에서 생각합니다. 도구는 압축 된 표현에서 작동합니다. 두뇌에 부담을주지 않고 런타임에 더 빠르거나 작습니다.

놀랍게도 이러한 방식으로 빌드 된 압축 된 CST는 손으로 디자인했을 수도있는 AST와 비슷해 보입니다 (예제 끝의 링크 참조). 특히 압축 된 CST는 구체적인 구문 인 노드를 전달하지 않습니다. 약간의 어색함이 있습니다. 예를 들어, 표현식 하위 문법에서 고전적으로 발견되는 ‘(‘및 ‘)’에 대한 구체적인 노드는 트리에 없지만 “괄호 노드” 는 압축 된 CST에 나타나며 처리해야합니다. 진정한 AST는 이것이 없을 것입니다. 이것은 AST 구성을 지정할 필요가 없다는 편의를 위해 지불하는 매우 작은 가격처럼 보입니다. 트리에 대한 문서는 항상 사용 가능하고 정확합니다. 문법 은 문서입니다.

“추가 방문자”를 피하려면 어떻게해야합니까? 우리는 전적으로는 아니지만 DMS는 AST를 안내하고 CST와 AST 간의 차이점을 투명하게 처리하는 AST 라이브러리를 제공합니다. DMS는 또한 노드에서 계산 된 값을 트리의 위아래로 전달하는 방법 인 “속성 문법”평가 기 (AGE)를 제공합니다. AGE는 모든 트리 표현 문제를 처리하므로 도구 엔지니어는 문법 규칙 자체에 직접 계산을 효과적으로 작성하는 것에 대해서만 걱정합니다. 마지막으로, DMS는 또한 관련된 대부분의 노드 유형을 알지 못해도 문법의 코드 조각을 사용하여 특정 유형의 하위 트리를 찾는 데 사용할 수있는 “표면 구문”패턴을 제공합니다.

다른 답변 중 하나는 소스를 재생성 할 수있는 도구를 빌드하려는 경우 AST가 CST와 일치해야한다는 것을 관찰합니다. 그것은 옳지 않지만 CST 노드가있는 경우 소스를 재생성하는 것이 훨씬 쉽습니다. DMS는 두 가지 모두에 액세스 할 수 있기 때문에 대부분의 prettyprinter를 자동으로 생성 합니다. :-}

결론 : AST는 물리적 및 개념적 모두 소규모에 적합합니다. CST의 자동화 된 AST 구성은 두 가지를 모두 제공하며 두 가지 세트를 추적하는 문제를 방지 할 수 있습니다.

2015 년 3 월 수정 : 이러한 방식으로 구축 된 CST 대 “AST”의 예 링크

Question 4

이것은 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에는 괄호가 없습니다.

AST

편집하다

자세한 설명은 컴파일러 및 컴파일러 생성기 페이지를 참조하십시오 . 23

Question 5

이 블로그 게시물 이 도움 이 될 수 있습니다.

AST가 의미론에 기여하지 않는 많은 중급 문법 / 구조 정보를 “버려 버린”것 같습니다. 예를 들어, 당신은 3이 원자이고 항이 요인이라는 것을 신경 쓰지 않습니다. 당신 3은 지수 식을 구현할 때인 지 또는 무엇이든 상관하지 않습니다.

Question 6

콘크리트 구문 트리가 언어의 문법의 규칙을 따른다. 문법에서 “표현식 목록”은 일반적으로 두 가지 규칙으로 정의됩니다.

expression_list는 다음과 같을 수 있습니다.
expression_list는 다음과 같을 수 있습니다. expression, expression_list

말 그대로이 두 가지 규칙은 프로그램에 나타나는 모든 표현식 목록에 빗 모양을 제공합니다.

추상 구문 트리가 더 조작 편리 형태이다. 프로그램이 작성된 방식뿐만 아니라 프로그램의 의미를 이해하는 사람에게 의미있는 방식으로 사물을 나타냅니다. 함수의 인수 목록이 될 수있는 위의 표현식 목록은 표현식의 벡터로 편리하게 표현할 수 있습니다. 정적 분석이 총 표현식 수를 명시 적으로 사용하고 각 표현식에 액세스 할 수있는 것이 더 낫기 때문입니다. 인덱스.

Question 7

간단히 말해서 AST는 코드의 의미 만 포함하고 Parse tree / CST에는 코드가 정확히 어떻게 작성되었는지에 대한 정보도 포함됩니다.

Question 8

구체적인 구문 트리에는 불필요한 괄호, 공백 및 주석과 같은 모든 정보가 포함되어 있으며 추상 구문 트리는이 정보를 추상화합니다.

NB : 재미있게도, 리팩토링 엔진을 구현할 때 AST는 다시 모든 구체적인 정보를 포함 할 것이지만, 그것이 현장의 표준 용어가 되었기 때문에 계속해서 AST로 언급 할 것입니다. 이전에는 원래 의미를 잃었습니다).