• Abstract Syntax Trees
  • Abstract Syntax Trees
  • Intermediate Representation And Three-Address Code
    • Intermediate Representation
    • Three-Address Code
    • Implementation of Three Address Code
    • Summing up (Example of Implementation of Three Address Code)
  • Static Single Assignment Form
    • Quiz6

10/27-W7

reference: [JavaScript] 抽象語法樹 Abstract syntax tree, 抽象语法树 Abstract syntax tree, 打包工具的运行原理

online AST compiler: AST explorer

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

Three-Address Code

• Three address code in Compiler
• It makes use of at most three addresses and one operator (on the right side of an instruction) to represent an expression

  that is, no built-up arithmetic expressions are permitted.

• And the value computed at each instruction is stored in temporary variable 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