의미 규칙/추상 구문 트리 규칙

Question

우선, 의미 규칙과 추상 구문 트리 규칙이 동일합니까?

이제 언어 사양이 있고 CFG가있는 경우 추상 구문 트리 규칙을 구성하는 방법은 무엇입니까? 모든 출처가 인정됩니다. 감사.

Answer 1

"추상 구문 트리"규칙 (이상한 용어 임)은 구문 분석이 진행되는 동안 추상 구문 구문을 형성하는 규칙으로 해석 될 수 있습니다. 이들은 일반적으로

T = '(' A ';' B ')' ; 

경우 T.의 자회사 문구를 분석하여 생산 된 추상 구문 트리를 통해 생성자와 같은 비 터미널 T에 대한 문법 규칙, 문법 규칙, T에 대한 AST 생성자가

이 될 수 있습니다입니다 작성됩니다

T(A,B) 

은 A 및 B 서브 파를 위해 구성된 AST 인 자식이있는 T 노드의 구성을 의미합니다.

의미 규칙은 프로그램이 단순한 구문 외에도 합법적이어야한다는 제약 조건입니다. 그래서 ("rules"에서) 추상 구문 트리를 만들 수 있습니다. 그렇게하는 것은 프로그램이 구문 상으로 옳았다는 것을 보여줍니다. 그러나 추상 구문이

"declare s as function; ... s=7; ..." 

일반적으로이를 확인하는 유일한 방법은 로컬 사실을 수집, 추상 구문 트리를 통해 산책하는 것입니다, 예를 들면 의미 단순히 무의미한 것들을 말할 수 (예를 들면, "s는 기능입니다 "은 declare 문에서 추출 된 사실이며"s는 정수가 할당 됨 "은 과제에서 수집되고 해당 사실이 충족 될 때까지 전파되며 호환 가능하도록 표시됩니다.

Answer 2

두 번째 질문에 대답하려면 다음은 문법과 구문 트리의 개념을 연결하고 일부 구문 분석 알고리즘을 검토하는 기사입니다. 문서에서

http://www.cs.purdue.edu/homes/xyzhang/spring11/notes/ast.pdf

:

The resulting grammar is called the concrete grammar. 
The corresponding derivation tree is called the parse tree. 

구체적인 구문 트리 또는 파스 트리 어떤 형식적인 문법에 따라 문자열의 구문 구조를 나타내는 트리입니다. 또한 모호 문법 다루는 문제를 강조

http://www.cs.rochester.edu/~nelson/courses/csc_173/grammars/parsetrees.html

: 여기

은 문법으로부터 파스 트리의 예시적인 유도에 대한 링크이다.