Week 9 Day 1 And 2

Question 1

Concrete Syntax Tree

Answer 1

Rooted, directed graph that contains no cycles
- start to terminals where: start is the roots, terminal is the leaves, interior nodes are nonterminals

Question 2

What kind of representation for Concrete Syntax Tree?

Answer 2

Graphical IR

Question 3

Concrete Syntax Tree Pros

Answer 3

1. Faithful representation of the original parse of the source code
   - Perfectly represents all of the production rules when parsing
2. Since its a tree, there are a lot of algorithms for it
3. They are primary IR for attribute grammar systems

Question 4

Concrete Syntax Tree Cons

Answer 4

1. Large
2. Contains unnecessary information
3. Requires careful consideration of implementation

Question 5

Abstract Syntax Tree (AST)

Answer 5

Concrete parse tree with many details abstracted away
- Nonterminal nodes are typically replaced by the terminal they map to

Question 6

What representation for Abstract Syntax Tree (AST)?

Answer 6

Graphical IR

Question 7

Abstract Syntax Tree (AST) Pros

Answer 7

• Smaller than a CST
• Retains essential structure of the source code (precedence)
• sometimes collapses to a binary tree

Question 8

Abstract Syntax Tree (AST) Cons

Answer 8

• Still near source level
• requires careful consideration for implementation

Question 9

Directed Acyclic Graph (DAG)

Answer 9

A directed graph with no cycles
- represents POSET
- nodes represented repeated values or subexpressions are combined

Question 10

What representation is DAG?

Answer 10

Graphical IR

Question 11

DAG Pros

Answer 11

• smaller than AST
• captures redundancies and some dead branches in local code

Question 12

DAG cons

Answer 12

• trickier to traverse than a tree
• still a graph, so implementation must be carefully considered

Question 13

Post Fix Notation

Answer 13

Also called reverse Polish Notation
- every expression is writes with the operator at the “end” as in far right side

Question 14

What representation is Post-Fix Notation

Answer 14

Linear IR

Question 15

Post Fix Notation Pros

Answer 15

• concise representation
• easy to generate from bottom up parse
• easy to process using a stack based approach

Question 16

Post Fix Notation Cons

Answer 16

• strange to read
• needs careful management of stack

Question 17

Three address code (TAC)

Answer 17

• resembles assembly for modern machines
• 4-Tuple = (O, D, S1, S2)

Question 18

What representation is TAC?

Answer 18

Linear IR

Question 19

Three-address Code Pros

Answer 19

• compact and concise
• near target representation
• highly amenable to optimization

Question 20

Three Address Code Cons

Answer 20

• requires careful consideration of the namespace for operations and memory
• initial start is highly unoptimized and bloated
• user more abstract registers than physical registers available

Question 21

Intermediate Languages

Answer 21

Front end of a compiler translates the source code program into another language that isn’t the assembly or machine code of the target machine
- C, LLVM (any existing programming language)

Question 22

Intermediate languages Pros

Answer 22

• completely decouples the front and back ends
• has interpreter or compiler
• useful for debugging

Question 23

Intermediate Languages Cons

Answer 23

• if language paradigm is sufficiently different than the IR language, translation will be more complicated
• depending on the tooling and environment of whichever IR language you choose

Question 24

Semantic Analysis

Answer 24

The phase of the compiler that checks the source program for semantic consistency with the language of the definition

Question 25

Jobs of semantic analyzer

Answer 25

Type checking, type coercion/conversion, variable declaration, access control, scope checking, function parameter count and consistency

Question 26

Attribute

Answer 26

Is any quality associated with a programming construct which we represent with our grammar symbols

Question 27

Synthesized attribute

Answer 27

Of a nonterminal A at a parse-tree node N is directly defined by a semantic rule associated with the production of N. Production must feature A as the LHS ( the “head” of the production)

Question 28

Inherited attribute

Answer 28

For nonterminal B at a parse tree node N is defined by a semantic rule associated with the production at parent of N. The production must feature B in the RHS (the “body” of the production)

Question 29

Semantic Rule

Answer 29

Is a specification declaring which attributes or actions to associate with a given nonterminal