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
   

   ---

3. Date: Oct. 8, 2026
   Question: Write a lex specification file to generate a scanner that will scan the keyboard and detect integer and floating-point numbers. When it finds a floating-point value, it will replace the corresponding lexeme with [FLOAT:val], similarly, a lexeme representing an integer value will be replaced by [INT:val]; where val; is the numeric value of the lexeme. Other characters should be echoed back to the screen. For example, if the input is

   ab007cd00.750ef-012gh-003.450ij

   the output will be

   ab[INT:7]cd[FLOAT:0.75]ef[INT:-12]gh[FLOAT:-3.45]ij

   Answer:

   %option main
   digit   [0-9]
   sign    [+-]
   %%
   {sign}?{digit}+             { int int_value;
                                 sscanf (yytext, "%d", &int_value);
                                 printf("[INT:%d]", int_value);
                               }
   {sign}?{digit}+\.{digit}+   { float float_value;
                                 sscanf (yytext, "%f", &float_value);
                                 printf("[FLOAT:%g]", float_value);
                               }
   

   ---

4. Date: Oct. 19, 2026
   Question: Determine the language generated by each grammar given below.. Is each of these grammars ambiguous? Check if these grammars contain any form of conflict. If there is a conflict indicate the type of conflict, and the token that causes the conflict.

   a)

   %token ID PLUS
   %%
   expr : expr PLUS expr
        | ID
        ;
   %%

   b)

   
   %token ID PLUS TIMES
   %%
   expr : expr PLUS term
        | term
        ;
   term : term TIMES factor
        | factor
        ;
   factor : ID
          ;
   %%

   Answer:

   a) L= {ID (PLUS ID)*}= {ID, ID PLUS ID, ID PLUS ID PLUS ID, ...}

   The grammar is ambiguous, since ID PLUS ID PLUS ID has two parse trees corresponding to ID PLUS (ID PLUS ID) and (ID PLUS ID) PLUS ID.

   Conflict analysis:

   $accept : ↑ expr $end.

   The pointer moves to the expr rules.
   

   expr: ↑ expr PLUS expr
expr: ↑ ID (*)

   If the next token is ID, the second rule (*) reduces.

   $accept : expr ↑ $end
expr: expr ↑ PLUS expr

   If the next token is PLUS, the pointer shifts.

   expr: expr PLUS ↑ expr

   The pointer moves to the expr rules.
   

   expr: expr PLUS expr
expr: ↑ expr PLUS expr
expr: ↑ ID (*)

   If the next token is ID, the third rule (*) reduces

   expr: expr PLUS expr ↑
expr: expr ↑ PLUS expr
   

   There is a Shift / Reduse conflict on PLUS as

           expr : expr PLUS expr ↑  (Reduce)
           expr : expr ↑ PLUS expr  (Shift)

   b) L= {ID (PLUS ID | TIMES ID)*} = {ID PLUS ID, ID PLUS ID PLUS ID, ID TIMES ID...}

   The grammar is unambiguous.

   There is no conflct.