Quiz 5 Abastract Syntax Tree

CFG and the attribute grammar

• FT with end tail = end product parent
• Use the cheat sheet for fig 4,3 to parse thru the tree?

Drawing 2025-02-25 05.46.55.excalidraw

Excalidraw Data

Text Elements

(7-1)*5

Embedded Files

12051a6973b770a604275ad3fa42a77230ebe8ff: Pasted Image 20250225064524_350.png

Link to original

AST

Constructing:

We think of this like reading, the leftmost on same depth will be the most immediate operation. So taking some - ⇒ ${}_{-}^{+}$ will be + then -.

NNN+10−(3∗2.3)−(2−OU)/2

• left right side of EQ is deepest in tree
• Rightmost creates the “root”
• Order of ops really only matters for same depth

  Drawing 2025-02-25 04.36.25.excalidraw

  Excalidraw Data

  Text Elements

  Link to original

  If we didn’t have parentheses around (2-OU), then \ instead of -

If we had $10-((3\ast 2.3)-(2-OU)/2)$ Instead, then 10 would be on depth 1, - on depth 0, (...) on depth 1 right side

Reading an AST:

Say we have

         (-)
        /   \
      (-)     (/)
     /   \   /   \
   (-)    2 OU   2
  /   \    
(+)     (*)
 / \    /   \
NNN 10  3   2.3

We read LEFT to RIGHT visiting each child before moving on. Start with NNN+10, then deal with -, which has unvisited child of * which has children of 2.3 $\to$ NNN+10-(3*2.3)
Repeat process as many times as needed

Fig 4.3 simplified (likely have on cheat sheet)

• .st is with any func with op, and is the argument for func. .
• val is the output of the func/statement

1. E $\to$ T TT
2. TT $\to$
   1. op T TT
   2. $ϵ$
3. T $\to$ F FT
4. FT $\to$
   1. op F FT
   2. $ϵ$ .st,.val= parent .val
5. F $\to$
   1. op
   2. (E)
   3. const

left box holds the st attribute