Semantic Analysis

Question 1

What are the two kinds of semantic (contextual) constraints?

Answer 1

Static and Dynamic

Question 2

A static semantic constraint can be checked by…

Answer 2

a compiler performing static analysis.

Question 3

How can a dynamic semantic (contextual) constraint be checked?

Answer 3

It can be checked by runtime code generated by a compiler.

Question 4

What are some examples of static context constraints?

Answer 4

• Variables must be declared before used.
• Variables cannot be declared more than once in the same program unit.
• In x = y, x and y must be compatible.
• Every function must contain at least one return statement.

Question 5

Static Analysis

Constraints can be described in terms of ______ or ______.

Answer 5

• Annotation
• Decoration of a Syntax Tree

Question 6

What is the name of the compiler component that checks for constraints?

Answer 6

Semantic Analyzer

Question 7

Do context free grammars impose contextual constraints on the sentences?

Answer 7

No.

Question 8

Symbols in the grammar are associated with…

Answer 8

attributes.

Question 9

Production rules in a grammar are associated with…

Answer 9

semantic rules indicating how the attribute values are computed.

Question 10

What do attributes in a grammar do?

Answer 10

Capture correspondence between characters and mathematical values.

Example

Attribute val: The mathematical value that corresponds to the digit.

digit = 0 (character)

digit.val = 0 (digit)

Question 11

What do conditions in a grammar do?

Answer 11

Constrain the sentences to those whose legal values are in a fixed and finite range.

Question 12

What can semantic rules do?

Answer 12

Tells us how to compute the values of the attributes from the characters and other attributes.

Question 13

What are synthesized attributes?

Answer 13

Attibute values that are calculated in productions where the associated symbol appears on the left hand side.

Dependencies point from child to parent in the parse tree.

Question 14

(T/F) In inherited attributes, information always flow from child to parent in the parse tree.

Answer 14

False

Information may flow to a node from the parent OR siblings.

Question 15

Analogous with CFG, attribute grammars are declarative.

Explain.

Answer 15

AGs define a set of valid trees, but don’t specify how to build or decorate them just like CFG define valid sentences, but not the parsing algorithm.

Question 16

What are some characteristics of a well-defined attribute grammar?

Answer 16

They have rules that determine a unique set of values for every possible parse tree.

Question 17

What are some characteristics of a non-circular attribute grammar?

Answer 17

A grammar that never yields a parse tree with cycles in the attribute flow graph.

Question 18

What is a translation scheme?

Answer 18

An algorithm that decorates a tree in an order that respects the AGs attribute flow.

Question 19

Describe Most Obvious Scheme

Answer 19

• Works with any well-defined AG, even circular
  
  • Repeated passes over tree
  • Compute attribute at each pass
  • Terminate when values no longer change
• Oblivious
  
  • Doesn’t use any knowledge of structure of tree or grammar

Question 20

How do dynamic scheme translators work?

Answer 20

They tailor the evaluation order to the structure of the given parse tree.

Question 21

The fastest translations schemes tend to be _______.

Answer 21

Static

Question 22

What are S-Attributed grammars?

Answer 22

All attributes are synthesized.

Question 23

How can S-attributed AGs be computed?

Answer 23

They can be computed by a bottom-up traversal of the syntax tree.

Question 24

What is an L-Attributed grammar?

Answer 24

This occurs when A.s depends on B.t if B.t is ever passed to a semantic function that returns a value for A.s.

Question 25

What are the two rules for L-Attributed AGs?

Answer 25

• Each synthesized attribute of a left-hand side symbol depends only on that symbol’s inherited attributes, or on attributes( synthesized or inherited) of right hand side symbols.
• Each inherited attribute of a right side symbol depends only on inherited attributes of the left side symbol, or on attributes of symbols to its left on the right hand side.

Question 26

(T/F) L-attributed grammars can be computed during an LL(1) parse.

Answer 26

True

Question 27

How is an abstract syntax tree different from a concrete syntax tree?

Answer 27

The AST represents the structure of a sentence without unnecessary details.

Question 28

In a parser, what is an action routine?

Answer 28

Semantic function that is executed at a particular point in a parse.

Question 29

What is a visitor pattern?

Answer 29

Separate code for what to do when traversing a data structure from the code for the data structure itself.

Question 30

How can a visitor pattern be implemented?

Answer 30

Define a visitor interface that can handle each type of node in the data structure with different types of signatures.

Question 31

All nodes in an AST are subclasses of a common…

Answer 31

Abstract base class

Question 32

In an AST, if there are multiple productions for a non-terminal, how can an AST be created?

Answer 32

Make the non-terminal class abstract, and introduce a subclass for each production.

Example of one subclass below:

Question 33

In project 3 (AST) the AST nodes consisted of the values of the productions created during parsing to display them. What else can the AST nodes be used for?

Answer 33

AST nodes can be used to store fields that hold attributes used in type checking and code generation.

Question 34

Why are visitor patterns useful in compilers?

Answer 34

It can traverse the AST multiple times with different purposes (type checking, code generation).

Question 35

The abstract AST class contains an abstract visit method to visit all of the concrete AST nodes created. Do all concrete AST node classes need to include an implementation of the visit method?

Answer 35

Yes. The visit method in the AST node will return the object’s information which could be a simple task of printing the values of its fields.