Trees and Abstract Syntax

Question 1

What 3 elements comprise a while loop (root, left, right)

Answer 1

Question 2

Why use abstract syntax trees (ASTs)

Answer 2

• Don’t need to be concerned with quirks of individual syntax
• Focuses on the semantics
• Trees vs. strings
• Root determines output type

Question 3

Write the following expression as an abstract syntax tree:

Answer 3

Question 4

What does a while loop look like as an AST

Answer 4

Question 5

What is the arity of a symbol in AST grammar

Answer 5

Question 6

What are the 4 elements that comprise tree grammar

Answer 6

Question 7

What do tree production rules look like

Answer 7

Question 8

What do parenthesis mean when writing ASTs inline

Answer 8

Means it is a sub-tree

Question 9

What does it mean for one symbol to have higher precedence than another?
Eg: 4+5*2

Answer 9

• That symbol ‘binds-tigher’, meaning it claims the element first.
• Can be considered as adding parenthesis
• 4+(5*2)

Question 10

How is precedence ranked

Answer 10

By number (higher is tighter)

Question 11

Why do languages define the association of operators

Answer 11

• To tell us where the missing parenthesis should go when we write an expression that includes adjacent operators of the same precedence.
• 3-2-1+0 = ((3-2)-1) + 1 OR 3 - ((2 -1) + 0) OR …

Question 12

What does left association mean

Answer 12

• Place parenthesis to the left
• Assume left association unless told otherwise

Question 13

What does right association mean

Answer 13

• Place parenthesis to the right

Question 14

What does this AST grammar look like in-line

Answer 14