CS 315-01 Quizzes

  1. Date: Sept. 26, 2017
    Question: Give the rightmost derivation of the string "a = const + b ; b = b - a" 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> - a
                 ⇒ <stmt> ; <var> = <var> - a
                 ⇒ <stmt> ; <var> = b - a
                 ⇒ <stmt> ; b = b - a
                 ⇒ <var> = <expr> ; b = b - a
                 ⇒ <var> = <term> + <term> ; b = b - a
                 ⇒ <var> = <term> + <var> ; b = b - a
                 ⇒ <var> = <term> + b ; b = b - a
                 ⇒ <var> = const + b ; b = b - a
                 ⇒ a = const + b ; b = b - a
    

  2. Date: Sept. 26, 2017
    Question: What are the srings in the language spacified by the following grammar?
    %token A B C D
    %%
    s: A x C A
     | A y A
    x: B ;
    y: B C ;
    
    Is this grammag ambiguous?

    Does the grammar generate conflicts on yacc? If so, what type of conflic is generated?
    Answer:

    There is only one string in the language, L={ABCA};

    The grammar is ambiguous, because the are two parse trees for the string ABCA, as shown below:

       

    The yacc ganerates a shift/reduce conflict on token C.
    On token C, the x rule reduces while the pointer on y rule shifts.


  3. Date: Oct. 27, 2017
    Question: What is the output of the following python program?
    x = 1
    def a(f):
      global x
      y = 7
      def b(f):
        nonlocal y
        print ("in b: x=",x, " y=", y, " f=",f)
        y = 9
      x = 3
      print ("in a,1: x=",x," f=",f)
      b(x)
      print ("in a,2: x=",x," f=",f)
    
    a(55)
    print("in main: x=",x)

    Answer:

    in a,1: x= 3  f= 55
    in b: x= 3  y= 7  f= 3
    in a,2: x= 3  f= 55
    in main: x= 3
    

  4. Date: Oct. 31, 2017
    Question: What are the referencing environments for each of the points in the following perl program?
    
    sub A {
        my $x=2;     # $x uses static scoping
        local $y=3;  # $y uses dynamic scoping
        # Point1
        B();
    
        sub D() {
            # Point2
        }
        D();
    }
    
    sub B {
        # Point3
        C();
    }
    
    sub C {
        $x = 1;
        # Point4
    }
    
    $x = 1;
    A();
    #  Point5
    

    Answer:

    Point1: $x in sub A, $y in sub A
    Point2: $x in sub A, $y in sub A
    Point3: $x in global, $y in sub A
    Point4: $x in global, $y in sub A
    Point5: $x in global


  5. Date: Nov. 23, 2017
    Question: Implement the factorial function using logically-controlled loop in Python. Assume that the parameter is a natural number.
    Answer:

    def factorial(n):
      result = 1
      while n>0 :
        result, n = result*n, n-1
      return result