CS 315-01 Quizzes

  1. Date: Oct. 9, 2018
    Question: Give the rightmost derivation of the string "a = a - 1 ; 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> 
       <const>  → 0 | 1 | 2 | 3 
    

    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> - <const> ; c = a + b
                 ⇒ <var> = <term> - 1 ; c = a + b
                 ⇒ <var> = <var> - 1 ; c = a + b
                 ⇒ <var> = a - 1 ; c = a + b
                 ⇒ a = a - 1 ; c = a + b
    
  2. Date: Oct. 11, 2018
    Question: Given the following grammar,
    <stmt> -> <matched> | <unmatched>
    <matched> -> if (<logic_expr>) <matched> else <matched>
               | a non-if statement
    <unmatched> -> if (<logic_expr>) <stmt>
                 | if (<logic_expr>) <matched> else <unmatched>
    
    what is the parse tree for the string
    if (C1) if (C2) A else B
    ? Here, C1 and C2 are logical expressions and A an B are non-if statements.
    Answer: