CSE 3341 Simple problems

Problem 1

Consider the following grammar discussed in class, derived from Section 6.4 of the C specification. 

identifier -> nondigit | identifier nondigit | identifier digit

nondigit ->  _ | a | ... | Z

digit ->  0 | ... | 9

Part 1. Does the string _ _ constitute a valid identifier, according to this grammar? If so, show one possible derivation of this string. If not, explain why not.

Part 2. Write a regular expression that describes the language defined by this grammar.

Problem 2

Consider the following grammar discussed in class (shown using BNF):

<integer> ::= <digit> | <digit> <integer> 

<digit> ::= 0 | ... | 9

 The grammar describes integer literals (i.e., integer constants in the code). However, in some languages, such literals should not start with 0. For example, in C, a decimal literal cannot start with 0 because only octal literals start with 0 (so, in C literal 53 has the value 10*5+3 = 53, but literal 053 is octal and has the value 8*5+3 = 43). 

Define a modified grammar that disallows integer literals that start with 0. Feel free to add new nonterminals and productions, or to modify existing productions. 

Problem 3

Consider the following ambiguous context-free grammar: 

<expr> ::= <expr> + <expr> | <expr> * <expr> |  ident

Show all possible parse trees for string x * y + z * w  

Problem 4

Consider the following ambiguous context-free grammar: 

<expr> ::= <expr> + <expr> | <expr> * <expr> | <expr> ** <expr> |  ( <expr> ) |  ident

Here ** denotes the exponentiation operator - e.g., x ** y denotes "x to the power of y" (similarly to Python, JavaScript, and Ruby). 

Suppose we instructed the parser to resolve the ambiguity as follows: (1) ** has higher precedence than * which has higher precedence than +; (2) * and + are left-associative; (3) ** is right-associative. Show the parse tree that would be produced for input string  x * y ** z ** ( w + v ) * u   

Problem 5

Suppose that we enhance Project 2 with compound assignment operators +=  and *= as defined by the following productions

<expr> ::= id += <expr> | id *= <expr>

The semantics of id += <expr> is equivalent to the semantics of (id = id + <expr>) and  similarly for *=

Consider expression (x += 1) + (x *= 4) and suppose that the value of x is 2 before the evaluation of this expression starts. Suppose that we use the semantics from Project 2: for any binary expression, the evaluation and side effects of the first operand are completed before evaluation of the second operand starts. What is the result of evaluating this expression? What is the value of x after the evaluation completes? 

Problem 6

Consider the following C program: 

int f(int x) { 

   int y, z; 

   if (x == 1) return 1;

   y = f(x-1); z = x + y; return z; }

void main(void) {

   int v, w;

   v = 3; w = f(v); }  

Part 1.  Consider all possible states of the run-time call stack during the execution of this program.  What is the largest stack depth (i.e., the largest number of activation records) that can be observed?

Part 2. For this largest depth, show all activation records that are on the stack, in the order in which they appear. Indicate clearly which record is on the bottom of the stack. Do not show registers AP/SP/PC, or the content of the code segment. Do show each activation record, the program function it corresponds to, and its local variables and formal parameters. 

Part 3. For the stack configuration from Part 2, consider the moment of time immediately before the top record on the stack is about to be popped. For this moment of time, show the values stored in local variables and formal parameters on the stack (show ``?'' for uninitialized variables).

Problem 7

Consider the following Java program: 

abstract class A { abstract void m(); }

class B extends A { void m() { ... } }

class C extends A { void m() { ... } }

class D extends C { }

class Main { 

   public static void main(String[] args) { 

        A x = new B(); A y = new C(); A z = new D(); B v = new B(); C w = new D();  

       x.m(); y.m(); z.m(); v.m(); w.m(); }

For each of the five calls to m in main, show which method is the compile-time target and which method is the run-time target.