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.
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
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:
a)
%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.
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
[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], next token is $end, error. Input reject.
a) A A B B $end
[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.
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=
In Python, the for loop can include an else clause. Java, however, does not support a similar for-else construct. Can any for-else construct be converted to an equivalent Java code? If yes, explain how. If not, explain why. Provide example code in either case.
Answer: Yes, any Python for-else construct can be converted to an equivalent Java code, although Java does not have a native for-else construct.
In Python, the else clause in a for loop is executed only if the loop completes without encountering a break. If the loop is exited early using break, the else block is skipped.
Example in Python:
for x in items:
if x == target:
print("Found")
break
else:
print("Not Found")
- If
targetis found,"Found"is printed, and the loop exits via break. The else block is skipped. - If the loop completes without finding
target, the else block is executed.
Example in Java:
boolean found = false;
for (String x : items) {
if (x.equals(target)) {
System.out.println("Found");
found = true;
break;
}
}
if (!found) {
System.out.println("Not Found");
}
Here, the found variable acts as an indicator of whether the loop exited early.
The final if (!found) simulates the Python else clause.
Assume the file "quiz7.py" contains the following lines.
a = 5
def quiz (q_par):
def closure(c_par):
global a
print ("in closure, a=", a, "q_par=", q_par, "c_par=", c_par)
if (q_par > a):
a += c_par
else:
return "done."
return closure
What is the output of executing each of the following lines, in the order given ?
>>> exec(open("quiz7.py").read())
>>> foo = quiz(12)
>>> foo(1)
# a)
>>> foo(2)
# b)
>>> foo(3)
# c)
>>> foo(4)
# d)
>>> foo(5)
# e)
>>> del quiz
>>> foo(6)
# f)
>>> del a
>>> foo(7)
#g)
Answer:
>>> exec(open("quiz7.py").read())
>>> foo = quiz(12)
>>> foo(1)
in closure, a= 5 q_par= 12 c_par= 1
>>> foo(2)
in closure, a= 6 q_par= 12 c_par= 2
>>> foo(3)
in closure, a= 8 q_par= 12 c_par= 3
>>> foo(4)
in closure, a= 11 q_par= 12 c_par= 4
>>> foo(5)
in closure, a= 15 q_par= 12 c_par= 5
'done.'
>>> del quiz
>>> foo(6)
in closure, a= 15 q_par= 12 c_par= 6
'done.'
>>> del a
>>> foo(7)
Traceback (most recent call last):
File "", line 1, in
File "", line 5, in closure
NameError: name 'a' is not defined
>>>
What are the results of evaluating the following s-expressions, written in Scheme?
a) (car '(a b c))
b) (null? (cddr '(a b)))
c) (list? (cddr '(a b)))
d) ((lambda (x y) (* x (/ x y))) 2 7)
e) (eq? (car '(a b)) (car '(a b c)))
f) (member 'a '((a b)))
g) (append '(a b) (cdr '(a b)))
h) (apply cadr '((a b c d e)))
i) (map (lambda (n m) (+ n (* 2 m))) '(3 5) '(2 4))
j) (apply * (map car '((3 5) (2 7) (4))))
Answer:
a) a
b) #t
c) #t
d) 4/7
e) #t
f) #f
g) (a b b)
h) b
i) (7 13)
j) 24