AST for this Mini-language

Question

추상 구문 트리가 메모리에서 어떻게 발생하는지, 각 구문의 트리가 될 것인가, 아니면 단일 루트 트리가 될 것인가를 결정하는 데 문제가 있습니까? .

샘플 소스 :

P: 10 
if A < 15: 
    P: 9 

다음은 BNF-문법입니다 : SPC 흰색 공간과 NL 개행 문자를 나타냅니다

<Prog>  ::= <Stmts> 
<Stmts>  ::= <Stmt> | <Stmt> <Stmt> 
<Stmt>  ::= <IfStmt> NL | <AssignStmt> NL 
<AssignStmt> ::= <Id> : <Aexp> | <Indents> <AssignStmt> 
<IfStmt>  ::= if <Lexp> : NL <Stmts> | <Indents> <IfStmt> 
<Aexp>  ::= <Id> | <Int> | <Aexp> <AOP> <Aexp> 
<Lexp>  ::= <Aexp> <LOP> <Aexp> 
<LOP>  ::= < | > | & 
<AOP>  ::= + | - | * |/
<Int>  ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | <Int> <Int> 
<Id>   ::= A | B | C | D | E | F | P 
<Indents> ::= SPC | SPC <Indents> 

. 예, 7 개의 식별자 만 허용합니다. 그리고 양의 정수.

쉽게 알아볼 수 있지만 많은 부분을 검색했지만 대부분의 AST 예제는 이해하기 쉽지 않은 수학적 표현만을 사용합니다. 문법이 잘못되었다고 생각되면 그렇게 말하십시오. 또한 문법은 파이썬에서 영감을 얻었습니다. 나는 Lexical Analysis 문서를 읽었지 만 단어 트리는 언급하지 않았습니다.

미리 감사드립니다.

Answer 1

프로그램에 여러 "명령문"이있을 수 있고 각 "if 문"아래에 있다고 가정하면 명령문을 메모리의 목록/배열로 정렬 할 수 있습니다. 정말로 나무를 사용하고 싶다면 그렇게 할 수는 있지만 그 나무는 형식적으로 나무가되어 퇴화되고 목록으로 보이고 기능 할 것입니다. 그것에 대해 생각해보십시오. 모든 진술은 나타나고 실행되는 순서가 아닌 다른 진술과 거의 관련이 없습니다. 그들은 재귀 구조를 형성하지 않습니다. P: 10 및 if A < 15:에는 서로 재귀 관계가 없습니다.

문을 표현하기 위해 나무를 사용하는 데는 분명히 유리한 이유가 있습니다. 그러나 나무를 사용하여 하나의 통일 된 데이터 구조를 가질 수 있습니다.

표현식은 많은 연산자가 2 진수이기 때문에 트리 아이디어에 잘 들어 맞습니다. 하나 또는 두 개의 입력을 받아 출력을 생성하고 다른 연산자의 입력으로 사용할 수 있습니다. 여기에 명확한 재귀가 있습니다.

전체 프로그램을 하위 목록 (명령문) 및 트리 (표현식) 목록으로 배열하는 것이 실용적이라고 생각합니다. 그러나 (하위) 목록 대신에 퇴보 된 나무를 사용할 수 있습니다.