Complier Design Q&A

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.

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.

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