CS 315-01 Quizzes

Date: Sept. 26, 2024
Question: Given the following grammar,

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

a) Drive the string "var x, y; x = 3 + x + y;", using the rightmost 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>
          ⇒ <stmt> <stmt>
          ⇒ <stmt> <assign_stmt>
          ⇒ <stmt> <var_id> = <expression> ;
          ⇒ <stmt> <var_id> = <expression> + <expression> ;
          ⇒ <stmt> <var_id> = <expression> + <expression> + <expression> ;
          ⇒ <stmt> <var_id> = <expression> + <expression> + <var_id> ;
          ⇒ <stmt> <var_id> = <expression> + <expression> + y ;
          ⇒ <stmt> <var_id> = <expression> + <var_id> + y ;
          ⇒ <stmt> <var_id> = <expression> + x + y ;
          ⇒ <stmt> <var_id> = <constant> 3 + x + y ;
          ⇒ <stmt> <var_id> = 3 + x + y ;
          ⇒ <stmt> x = 3 + x + y ;
          ⇒ <declaration_stmt> x = 3 + x + y ;
          ⇒ var <ident_list> ; x = 3 + x + y ;
          ⇒ var <var_id> , <ident_list> ; x = 3 + x + y ;
          ⇒ var <var_id> , <var_id> ; x = 3 + x + y ;
          ⇒ var <var_id> , y ; x = 3 + x + y ;
          ⇒ var x , y ; x = 3 + x + y ;  ✓

21 sentential forms.

b) The parse tree

c) It is ambiguous, becuase <expression> ::= <expression> + <expression> rule can be expanded from the left <expression> or the right one leading to two different parse trees.

Date: Oct. 10, 2024
Question: Question: A scanner is built from the following lex specification.

%option main
digit   [0-9]
sign    [+-]
%%
[*/%+-]                         printf("OP ");
{sign}?{digit}+                 printf("INT ");
{sign}?{digit}*(\.)?{digit}+    printf("FLOAT ");
\(                              printf("LP ");
\)                              printf ("RP ");
[ \t]                           ;

What is the output of this scanner for the following input?

2+2
2-3 *  5
5*(7+1.23 - 5)
x = 2%.9 / -1.2)
y = a[1] - 2

Answer:

INT INT
INT INT OP INT
INT OP LP INT FLOAT OP INT RP
x=INT OP FLOAT OP FLOAT RP

Date: Oct. 21, 2024
Question: In this quiz, you will write three yacc specifications, where the tokens are your names, written in capital letters in the English alphabet. For example, in my case, the tokens are HALIL, ALTAY, and GUVENIR.
a) The grammar has a reduce/reduce conflict, but it is not ambiguous. Indicate which token causes the conflict. What is the language of the grammar?
b) The grammar has a shift/reduce conflict, and it is ambiguous. Indicate which token causes the conflict. What is the language of the grammar?
c) The grammar has no conflicts. What is the language of the grammar?
Answer:
a)
```
%token HALIL ALTAY GUVENIR
%%
start: x ALTAY GUVENIR
     | y ALTAY
;
x: HALIL ;
y: HALIL ;
```
L = {HALIL ALTAY GUVENIR, HALIL ALTAY}.

Reduce/reduce conflic on ALTAY.

The grammar is unambiguous.
b)
```
%token HALIL ALTAY GUVENIR
%%
start: x GUVENIR
     | y ALTAY GUVENIR
;
x: HALIL ALTAY ;
y: HALIL ;
```
L = {HALIL ALTAY GUVENIR}
Shift/reduce conflic on ALTAY.
The grammar is unambiguous.
c)
```
%token HALIL ALTAY GUVENIR
%%
start: HALIL ALTAY GUVENIR ;
```
L = {HALIL ALTAY GUVENIR}
No conflicts => No ambiguity

Date: Nov. 7, 2024
Question: What is the output of the following Perl program?

sub big {
    my $var=1;    ## Replace 1 with the last digit of your ID
    sub sub1 () {
        print "  In sub1 var=$var\n";
    }
    sub sub2 () {
        my $var = 2;    ## Replace 2 with the second last digit of your ID
        print "In sub2, var=$var\n";
        sub1();
    }
    sub2();
    sub1();
}

print "In global, before big, var=$var\n";
big();
print "In global, after big, var=$var\n";

Answer:

In global, before big, var=
In sub2, var=2
  In sub1 var=1
  In sub1 var=1
In global, after big, var=

Date: Nov. 14, 2024
Question: What are the referencing environments of the print statements in the following python program? What is the output generated?

def foo1():
    x = 1   # Replace 1 with the 1st digit of your ID
    print("Point 1: x=", x, " y=",y)
    def foo2():
        x = 2   # Replace 2 with the 2nd digit of your ID
        global y
        y = 3   # Replace 3 with the 3rd digit of your ID
        def foo3():
            nonlocal x
            x = 4   # Replace 4 with the 4th digit of your ID
            y = 5   # Replace 5 with the 5th digit of your ID
            print("Point 2: x=",x, " y=",y)
        foo3()
        print("Point 3: x=",x, " y=",y)
    foo2()
    print("Point 4: x=",x, " y=",y)

x = 6   # Replace 6 with the 6th digit of your ID
y = 7   # Replace 7 with the 7th digit of your ID
foo1()
print("Point 5: x=",x," y=",y)

Answer:

Point 1: x of foo1, y of global (reference only)
Point 2: x of foo2, y of foo3
Point 3: x of foo2, y of global
Point 4: x of foo1, y of global (reference only)
Point 5: x of global, y of global

Output:

Point 1: x= 1  y= 7
Point 2: x= 4  y= 5
Point 3: x= 4  y= 3
Point 4: x= 1  y= 3
Point 5: x= 6  y= 3