---
title: Adv Compiler(10/27)W7#7 - Abstract Syntax Trees
tags: 111-1, AdvCompiler
---
[TOC]

<style>
.blue {
color: blue;
}
.red {
color: red;
}
.green {
color: green;
}
.purple {
color: purple;
}
</style>

###### 10/27-W7
###### reference: [[JavaScript] 抽象語法樹 Abstract syntax tree](https://zwh.zone/javascript--e6-8a-bd-e8-b1-a1-e8-aa-9e-e6-b3-95-e6-a8-b9-abstract-syntax-tree--ef-bc-9a-e6-89-93-e5-8c-85-e5-b7-a5-e5-85-b7--e8-88-87--e4-bb-a3-e7-a2-/), [抽象语法树 Abstract syntax tree](https://juejin.cn/post/6844903582676811790), [打包工具的运行原理](https://juejin.cn/post/6844903620765286407?utm_source=gold_browser_extension)
###### online AST compiler: [AST explorer](https://astexplorer.net/)

# Abstract Syntax Trees
- **直接將 代碼 轉換成 樹狀 的方式表示**
- 打包工具 與 代碼編譯 的核心原理
- 要能夠從記錄的資料還原成原始資料。
- example: 右圖為轉換為 AST 之後的樣子(JaveScript)

## Abstract Syntax Trees
Design of an AST
⬢ Rule of thumb: It should be possible to
unparse an AST.
⬢ The implementation of an AST should be
decoupled from the essential information
represented within the AST.
⬢ There is no single glass hierarchy that can
serve to describe AST nodes for all purposes.

## Intermediate Representation And Three-Address Code
### Intermediate Representation
- [Intermediate Code Generation in Compiler Design](https://www.geeksforgeeks.org/intermediate-code-generation-in-compiler-design/)
### Three-Address Code
- [Three address code in Compiler](https://www.geeksforgeeks.org/three-address-code-compiler/)
- It makes use of <span class="red">at most three addresses</span> and <span class="red">one operator</span> (on the right side of an instruction) to represent an expression
> that is, no built-up arithmetic expressions are permitted.
- And <span class="red">the value computed</span> at each instruction <span class="red">is stored in temporary variable</span> generated by compiler.
#### Example: a+a*(b–c)+(b–c)*d

#### Addresses
An address can be:
⬢ A name
⬢ A constant
⬢ A compiler-generated temporary

### Implementation of Three Address Code
- 3 representations of three address code namely
1. Quadruple
2. Triples
3. Indirect Triples

#### 1. Quadruple
- It is structure with consist of 4 fields namely op, arg1, arg2 and result.
1. op $\leftarrow$ operator
2. arg1, arg2 $\leftarrow$ two operands
3. result $\leftarrow$ store the result of the expression
- Advantage:
- Easy to *rearrange code* for **global optimization**.
- One can ***quickly access** value of temporary variables using **symbol table**.*

- Disadvantage:
- Contain lot of temporaries. *Temporary variable* creation **increases time and space complexity**.

#### 2. Triples

#### 3. Indirect Triples

### Summing up (Example of Implementation of Three Address Code)
#### Question – Write **quadruple**, **triples** and **indirect triples** for following expression :
**(x + y) * (y + z) + (x + y + z)**
#### Answer -
The three address code is:
t1 = x + y
t2 = y + z
t3 = t1 * t2
t4 = t1 + z
t5 = t3 + t4

## Static Single Assignment Form
- requires that each variable be assigned exactly once.
- every variable be defined before it is used.

### Quiz6