June 21, 2024

Complier Design Q&A

Compiler Design
Share :

Complier Design Question and Answers


( Suggestion :  keep refreshing the page for updated content & Search Questions Using Find )


Q.1) a. Consider the following grammar. Analyze if it is suitable for Justify your answer Top-down S->(S) | SS | E
b. Eliminate left Recursion in the following grammar S->Aa|b A->Ac|Sd|E

Answer.

a.
Top-down Analysis of Grammar

The given grammar is :
S -> (S) | SS | E

For a grammar to be suitable for top-down parsing, it should not have left recursion and should preferably be left-factored. Let’s analyze each production:

1. `S -> (S)`: This production indicates recursion where ‘S’ is surrounded by parentheses. However, it’s right recursive which is suitable for top-down parsing.

2. `S -> SS`: This production also indicates recursion but it’s right recursive which is suitable for top-down parsing.

3. `S -> E`: This production is a terminal production, indicating the end of a string.

So, the grammar is suitable for top-down parsing.

b.
Elimination of Left Recursion

The given grammar is:
S -> Aa | b
A -> Ac | Sd | ε

To eliminate left recursion, we can apply the following steps:

1. Identify left-recursive productions.
2. Replace the left-recursive productions with equivalent non-left-recursive productions.

Given that:

S -> Aa | b
A -> Ac | Sd | ε

We can rewrite them as:

S -> bS’
S’ -> aS’ | ε
A -> bA’ | ε
A’ -> cA’ | dS’ | ε

Now the left recursion is eliminated from the grammar.


Q.2) a. Write a YACC program to recognize (0$n 1$n: n >= 0} ($ is to the power operator)

b. Construct the Abstract Syntax Tree and the DAG along with their Three Address Code d+(d*e)-((d+e)/(d*e) +e*(d+e))
Answer.

a)

To write a YACC program to recognize expressions of the form (0^n 1^n: n >= 0), where “$” represents the power operator, you need to define the grammar rules and actions to handle the parsing. Here’s a YACC program for this purpose:

%{
#include <stdio.h>
#include <math.h>
%}

%token NUMBER
%left '^'

%%
input: /* empty */
| input expr '\n' { printf("Valid expression\n"); }
;

expr: '0' '^' NUMBER '1' '^' NUMBER { 
int n = atoi($3);
int m = atoi($6);
if (pow(0, n) == pow(1, m)) {
printf("Valid\n");
} else {
printf("Invalid\n");
}
}
;

%%

int yywrap() {
return 1;
}

int main() {
printf("Enter expression (0^n 1^m: n >= 0, m >= 0):\n");
yyparse();
return 0;
}

int yyerror(char *s) {
printf("Error: %s\n", s);
return 0;
}

int yylex() {
int c = getchar();
if (c == EOF) return 0;
if (c == '0' || c == '1') {
yylval = c;
return NUMBER;
}
if (c == '^' || c == '\n') {
return c;
}
return 0;
}

Save this code in a file named `power_expression.y` and then compile it using `yacc` and `lex`. Here’s how you can compile and run it:

yacc -d power_expression.y
gcc y.tab.c lex.yy.c -o power_expression -lm
./power_expression

Then you can input expressions like `0^3 1^3`, and the program will tell you whether they are valid or not.


B)

To construct the Abstract Syntax Tree (AST) and Directed Acyclic Graph (DAG) along with their Three Address Code (TAC) for the expression `d+(d*e)-((d+e)/(d*e) +e*(d+e))`, we’ll follow these steps:

1. Tokenize the expression.
2. Build the AST.
3. Generate the DAG.
4. Generate the Three Address Code.

Let’s go through each step:

1. Tokenize the expression:
The expression `d+(d*e)-((d+e)/(d*e) +e*(d+e))` can be tokenized as follows:
– `d`, `+`, `(`, `d`, `*`, `e`, `)`, `-`, `(`, `(`, `d`, `+`, `e`, `)`, `/`, `(`, `d`, `*`, `e`, `)`, `+`, `e`, `*`, `(`, `d`, `+`, `e`, `)`, `)`

2. Build the Abstract Syntax Tree (AST):

+
/ \
d -
/ \
* +
/ \ / \
d e * +
/ \ / \
/ e +
/ / \
+ d e
/ \
d e

3. Generate the Directed Acyclic Graph (DAG):

+ (t1)
/ \
t2*d t3+
/ \ 
t4+d*e t5e

4. Generate the Three Address Code (TAC):

1. t1 = d * e
2. t2 = d + t1
3. t3 = d + e
4. t4 = d * e
5. t5 = d + e
6. t6 = t3 / t4
7. t7 = t5 * t3
8. t8 = t2 - t6
9. t9 = t8 + t7
10. Result = t9

Please note that in the DAG, we’re reusing existing temporary variables to optimize memory usage.





Q.3) A. Implement the following expression using quadruples, triples and indirect triples : A=(b+c)*(d-e) 
B)Consider the following block of Statements.
a) SumEven=0 b) SumOdd=0 c) 1-1 d) if t>8 go to Step 12 e) Input a number n f) If n MOD 2==0 then go to step 9 g) SumOdd = SumOdd + n h) Go to step 10 i) SumEven = SumEven + n j) t=t+1 k) go to step 4 Write SumEven m) Write SumOdd Identify the leader statements from the above code segment. Determine the basic blocks and Draw the Control Flow Graph
Answer.
A)

Sure, let’s represent the expression \( A = (b + c) \times (d – e) \) using quadruples, triples, and indirect triples.

First, let’s define some temporary variables to hold intermediate results:

– Let T1, T2, and T3 be temporary variables.

Now, let’s create quadruples (four-element tuples) to represent each operation:

1. Quadruples for addition:
“`
1. (ADD, b, c, T1) // T1 = b + c
“`

2. Quadruples for subtraction:
“`
2. (SUB, d, e, T2) // T2 = d – e
“`

3. Quadruples for multiplication:
“`
3. (MUL, T1, T2, A) // A = T1 * T2
“`

So, combining all the quadruples, we get:

“`
1. (ADD, b, c, T1) // T1 = b + c
2. (SUB, d, e, T2) // T2 = d – e
3. (MUL, T1, T2, A) // A = T1 * T2
“`

These quadruples represent the expression \( A = (b + c) \times (d – e) \) using quadruples.

Now, let’s represent the same expression using triples (three-element tuples):

1. Triples for addition:
“`
1. (ADD, b, c)
“`

2. Triples for subtraction:
“`
2. (SUB, d, e)
“`

3. Triples for multiplication:
“`
3. (MUL, 1, 2, A) // Where 1 and 2 refer to the triples corresponding to addition and subtraction respectively.
“`

So, combining all the triples, we get:

“`
1. (ADD, b, c)
2. (SUB, d, e)
3. (MUL, 1, 2, A)
“`

Finally, let’s represent the expression using indirect triples:

1. Indirect triples for addition:

1. (ADD, b, c, T1) // T1 = b + c

2. Indirect triples for subtraction:

2. (SUB, d, e, T2) // T2 = d - e

3. Indirect triples for multiplication:

3. (MUL, T1, T2, A) // A = T1 * T2

So, combining all the indirect triples, we get:

1. (ADD, b, c, T1) // T1 = b + c
2. (SUB, d, e, T2) // T2 = d - e
3. (MUL, T1, T2, A) // A = T1 * T2

These representations demonstrate how the expression can be implemented using quadruples, triples, and indirect triples. Each approach provides a different way to organize the operations and intermediate results.

B)

To identify leader statements, we need to look for statements that are the target of a branch or the start of the code. In this code segment, the leader statements are:

1. a) SumEven=0
2. e) Input a number n
3. f) If n MOD 2==0 then go to step 9
4. g) SumOdd = SumOdd + n
5. i) SumEven = SumEven + n
6. j) t=t+1
7. k) go to step 4
8. Write SumEven
9. m) Write SumOdd

Now, let’s identify the basic blocks and draw the Control Flow Graph (CFG).

Basic Blocks:
1. Block 1: a) SumEven=0, e) Input a number n
2. Block 2: f) If n MOD 2==0 then go to step 9, g) SumOdd = SumOdd + n, i) SumEven = SumEven + n
3. Block 3: j) t=t+1, k) go to step 4
4. Block 4: Write SumEven, m) Write SumOdd

Control Flow Graph (CFG):

+---> [Block 1] ----> [Block 2] ----> [Block 3] ---+
| |
+---------------------------------------------------+
|
v
[Block 4]

This Control Flow Graph represents the flow of control between basic blocks in the given code segment.





Q.4) a. Construct DAG for the following ((A+B)-((A-B) (A+B)))+((A-B)*(A+B))
b. Write the three-address code, identify the leaders and draw the Control Flow Graph for the following code
1:=1;
j:= 2;
while i≤ 30 && j≤ 15
a:=b+c*d;
i:=i+1;
Answer.

a. Constructing DAG

A DAG (Directed Acyclic Graph) can be constructed for the given expression to optimize it for various compiler tasks like code generation and optimization. Here’s how the DAG can be constructed for the expression:

+
/ \
- *
/ \ / \
+ - + +
/ \ | |
A B A B
/ \ 
A B

b. Three-address code, leaders identification, and Control Flow Graph (CFG)

Three-address code:

1: 1 :=
2: 2 :=
3: i <= 30
4: j <= 15
5: if_false (3 || 4) goto 11
6: t1 := c * d
7: t2 := b + t1
8: a := t2
9: i := i + 1
10: goto 5
11:

Identifying leaders:
– Leader: 1
– Leader: 5
– Leader: 11

Control Flow Graph:
1 -> 5 -> 6 -> 7 -> 8 -> 9 -> 5
5 -> 11





Q.5) a. Construct a transition diagram for unsigned numbers with an Optional fraction and Optional exponent.

b. Design DFA to accept strings over {a,b} having even number of 0’s and even number of 1’s. 

Answer.

a)
To construct a transition diagram for unsigned numbers with an optional fraction and optional exponent, we can use a simplified version of a Finite Automaton.

Here’s a basic representation:

START –> [0-9] –> INTEGER –> (.) –> FRACTION –> (e|E) –> EXPONENT –> (0-9) –> EXP_DIGIT –> ACCEPT
↑ |
| |
| ↓
| (+|-) –> EXP_SIGN –> (0-9) –> EXP_DIGIT –> ACCEPT
|
└—> ACCEPT

Legend:
– START: Starting state.
– INTEGER: State representing integer part.
– FRACTION: State representing fractional part (optional).
– EXPONENT: State representing exponent part (optional).
– EXP_DIGIT: State representing the digits of the exponent.
– EXP_SIGN: State representing the sign of the exponent (optional).
– ACCEPT: Accepting state.

Explanation:
– The transition from START to INTEGER occurs when a digit is encountered.
– From INTEGER, if a dot (.) is encountered, it transitions to FRACTION.
– From FRACTION, if a digit is encountered, it remains in FRACTION.
– From FRACTION, if ‘e’ or ‘E’ is encountered, it transitions to EXPONENT.
– From EXPONENT, if a digit is encountered, it transitions to EXP_DIGIT.
– From EXP_DIGIT, if more digits are encountered, it remains in EXP_DIGIT.
– From EXP_DIGIT, if a dot (.) or ‘e’ or ‘E’ is encountered, it transitions to ACCEPT.
– From INTEGER, if ‘e’ or ‘E’ is encountered, it transitions to EXPONENT.
– From INTEGER, if a (+|-) sign is encountered, it transitions to EXP_SIGN.
– From EXP_SIGN, if a digit is encountered, it transitions to EXP_DIGIT.
– From EXP_SIGN, if a dot (.) is encountered, it transitions to FRACTION.

This diagram allows us to recognize unsigned numbers with optional fractions and optional exponents.





b)

To design a Deterministic Finite Automaton (DFA) that accepts strings over the alphabet {a, b} with an even number of 0’s and an even number of 1’s, we can follow these steps:

1. Define the states.
2. Determine the initial state.
3. Define the transition function.
4. Identify the accepting states.

Let’s design the DFA step by step:

1. Define the states:
– Let’s have four states to represent the parity of the number of 0’s and 1’s:
– State 0: Even number of 0’s and even number of 1’s.
– State 1: Odd number of 0’s and even number of 1’s.
– State 2: Even number of 0’s and odd number of 1’s.
– State 3: Odd number of 0’s and odd number of 1’s.

2. Determine the initial state:
– Since we start with no input, the initial state is State 0.

3. Define the transition function:
– For each state, we define transitions for inputs ‘a’ and ‘b’ based on whether adding ‘a’ or ‘b’ results in an even or odd number of 0’s and 1’s.

| State | Input ‘a’ | Input ‘b’ |
|——-|———–|———–|
| 0 | 2 | 1 |
| 1 | 3 | 0 |
| 2 | 0 | 3 |
| 3 | 1 | 2 |

4. Identify the accepting states:
– The accepting states are those where both the number of 0’s and 1’s is even. So, the accepting states are State 0 and State 2.

With these steps, we have designed the DFA to accept strings over {a, b} with an even number of 0’s and an even number of 1’s. Here is the visual representation of the DFA:

“`
a b
—–> 0 —– 1
| | |
| |b |a
v v v
2 3 —– 0
| | |
| |a |b
v v v
0 <—- 2 —– 1
“`

This DFA will accept strings such as “”, “ab”, “baab”, “baba”, “aabbaa”, etc., but reject strings like “a”, “b”, “aa”, “bb”, “aba”, etc.

 


For More Updates Join Our Channels :