Context Sensitive Anal

Question 1

What is the difference between context free and context sensitive analysis?

Answer 1

Context sensitive analysis will detect if a variable is used before it is declared while context free analysis doesn’t care

Question 2

What is the input, precondition and output of context sensitive analysis

Answer 2

Input: A parse tree

Pre-condition: The program is syntactically valid

Output: 
if ( input is sematically valid) 
=> augmented parse tree & symbol table
else 
=> output ERROR

Question 3

If a program is syntactically valid, what else could be wrong?

Answer 3

• Variables or Procedures could be used before declaration or declared multiple times
• The return value type may not match with what it should be
• parameter list may not be well-typed
• Operators may not be well-typed
• Variables may be used out of scope

Question 4

How do we solve variable declaration issues?

Answer 4

Create a symbol table that stores the name of the variable, location it was declared and type of the variable

Question 5

How do we check for variable declaration issues when using a variable?

Answer 5

Check if the variable is in the symbol table, if it is then continue, else throw an error

Question 6

How do we check for variable declaration issues when declaring a variable?

Answer 6

• Check to see if it is in the symbol table
• If not, add it (name, location, type)
• If it is in the symbol table, throw an error (multiple declarations)

Question 7

When given a parse tree as input, how would you check for variable declaration issues?

Answer 7

First pass (check for multiple declarations):

• recursively traverse the tree
• search for dcl => TYPE ID rule
• if the name is already in the table => throw an error
• else, add the type and name to the symbol table

Second pass (check for undeclared variables):
- recursively traverse the parse tree
- search for rules:
factor => ID
lvalue => ID
- if the ID name is not in the symbol table yet, throw an error

Question 8

How do we check for scope in context sensitive analysis?

Answer 8

Build a global symbol table that keeps track of you procedure names and types

Each procedure in your global symbol table will have its own symbol table to track its paramaeters and local variables

When adding procedures to the global symbol table, check if the procedure name is in the table already, if it is throw an error.

Question 9

What is a procedure signature?

Answer 9

A procedure’s:

• name
• return type
• parameter list and type

Question 10

Why do types matter?

Answer 10

• help us remember what a variable means
• interpret its bits
• limit how a value can be used
• ## catch if we are using it improperly