CS 315-01 Quizzes

Date: Feb. 3, 2025
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, z; z = 3 + x + 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 leftmost derivation:

<program> ⇒ <stmt_list>
          ⇒ <stmt> <stmt_list>
          ⇒ <declaration_stmt> <stmt_list> 
          ⇒ var <ident_list> ; <stmt_list> 
          ⇒ var <var_id> , <ident_list> ; <stmt_list> 
          ⇒ var x , <ident_list> ; <stmt_list> 
          ⇒ var x , <var_id> , <ident_list> ; <stmt_list> 
          ⇒ var x , y , <ident_list> ; <stmt_list> 
          ⇒ var x , y , <var_id> ; <stmt_list> 
          ⇒ var x , y , z ; <stmt_list>
          ⇒ var x , y , z ; <stmt>
          ⇒ var x , y , z ; <assign_stmt>
          ⇒ var x , y , z ; <var_id> = <expression> ;
          ⇒ var x , y , z ; z = <expression> ;
          ⇒ var x , y , z ; z = <expression> + <expression> ;
          ⇒ var x , y , z ; z = <expression> + <expression> + <expression> ;
          ⇒ var x , y , z ; z = <constant> + <expression> + <expression> ;
          ⇒ var x , y , z ; z = 3 + <expression> + <expression> ;
          ⇒ var x , y , z ; z = 3 + <var_id> + <expression> ;
          ⇒ var x , y , z ; z = 3 + x+ <expression> ;
          ⇒ var x , y , z ; z = 3 + x+ <var_id> ;
          ⇒ var x , y , z ; z = 3 + x + y ;  ✓

23 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: Feb. 13, 2025
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?

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

Answer:

-5
INT
2+2
INT INT
3*5
INT OP INT
2-3 *  5
INT INT OP INT
2/(3 + 5)
INT OP LP INT OP INT RP
(( - 3.15))
LP LP OP FLOAT RP RP
5*(7+1.23 / 5)
INT OP LP INT FLOAT OP INT RP
x = 2%.9 / -  1.2)
x=INT OP FLOAT OP OP FLOAT RP
y = a[1] - 2
y=a[INT ]OP INT
foo(5)
fooLP INT RP

Date: Oct. 21, 2024
Question: In this quiz, you will write a yacc specification file with tokens corresponding to the unique letters in your last name, only. For example, in my case, the tokens are G, U, V, E, N, I, R.

a) Write the grammar rules in such a way that the grammar will have a reduce/reduce conflict.

b) Indicate on what token the conflict will occur.

c) What is the language of the grammar?

d) Is your grammar ambiguous? Why?

Answer:

%token HALIL ALTAY GUVENIR
%%
start: x ALTAY GUVENIR
     | y ALTAY
;
x: HALIL ;
y: HALIL ;

Reduce/reduce conflic on ALTAY.

b) Token ALTAY couses the conflit.

c) L = {HALIL ALTAY GUVENIR, HALIL ALTAY}

d) The grammar is not ambiguous.

Date: Feb. 24, 2025
Question: Given the Push Down Automata given below, show the execution steps of the following input sequences.

a) A A B $end

b) A A B B $end

   0  $accept : start $end

   1  start : A B
   2        | A start B
^L
state 0
        $accept : . start $end  (0)

        A  shift 1
        .  error

        start  goto 2

state 1
        start : A . B  (1)
        start : A . start B  (2)

        A  shift 1
        B  shift 3
        .  error

        start  goto 4

state 2
        $accept : start . $end  (0)

        $end  accept

state 3
        start : A B .  (1)

        .  reduce 1

state 4
        start : A start . B  (2)

        B  shift 5
        .  error

state 5
        start : A start B .  (2)

        .  reduce 2


4 terminals, 2 nonterminals
3 grammar rules, 6 states

Answer:

a) A A B $end

a) A A B B $end

Stack, Case, Action
[0], Token A, shift 1 (push 1 on the stack)
[1,0], Token A, shift 1 (push 1 on the stack)
[1,1,0], Token B, shift 3 (push 3 on the stack)
[3,1,1,0], default redeuce 1, pop 2 states from the stack ( |RHS(rule1)| = 2)
[1,0], a start rule (rule 1) is just reduced, push 4 on the stack
[4,1,0], Token B, shift 5 (push 3 on the stack)
[5,4,1,0], default reduce rule 2, pop 3 states from the stack ( |RHS(rule2)| = 3)
[0], a start rule (rule 1) is just reduced, push 2 on the stack
[2,0], Token $end, accept. Input accepted.

Date: Mar. 13, 2025
Question: What is the output of the following Perl program?

sub fun1 {
    local $a = 10;   # Replace 10 with the last digit of your ID
    local $b = 20;   # replace 20 with the second last digit of your ID
    sub fun1_1 {
        local $b = 30;   # replace 30 with the last two digits of your ID
        print "Point1_1: a=$a, b=$b\n";
        fun1_2();
    }
    sub fun1_2 {
        local $a = 40;
        print "Point1_2: a=$a, b=$b\n";
        fun2();
    }
    fun1_1();
    print "Point1: a=$a, b=$b\n";
}

sub fun2 {
    $a = 50;
    print "Point2: a=$a, b=$b\n";
}

fun1();
print "Point3: a=$a, b=$b\n";

Answer: Assume the last two digits of your ID number are 78.

Point1_1: a=8, b=78
Point1_2: a=40, b=78
Point2: a=50, b=78
Point1: a=8, b=7
Point3: a=, b=