Tutorial Problems
Tutorial -1
Define Regular Expression for the following:-
i) Validate Email Id
ii) N digit Number
iii) Floating Point Number
iv) Email Validation
v) Residence Address
vi) Vehicle Number
Tutorial – 2
Define the Context Free Grammar for the following:-
i) Assignment Statement
ii) If Statement
iii) While Loop
iv) For Loop
v) Nested For/While loop
vi) Switch Statement
vii) Function Definition and Function call
viii) Printf Statement
Tutorial – 3
Eliminate Left Recursion and Left Factoring for the following Context Free Grammar
Context Free Grammar 1:-
SABD
A aA | a | ε
B bB | b | ε
DdD|d
Context Free Grammar 2:-
S Type id ( Para )
Type int | char | float | void
Para Para, id | id
Context Free Grammar 3:-
S à If ( Cond) { Stat } else { Stat }
Cond à id Relop id
Relop à < | > | <= | >=
Stat à id = Exp
Exp à Exp + Exp | Exp – Exp | Exp * Exp | id | Number
Context Free Grammar 4:-
SABC
A A a1 | A a2 | S A B | a4 | a5
B B b B | B A | b1 | b2
CCAB|aB|CbA
Tutorial – 4
Compute First, Follow and construct predictive parsing table for the following grammar and also
Proposed error recovery mechanism using parsing table.
Context Free Grammar 1:-
S à If ( Cond) { Stat }
Cond à id Relop id
Relop à < | > | <= | >=
Stat à id = Exp
Exp à Exp + Exp | Exp – Exp | Exp * Exp | id
Context Free Grammar 2:-
Sà While(Cond) { Stat ; }
Cond à id Relop id
Relop à < | > | <= | >=
Stat à id = Exp
Exp à Exp + Exp | Exp – Exp | Exp * Exp | id
Context Free Grammar 3:-
SAB
AAbB|Ab|c
BBaB|BAb|BABd|e|f
Tutorial 5
Generate the parsing table for the given grammar using SLR parser and validate the given input
string.
i) SL=R
SR
L*R
L id
RL
ii) S BB
B aB
Ba
Generate the parsing table for the given grammar using canonical LR parser and validate the
given input string:
i) E E sub E sup E
E E sub E
E E sup E
E{E}
ii) S iSeS
S iS
S a
Tutorial 6
Construct the Operator Precedence parsing table for the following grammar and valid the given
input string:-
Grammar 1:-
E → E + E |E − E |E * E |(E) | id.
S iCtS | iCtSeS| a | b
Cd
Grammar 2:-
Sa|V|(T)
T T , S | S
Grammar 3:-
S if ( Cond ) { Stmt } else { Stmt }
Cond id Relop id | id
Relop < | > | <= | > =
Stmt Exp | Assign
Exp Exp + Exp | Exp * Exp | id
Assign id = Exp
Design recursive descent parser for the following grammar:-
Grammar:-
EE+T|T
TT*F|F
F ( E ) | id
Tutorial 7
Construct the parsing table using LALR parser and validate the given input string:-
Grammar 1:-
EE+T|T
T TF | F
F F* | ( E ) | a | b| ε
Grammar 2:-
S aBc | bCd | bBd
B e
Ce
Design recursive descent parser for the following grammar:-
Grammar:-
E E + E | E – E | E * E | - E | ( E ) | id | Number
Tutorial 8
Define syntax translation scheme for assignment statement and construct parse tree for the
following assignment statement and generate intermediate code generated
i) Result = a + b * c – e + f * g – d + e
ii) Total = n1 * n2 + n4 –n1 + n6 + n2 * f2
iii) Value = x1*y1*z1 + x2 * y2*z3 + x3*y3*z3
Define syntax translation scheme for Boolean expression and construct parse tree for the
following Boolean expression and generate intermediate code:-
i) P1 < T1 or R3 > Y4 and X4 < G6 and G8
ii) Num1 < 10 or Num2 > 100 and Num 3 < Num 4
iii) Arg1 < 10 and Arg2 > 100 or Arg3 or Arg4 or Arg2 > Arg3
Tutorial 9
Optimize the given code using Block Partitioning algorithm and construct the basic block
diagram.
Code 1:-
i=0
j=0
Do
Do
Sum = sum + A[i][j] * B[i][j]
j= j + 1
}while(j<20)
i=i+1
}while (i<20)
Code 2:-
i=0
j=0
Sum=0
if( Num1 < Num2)
do
{
Sum = Sum+ C[i][j] + A[i][j] * B[i][j]
j= j + 1
}while(j<20)
else
do
Sum = Sum + C[i] + A[i] * B[i]
i= i + 1
}while(i<20)
Optimize the following three address statement using Basic Block Partitioning algorithm and
construct the basic block flow diagram.
1) i=1
2) j=1
3) t1 = 10 * i
4) t2 = t1 + j
5) t3 = 8 * t2
6) t4 = t3 - 88
7) a[t4] = 0.0
8) j = j + 1
9) if j <= goto (3)
10) i = i + 1
11) if i <= 10 goto (2)
12) i = 1
13) t5 = i - 1
14) t6 = 88 * t5
15) a[t6] = 1.0
16) i = i + 1
17) if i <= 10 goto (13)
Tutorial 10
Design the two pass assembler design for the following assembly code and show the content of
all the data structures.
START 200
MOVER AREG,=’5’
MOVEM AREG,A
LOOP MOVER AREG, A
MOVER CREG, B
ADD CREG,=’1’
……
BC ANY, NEXT
LTORG
=’5’
=’1’
……..
NEXT SUB AREG,=’1’
BC LT, BACK
STOP
ORIGIN LOOP+2
MULT CREG, B
ORIGIN LAST+1
A DS 1
BACK EQU LOOP
B DS 1
END
=’1’
Construct the DAG for the following expressions
1) Temp = A + B * C + B * A + D * E
2) Value = X + Y * C + Y + X + Z * A * B
3) Total = N1 + N2 * N3 – N2+ N3 * N5
Construct the DAG for the following three address statement
1) S1 = 4 * I
2) S2 = addr(A) – 4
3) S3=S2[S1]
4) S4=4*I
5) S5=addr(B)- 4
6) S6=S5[S4]
7) S7=S3 * S6
8) S8= PROD + S7
9) PROD = S8
10) S9 = I +1
11) I = S9
12) If I <= 20 goto (1)
