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

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

---

AST가 무엇인지에 대한 일반적인 아이디어가 어떻게 구성하는지 알고 싶습니다.

문법과 구문 분석 트리가 주어진 경우 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와 같은 파서 생성기를 사용합니다. 이러한 도구는 문법에 대한 설명을 가져와 토큰 화 및 파서 용 코드를 생성합니다. (코드 생성 대부분의 인기있는 언어와 일부 인기없는 언어에 존재합니다.)

파서 구성하는 방법은 사용하는 언어에 따라 크게 달라집니다. Haskell에서 파서를 작성하는 방법은 C에서 작성하는 방법과 완전히.

• 다음은 자체 재귀 하강 파서

  를 빌드 하는 방법을 배우고 있습니다.

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

• 당신의 일이라면 아마도 당신을 위해 pyparsing .

---

렉서와 파서에 대해 이야기하지 않고 대답하겠습니다.

구문 분석 트리에는 생성 자유 문법의 일부인 비 터미널 기호가 포함되어 있고, 재귀 적이든 아니든 터미널 기호로 구성되어 있습니다. 따라서 문법이 필요하지 않습니다. 구문 분석 트리에서 문법을 파생 할 수 있습니다.

AST는 비 터미널 기호를 포함하지 않습니다. 기호 만 포함되어 있습니다.

예 :

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

매우 빠른 버전의 a+a*b. 추상 구문 트리가 해석되는 방식은 트리의 우선 순위, 수행하는 순회 유형 (순서, 사전 주문, 사후 주문)에 따라 진행됩니다. 이것은 검색 트리에 코딩하는 일반적인 함수입니다. 그러나 일반적으로 해당 구문 분석 트리의 AST는 다음과 가변적입니다.

   +
 |   |
 a   * 
    | |
    a b

참고 URL : https://stackoverflow.com/questions/1721553/how-to-construct-an-abstract-syntax-tree