CS 315-01 Quizzes

  1. Date: Feb. 1, 2018
    Question: Give the rightmost derivation of the string "a = a + b ; c = a - b" in the following grammar.
       <program> → <stmts>
       <stmts> → <stmt> | <stmt> ; <stmts>
       <stmt> → <var> = <expr>
       <var>  → a | b | c | d
       <expr> → <term> + <term> | <term> - <term>
       <term> → <var> | const
    

    Answer:

       <program> ⇒ <stmts>
                 ⇒ <stmt> ; <stmts>
                 ⇒ <stmt> ; <stmt>
                 ⇒ <stmt> ; <var> = <expr>
                 ⇒ <stmt> ; <var> = <term> - <term>
                 ⇒ <stmt> ; <var> = <term> - <var>
                 ⇒ <stmt> ; <var> = <term> - b
                 ⇒ <stmt> ; <var> = <var> - b
                 ⇒ <stmt> ; <var> = a - b
                 ⇒ <stmt> ; c = a - b
                 ⇒ <var> = <expr> ; c = a - b
                 ⇒ <var> = <term> + <term> ; c = a - b
                 ⇒ <var> = <term> + <var> ; c = a - b
                 ⇒ <var> = <term> + b ; c = a - b
                 ⇒ <var> = <var> + b ; c = a - b
                 ⇒ <var> = a + b ; c = a - b
                 ⇒ a = a + b ; c = a - b
    

  2. Date: Feb. 15, 2018
    Question: a) Write a Lex specification file for a lexical analyzer that will scan the input for simple arithmetic operators and replace corresponding expressions with their resulting values. All remaining characters will be discarded.
    b) What is the output for the input string "5 * 2 + 3"?
    Answer:

    a)
    /* eval.l */
    %option main
    digit   [0-9]
    sign    [+-]
    float   {sign}?{digit}*(\.)?{digit}+
    op      [+\-\*/]
    %%
       float val1, val2;
       char  op;
    {float}[ ]*{op}[ ]*{float}  {sscanf(yytext, "%f %c %f", &val1, &op, &val2);
                                   if (op == '+') printf("%f", val1 + val2);
                                   if (op == '-') printf("%f", val1 - val2);
                                   if (op == '*') printf("%f", val1 * val2);
                                   if (op == '/') printf("%f", val1 / val2);
                                }
    . ;
    
    b)
    10.000000

  3. Date: Feb. 26, 2018
    Question: Analyze the following grammars in yacc notation for ambiguity and possible conflicts.

    a)

    %token A B C D
    %%
    start: A B x D | y D;
    x: C;
    y: A B C;
    

    b)

    %token X Y
    %%
    s: a | b Y | c X ;
    a: e;
    b: e X | Y;
    c: X | Y ;
    e: ;
    

    Answer:

    a) L={ABCD}. The grammar is ambiguous.

            start            start
         /  /  \  \          /   \
        A   B  x   D        y     D
               |          / | \
               C         A  B  C
    The grammar has reduce / reduce conflict on D. Both of the rules "x: C ." and "y: A B C ." reduce if the next token is D.

    b) L={ε, XY, YY, XX, YX}. The grammar is not ambiguous.
    However, it has shift / reduce conflict on X. When the pointer in rule "e: . " reduces, the pointer on "c: . X" shifts


  • Date: Apr. 12, 2018
    Question:
    void bar (int n, int m) {
       printf("n=%d, m=%d\n", n, m);
       // Point 1
    }
    void foo (int i) {
       int j= i * 3;
       bar (i, j);
       // Point 2
    }
    int main() {
       int x= 3;
       int y= 7 + x;
       foo(y);
    }
    
    For the program given above, what are the contents of the data memory at
    a) Point 1 and
    b) Point 2


    Answer:

    a)
    b)


  • Date: Apr. 19, 2018
    Question: Assume that the following program is written in a language that uses dynamic scoping, and the compiler employs shallow access method.

    a) Draw the contents of the stacks of variables, at the time the print statement is executed for the first time.
    b) What is the output generated at this time.

    void sub3() {
      int x=8, z=9;
      x = u + v;
      print(u, v, w, x, z)
    }
    void sub2(){
      int w=6, x=7;
      sub3();
    }
    void sub1() {
      int w=3, v=5;
      if (flag) sub1(); // flag is true in the first evaluation, false in the second.
      sub2();
    }
    main(){
      int v=1, u=2;
      sub1();
    }


    Answer:

    a)
    b)2 5 6 7 9