CS 315-01 Quizzes

1. Date: Sept. 24, 2026
   Question: Given the following grammar,

   <program> ::= <stmt_list>
   <stmt_list> ::= <stmt> | <stmt> <stmt_list>
   <stmt> ::= <declaration_stmt> | <assign_stmt> 
   <declaration_stmt> ::= int <ident_list> ;
   <ident_list> ::= <var_id> | <var_id> , <ident_list>
   <var_id> ::=  x | y | z
   <assign_stmt> ::= <var_id> = <expression> ;
   <expression> ::= <expression> + <expression>
                  | <expression> * <expression>
                  | <constant> | <var_id>
   <constant> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
   

   a) Drive the string "int x, y; x = x + 5 * y;", using the leftmost derivation to show that it is in the language.

   b) Show its parse tree.

   c) Is the grammar ambiguous or not?

   Answer:

   a) The rightmost derivation:

   <program> ⇒ <stmt_list>
             ⇒ <stmt> <stmt_list>
             ⇒ <declaration_stmt> <stmt_list>
             ⇒ int <ident_list> ; <stmt_list>
             ⇒ int <var_id> , <ident_list> ; <stmt_list>
             ⇒ int x , <ident_list> ; <stmt_list>
             ⇒ int x , <var_id> ; <stmt_list>
             ⇒ int x , y ; <stmt_list>
             ⇒ int x , y ; <stmt>
             ⇒ int x , y ; <assign_stmt>
             ⇒ int x , y ; <var_id> = <expression> ;
             ⇒ int x , y ; x = <expression> ;
             ⇒ int x , y ; x = <expression + <expression>  ;
             ⇒ int x , y ; x = <var_id> + <expression> ;
             ⇒ int x , y ; x = x + <expression> ; 
             ⇒ int x , y ; x = x + <expression> * <expression> ; 
             ⇒ int x , y ; x = x + <constant> * <expression> ; 
             ⇒ int x , y ; x = x + 5 * <expression>; 
             ⇒ int x , y ; x = x + 5 * <var_id>; 
             ⇒ int x , y ; x = x + 5 * y; ✓
   

   21 sentential forms.

   b) A parse tree

   

   c) It is ambiguous, becuase instead of <expression> ::= <expression> + <expression> rule, <expression> ::= <expression> * <expression> could be chosen, leading to a different parse tree.

---

2. Date: Oct. 1, 2026
   Question: Disambiguate the following grammar:

   <program> ::= <stmt_list>
   <stmt_list> ::= <stmt> | <stmt> <stmt_list>
   <stmt> ::= <declaration_stmt> | <assign_stmt> 
   <declaration_stmt> ::= int <ident_list> ;
   <ident_list> ::= <var_id> | <var_id> , <ident_list>
   <var_id> ::=  x | y | z
   <assign_stmt> ::= <var_id> = <expr> ;
   <expression> ::= <expr> + <expr>
                  | <expr> * <expr>
                  | <constant> | <var_id>
   <constant> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
   

   Answer:

   <program> ::= <stmt_list>
   <stmt_list> ::= <stmt> | <stmt> <stmt_list>
   <stmt> ::= <declaration_stmt> | <assign_stmt> 
   <declaration_stmt> ::= int <ident_list> ;
   <ident_list> ::= <var_id> | <var_id> , <ident_list>
   <var_id> ::=  x | y | z
   <assign_stmt> ::= <var_id> = <expr_0> ;
   <expr_0> ::= <expr_0> + <expr_1>
              | <expr_1>
   <expr_1> ::= <expr_1> + <expr_2>
              | <expr_2>
   <expr_2> ::=  <constant> | <var_id>
   <constant> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9