추상 구문 트리를 구성하는 방법

Question

나는 AST가 무엇인지에 대한 일반적인 생각을 가지고 있지만 어떻게 구성하는지 알고 싶다.

문법 및 구문 분석 트리가 있다면, 어떻게 AST를 구성합니까?

문법과 표현식을 사용하면 어떻게 할 수 있습니까?

Answer 1

음, 먼저 문법은 표현식에서 구문 분석 트리를 구성하는 데 사용됩니다. 따라서 이미 파스 트리가 있다면 문법이 필요하지 않습니다.

파서가 수행하는 작업에 따라 표현식을 파싱하여 결과 트리가 이미 추상 구문 트리가 될 수 있습니다. 또는 그것은 ast를 구성하기 위해 두 번째 패스가 필요한 간단한 구문 분석 트리 일 수 있습니다.

문법과 표현식에서 구문 분석 트리를 구성하려면 먼저 문법을 작업 코드로 변환해야합니다. 일반적으로 표현식을 나타내는 입력 스트림을 토큰 목록으로 분할하는 토크 나이저와 토큰 목록을 가져 와서 구문 분석 트리 \ ast를 파서로 만드는 파서로 작업을 분할합니다.

그래서 표현 1 + 2*(3+4)는 다음과 같이 토큰 목록으로 분할 될 수 있습니다

1 - int 
+ - add_operator 
2 - int 
* - mul_operator 
(- lparen 
3 - int 
+ - add_operator 
4 - int 
) - rparen 

첫 번째 열은 실제 텍스트 값입니다. 두 번째는 토큰 유형을 나타냅니다. 이 토큰은 구문 분석기로 보내지며 구문 분석기는 토큰을 인식하고 구문 분석 트리를 작성합니다.

그렇다면 어휘 토크 나이저와 실제 파서는 어떻게 작성합니까? 직접 손으로 굴릴 수 있습니다. 또는 더 일반적으로 coco 또는 antlr 또는 lex/yacc와 같은 파서 생성기를 사용하십시오. 이 도구는 문법을 설명하고 tokenzier 및 파서의 코드를 생성합니다. (코드 생성기는 가장 널리 사용되는 언어와 인기없는 언어에도 사용됩니다.)

구문 분석기를 구성하는 방법은 사용하는 언어에 따라 크게 달라집니다. 어떻게 하스켈 파서를 작성합니다 여기에 당신에게 보여주는 튜토리얼이다,

• C.

  당신이, 말을하는 방법과 완전히 다른 방법 build your own recursive descent parser합니다.

• Coco은 다양한 언어의 파서 생성기이며 에는 시작하는 방법에 대한 문서가 함께 제공됩니다.

• 파이썬이 당신 일이라면 pyparsing 일 것입니다.

Answer 2

나는 렉서와 파서에 대해 이야기하지 않고 일반적인 관점에서 대답 할 것이다.

구문 분석 트리는 문맥 자유 문법의 일부인 비단 말 기호를 포함하며 반복적 또는 비 반복적으로 터미널 기호로 구성된 문자열을 얻기 위해 프로덕션 체인을 표시합니다. 따라서 파스 트리가 있으면 문법이 필요 없습니다. 파스 트리에서 문법을 파생시킬 수 있습니다.

AST에는 비단 말 기호가 없습니다. 심볼 만 포함합니다.

예 :

a+a*b를 보여주는 매우 빠른 버전입니다

E 
| 
E + T 
| | 
T M * M 
| | | 
M a b 
| 
a 

. 추상 구문 트리가 해석되는 방식은 트리의 우선 순위, 어떤 유형의 탐색 (순서대로, 선주 주문, 후행 정렬)에 따라 달라집니다. 이는 검색 트리에 코드를 작성하는 일반적인 기능입니다. 그러나 일반적으로 구문 분석 트리의 AST는 다음과 같을 수 있습니다.

+ 
| | 
a * 
    | | 
    a b