CS 315-01 Quizzes

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.

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

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);
                            }

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.

Date: Nov. 2, 2026
Question: Given the following JavaScript code,


<script>
x = 5;

function foo() {
  console.log("in foo 1, x=" + x);
  x = 7;  // (*)
  console.log("in foo 2, x=" + x);
}

console.log("in global 1, x=" + x);
foo();
console.log("in global 2, x=" + x);
</script>

Describe what is written to the console.log when the code runs,

a) as given above.

b) when the line with (*) is replaced with var x = 3;

c) when the line with (*) is replaced with let x = 3;

Answer:

in global 1, x=5
in foo 1, x=5
in foo 2, x=7
in global 2, x=7

in global 1, x=5
in foo 1, x=undefined
in foo 2, x=3
in global 2, x=5

in global 1, x=5
Uncaught ReferenceError: Cannot access 'x' before initialization

Date: Nov. 12, 2026
Question: Write the exact output displayed by the Python interpreter for each item.
a) x = [2,4,6,8,10]; del x[1:4]; x
b) x = [10,20,30,40,50]; x[1:4] = ['a','b']; x
c) x = [1,2,3]; y = [x,[4,5]]; x.append(6); y
d) x = (10,20,30); y = list(x); y.insert(1,15); tuple(y)
e) x = ('a','b',[10,20]); x[2].append(30); x
f) x = [11,22,33,44]; h,*t=x; z=[h,*t]; z
g) d = {'a':10,'b':20}; d['c'] = d['a'] + d['b']; d
h) d = {1:'one',2:'two',3:'three'}; del d[2]; d[1]='ONE'; d
i) x = [1,2]; y = x; x = x + [3]; (x,y)
j) x = [10,20]; t = (x,30); d = {'a':t}; x.append(40); d['a']
Answer:
a) [2, 10]
b) [10, 'a', 'b', 50]
c) [[1, 2, 3, 6], [4, 5]]
d) (10, 15, 20, 30)
e) ('a', 'b', [10, 20, 30])
f) [11, 22, 33, 44]
g) {'a': 10, 'b': 20, 'c': 30}
h) {1: 'ONE', 3: 'three'}
i) ([1, 2, 3], [1, 2])
j) ([10, 20, 40], 30)