comp
Compiler Journal Index
Practical No: 01
Aim: Write a program to accept a string and validate using NFA
Given a string str consisting of characters a, b and c, check if the number of occurrences of any character in the string is a multiple of 3 or not.
Description: The objective is to pass a regular expression as string, parse it, build a NFA (nondeterministic finite automata), then pass through a series of test strings to see if they are accepted by the regular expression.
CODE:
class Nfa {
static int nfa = 1;
static int flag = 0;
static void state1(char c)
{
if (c == 'a')
nfa = 2;
else if (c == 'b' || c == 'c')
nfa = 1;
else
flag = 1;
}
static void state2(char c)
{
if (c == 'a')
nfa = 3;
else if (c == 'b' || c == 'c')
nfa = 2;
else
flag = 1;
}
static void state3(char c)
{
if (c == 'a')
nfa = 1;
else if (c == 'b' || c == 'c')
nfa = 3;
else
flag = 1;
}
static void state4(char c)
{
if (c == 'b')
nfa = 5;
else if (c == 'a' || c == 'c')
nfa = 4;
else
flag = 1;
}
static void state5(char c)
{
if (c == 'b')
nfa = 6;
else if (c == 'a' || c == 'c')
nfa = 5;
else
flag = 1;
}
static void state6(char c)
{
if (c == 'b')
nfa = 4;
else if (c == 'a' || c == 'c')
nfa = 6;
else
flag = 1;
}
static void state7(char c)
{
if (c == 'c')
nfa = 8;
else if (c == 'b' || c == 'a')
nfa = 7;
else
flag = 1;
}
static void state8(char c)
{
if (c == 'c')
nfa = 9;
else if (c == 'b' || c == 'a')
nfa = 8;
else
flag = 1;
}
static void state9(char c)
{
if (c == 'c')
nfa = 7;
else if (c == 'b' || c == 'a')
nfa = 9;
else
flag = 1;
}
static boolean checkA(String s, int x)
{
for (int i = 0; i < x; i++) {
if (nfa == 1)
state1(s.charAt(i));
else if (nfa == 2)
state2(s.charAt(i));
else if (nfa == 3)
state3(s.charAt(i));
}
if (nfa == 1) {
return true;
}
else {
nfa = 4;
}
return false;
}
static boolean checkB(String s, int x)
{
for (int i = 0; i < x; i++) {
if (nfa == 4)
state4(s.charAt(i));
else if (nfa == 5)
state5(s.charAt(i));
else if (nfa == 6)
state6(s.charAt(i));
}
if (nfa == 4) {
return true;
}
else {
nfa = 7;
}
return false;
}
static boolean checkC(String s, int x)
{
for (int i = 0; i < x; i++) {
if (nfa == 7)
state7(s.charAt(i));
else if (nfa == 8)
state8(s.charAt(i));
else if (nfa == 9)
state9(s.charAt(i));
}
if (nfa == 7) {
return true;
}
return false;
}
public static void main (String[] args)
{
String s = "aabca";
int x = 5;
if (checkA(s, x) || checkB(s, x) || checkC(s, x)) {
System.out.println("STRING IS ACCEPTED");
}
else {
if (flag == 0) {
System.out.println("NOT ACCEPTED");
}
else {
System.out.println("INPUT OUT OF BOUND");
}
}
}
}
OutPut:
Conclusion:
The given string does not satisfy the condition of having a multiple of three occurrences of any one character (a, b, or c), so it is NOT ACCEPTED.
The above algorithm works for n length of string with the time complexity of linear O(n)
Practical No.02
Aim :- Write a program to minimize DFA.
Theory: -
o DFA refers to deterministic finite automata. Deterministic refers to the uniqueness of the computation. The finite automata are called deterministic finite automata if the machine is read an input string one symbol at a time.
o In DFA, there is only one path for specific input from the current state to the next state.
o DFA does not accept the null move, i.e., the DFA cannot change state without any input character.
o DFA can contain multiple final states. It is used in Lexical Analysis in Compiler.
In the following diagram, we can see that from state q0 for input a, there is only one path which is going to q1. Similarly, from q0, there is only one path for input b going to q2.
Formal Definition of DFA
A DFA is a collection of 5-tuples same as we described in the definition of FA. 1. Q: finite set of states
2. ∑: finite set of the input symbol
3. q0: initial state
4. F: final state
5. δ: Transition function
Transition function can be defined as:
1. δ: Q x ∑→Q
Graphical Representation of DFA
A DFA can be represented by digraphs called state diagram. In which: 1. The state is represented by vertices.
2. The arc labeled with an input character show the transitions. 3. The initial state is marked with an arrow.
4. The final state is denoted by a double circle.
Example 1:
1. Q = {q0, q1, q2}
2. ∑ = {0, 1}
3. q0 = {q0}
4. F = {q2}
Solution:
Transition Diagram:
Minimization of DFA
Minimization of DFA means reducing the number of states from given FA. Thus, we get the FSM(finite state machine) with redundant states after minimizing the FSM.
We have to follow the various steps to minimize the DFA. These are as follows:
Step 1: Remove all the states that are unreachable from the initial state via any set of the transition of DFA.
Step 2: Draw the transition table for all pair of states.
Step 3: Now split the transition table into two tables T1 and T2. T1 contains all final states, and T2 contains non-final states.
Step 4: Find similar rows from T1 such that:
1. 1. δ (q, a) = p
2. 2. δ (r, a) = p
That means, find the two states which have the same value of a and b and remove one of them.
Step 5: Repeat step 3 until we find no similar rows available in the transition table T1.
Step 6: Repeat step 3 and step 4 for table T2 also.
Step 7: Now combine the reduced T1 and T2 tables. The combined transition table is the transition table of minimized DFA.
Example:
Solution:
Step 1: In the given DFA, q2 and q4 are the unreachable states so remove them. Step 2: Draw the transition table for the rest of the states.
→Q0 q1 q3
Step 3: Now divide rows of transition table into two sets as:
1. One set contains those rows, which start from non-final states:
2. Another set contains those rows, which starts from final states.
Step 4: Set 1 has no similar rows so set 1 will be the same.
Step 5: In set 2, row 1 and row 2 are similar since q3 and q5 transit to the same state on 0 and 1. So skip q5 and then replace q5 by q3 in the rest.
Step 6: Now combine set 1 and set 2 as:
Now it is the transition table of minimized DFA.
Code:-
Disjoint.py
class DisjointSet(object):
def __init__(self, items):
self._disjoint_set = list()
if items:
for item in set(items):
self._disjoint_set.append([item])
def _get_index(self, item):
for s in self._disjoint_set:
for _item in s:
if _item == item:
return self._disjoint_set.index(s)
return None
def find(self, item):
for s in self._disjoint_set:
if item in s:
return s
return None
def find_set(self, item):
s = self._get_index(item)
return s + 1 if s is not None else None
def union(self, item1, item2):
i = self._get_index(item1)
j = self._get_index(item2)
if i != j:
self._disjoint_set[i] += self._disjoint_set[j]
del self._disjoint_set[j]
def get(self):
return self._disjoint_set
DFA.py
Code
from collections import defaultdict
from disjoint_set import DisjointSet
class DFA(object):
def __init__(self, states_or_filename, terminals=None, start_state=None,
transitions=None, final_states=None):
if terminals is None:
self._get_graph_from_file(states_or_filename)
else:
self.states = states_or_filename
self.terminals = terminals
self.start_state = start_state
self.transitions = transitions
self.final_states = final_states
def _remove_unreachable_states(self):
g = defaultdict(list)
for k, v in self.transitions.items():
g[k[0]].append(v)
stack = [self.start_state]
reachable_states = set()
while stack:
state = stack.pop()
if state not in reachable_states:
stack += g[state]
reachable_states.add(state)
self.states = [state for state in self.states if state in reachable_states]
self.final_states = [state for state in self.final_states if state in reachable_states]
self.transitions = {k: v for k, v in self.transitions.items() if k[0] in reachable_states}
def minimize(self):
self._remove_unreachable_states()
def order_tuple(a, b):
return (a, b) if a < b else (b, a)
table = {}
sorted_states = sorted(self.states)
for i, item in enumerate(sorted_states):
for item_2 in sorted_states[i+1:]:
table[(item, item_2)] = (item in self.final_states) != (item_2 in self.final_states)
flag = True
while flag:
flag = False
for i, item in enumerate(sorted_states):
for item_2 in sorted_states[i+1:]:
if table[(item, item_2)]:
continue
for w in self.terminals:
t1 = self.transitions.get((item, w), None)
t2 = self.transitions.get((item_2, w), None)
if t1 is not None and t2 is not None and t1 != t2:
marked = table[order_tuple(t1, t2)]
flag = flag or marked
table[(item, item_2)] = marked
if marked:
break
d = DisjointSet(self.states)
for k, v in table.items():
if not v:
d.union(k[0], k[1])
self.states = [str(x) for x in range(1, 1 + len(d.get()))]
new_final_states = []
self.start_state = str(d.find_set(self.start_state))
for s in d.get():
for item in s:
if item in self.final_states:
new_final_states.append(str(d.find_set(item)))
break
self.transitions = {(str(d.find_set(k[0])), k[1]): str(d.find_set(v))
for k, v in self.transitions.items()}
self.final_states = new_final_states
def show(self):
temp = defaultdict(list)
for k, v in self.transitions.items():
temp[(k[0], v)].append(k[1])
return temp
def __str__(self):
num_of_state = len(self.states)
start_state = self.start_state
num_of_final = len(self.final_states)
return '{} states. {} final states. start state - {}'.format(
num_of_state, num_of_final, start_state)
def _get_graph_from_file(self, filename):
with open(filename, 'r') as f:
lines = f.readlines()
states, terminals, start_state, final_states = lines[:4]
self.states = states.strip().split()
self.terminals = terminals.strip().split()
self.start_state = start_state.strip()
self.final_states = final_states.strip().split()
self.transitions = {}
for line in lines[4:]:
current_state, terminal, next_state = line.strip().split()
self.transitions[(current_state, terminal)] = next_state
if __name__ == "__main__":
filename = 'graph'
dfa = DFA(filename)
x = dict(dfa.show())
for key, value in x.items():
print(key, ':', value)
print(dfa, "\n")
dfa.minimize()
x = dict(dfa.show())
for key, value in x.items():
print(key, ':', value)
print(dfa)
Graph:
1 2 3 4 5
a b
1
1 5
1 a 3
1 b 2
2 b 1
2 a 4
3 b 4
3 a 5
4 a 4
4 b 4
5 a 3
5 b 2
Output:
Before Minimization
('1', '3') : ['a']
('1', '2') : ['b']
('2', '1') : ['b']
('2', '4') : ['a']
('3', '4') : ['b']
('3', '5') : ['a']
('4', '4') : ['a', 'b']
('5', '3') : ['a']
('5', '2') : ['b']
5 states. 2 final states. start state – 1
After Minimization
('4', '2') : ['a']
('4', '3') : ['b']
('3', '4') : ['b']
('3', '1') : ['a']
('2', '1') : ['b']
('2', '4') : ['a']
('1', '1') : ['a', 'b']
4 states. 1 final states. start state - 4
Conclusion: DFA minimization reduced the automaton from 5 states to 4 states while preserving the same language.
Practical No 3
Aim: Write a Program to implement DFA for the given Language
Theory:
A Deterministic Finite Automaton (DFA) is a mathematical model of computation used to recognize patterns and validate strings over a given alphabet. It consists of a finite set of states, a start state, a set of accepting states, and a transition function that determines the next state for each input symbol. For the given language, the DFA processes each character of the input string and changes states according to predefined rules. If the final state after processing the entire string is an accepting state, the string is accepted; otherwise, it is rejected.
Code:
DFAstartsenda.java
import java.util.*;
class DFAStartEndA {
public static void main(String[] args) {
Random r = new Random();
int max = 1 + Math.abs(r.nextInt() % 15);
int i = 0;
while (i < max) {
char c = (char) ('a' + Math.abs(r.nextInt() % 2));
System.out.print(c + " ");
i++;
if (c == 'a') {
if (i == max)
System.out.print("YES\n");
while (i < max) {
c = (char) ('a' + Math.abs(r.nextInt() % 2));
System.out.print(c + " ");
i++;
if (c == 'a' && i == max)
System.out.print("\nYES\n");
else if (i == max)
System.out.print("\nNO\n");
}
} else {
while (i < max) {
c = (char) ('a' + Math.abs(r.nextInt() % 2));
System.out.print(c + " ");
i++;
}
System.out.print("\nNO\n");
}
}
}
}
DFALanguage.java
Code:
class DFAlanguage {
static int dfa = 0;
static void start(char c) {
if (c == 'a') {
dfa = 1;
} else if (c == 'b') {
dfa = 3;
} else {
dfa = -1;
}
}
static void state1(char c) {
if (c == 'a') {
dfa = 2;
} else if (c == 'b') {
dfa = 4;
} else {
dfa = -1;
}
}
static void state2(char c) {
if (c == 'b') {
dfa = 3;
} else if (c == 'a') {
dfa = 1;
} else {
dfa = -1;
}
}
static void state3(char c) {
if (c == 'b') {
dfa = 3;
} else if (c == 'a') {
dfa = 4;
} else {
dfa = -1;
}
}
static void state4(char c) {
dfa = -1;
}
static int isAccepted(char str[]) {
for (int i = 0; i < str.length; i++) {
if (dfa == 0) {
start(str[i]);
} else if (dfa == 1) {
state1(str[i]);
} else if (dfa == 2) {
state2(str[i]);
} else if (dfa == 3) {
state3(str[i]);
} else if (dfa == 4) {
state4(str[i]);
} else {
return 0;
}
}
return (dfa == 3) ? 1 : 0;
}
public static void main(String[] args) {
char str[] = "aaaaaabbbb".toCharArray();
System.out.println("Input: aaaaaabbbb");
if (isAccepted(str) == 1) {
System.out.println("Output: ACCEPTED");
} else {
System.out.println("Output: NOT ACCEPTED");
}
}
}
Ouput:-
First program output:
Second program ouput:
Conclusion:
Hence,
Hence,The DFA program successfully verifies whether a given string belongs to the specified language by following predefined state transitions. It accepts the string if it ends in a valid final state; otherwise, it rejects it, thus ensuring correct pattern recognition.
Practical No 4
Aim: java program to check syntax of ‘for’ loop
Theory: A for loop in programming follows a fixed syntax that includes the keyword for, parentheses, and exactly two semicolons. Any mistake in this structure can cause a syntax error. This program checks whether the given loop follows the correct format by validating the keyword, counting parentheses, and verifying the number of semicolons. It helps beginners understand common syntax mistakes and ensures proper loop formation. Such syntax checking is useful in basic compiler design concepts
Code:
class ForSyntaxChecker {
static char[] arr = new char[3];
static void isCorrect(String str) {
int semicolon = 0, bracket1 = 0, bracket2 = 0, flag = 0;
int i;
for (i = 0; i < 3; i++) {
arr[i] = str.charAt(i);
}
String firstThree = new String(arr);
if (!firstThree.equals("for")) {
System.out.println("Error in for keyword usage");
return;
}
while (i != str.length()) {
char ch = str.charAt(i++);
if (ch == '(') {
bracket1++;
} else if (ch == ')') {
bracket2++;
} else if (ch == ';') {
semicolon++;
}
}
if (semicolon != 2) {
System.out.println("Semicolon Error");
flag++;
} else if (str.charAt(str.length() - 1) != ')') {
System.out.println("Closing parenthesis absent at end");
flag++;
} else if (str.charAt(3) == ' ' && str.charAt(4) != '(') {
System.out.println("Opening parenthesis absent after for keyword");
flag++;
} else if (bracket1 != 1 || bracket2 != 1 || bracket1 != bracket2) {
System.out.println("Parentheses Count Error");
flag++;
}
if (flag == 0) {
System.out.println("No error");
}
}
public static void main(String[] args) {
String str1 = "for (i = 10; i < 20; i++)";
isCorrect(str1);
String str2 = "for i = 10; i < 20; i++)";
isCorrect(str2);
}
}
Ouput:
Conclusion:
This program successfully checks the syntax of a for loop by validating the correct use of the for keyword, parentheses, and semicolons. It helps in identifying common syntax errors and ensures that the loop follows the standard programming rules.
Practical No 5
Aim: Write a program to construct NFA using given regular expression.
Theory: -
Regular Expression
The language accepted by finite automata can be easily described by simple expressions called Regular Expressions. It is the most effective way to represent any language.
The languages accepted by some regular expression are referred to as Regular languages.
A regular expression can also be described as a sequence of pattern that defines a string.
Regular expressions are used to match character combinations in strings. String searching algorithm used this pattern to find the operations on a string.
For instance:
In a regular expression, x* means zero or more occurrence of x.
It can generate {e, x, xx, xxx, xxxx, .....}
In a regular expression, x+ means one or more occurrence of x.
It can generate {x, xx, xxx, xxxx, .....}
Operations on Regular Language
The various operations on regular language are:
Union: If L and M are two regular languages then their union L U M is also a union.
L U M = {s | s is in L or s is in M}
Intersection: If L and M are two regular languages then their intersection is also an intersection.
L ⋂ M = {st | s is in L and t is in M}
Kleen closure: If L is a regular language then its Kleen closure L1* will also be a regular language.
L* = Zero or more occurrence of language L.
Example 1:
Write the regular expression for the language accepting all combinations of a's, over the set ∑ = {a}
Solution:
All combinations of a's means a may be zero, single, double and so on. If a is appearing zero times, that means a null string. That is we expect the set of {ε, a, aa, aaa, ....}. So we give a regular expression for this as:
R = a*
That is Kleen closure of a.
Example 2:
Write the regular expression for the language accepting all combinations of a's except the null string, over the set ∑ = {a}
Solution:
The regular expression has to be built for the language
L = {a, aa, aaa, ....}
This set indicates that there is no null string. So we can denote regular expression as:
R = a+
Theory Explanation :
∈-NFA is similar to the NFA but have minor difference by epsilon move. This automaton replaces the transition function with the one that allows the empty string ∈ as a possible input. The transitions without consuming an input symbol are called ∈-transitions.
In the state diagrams, they are usually labeled with the Greek letter ∈. ∈-transitions provide a convenient way of modeling the systems whose current states are not precisely known: i.e., if we are modeling a system and it is not clear whether the current state (after processing some input string) should be q or q’, then we can add an ∈-transition between these two states, thus putting the automaton in both states simultaneously.
Common regular expression used in make ∈-NFA:
Example: Create a ∈-NFA for regular expression: (a/b)*a
Algorithm:
To draw NFA for a, a/b ,ab ,a* create a routine for each regular expression.
For converting from regular expression to NFA, certain transitions had been made based on choice of input at the runtime.
Each of the NFA will be displayed in sequential order.
Program:-
nfa.py – consists of the main module and nfa class structure.
from nfa_utils import *
import time
class NFA:
"""Class representing a Non-Deterministic Finite Automaton"""
def __init__(self):
self.alphabet = set()
self.states = {0}
self.transition_function = {}
self.accept_states = set()
self.in_states = {0}
def add_state(self, state, accepts=False):
self.states.add(state)
if accepts:
self.accept_states.add(state)
def add_transition(self, from_state, symbol, to_states):
self.transition_function[(from_state, symbol)] = to_states
if symbol != "":
self.alphabet.add(symbol)
def is_accepting(self):
return len(self.in_states & self.accept_states) > 0
def __str__(self):
return (
"NFA:\n"
f"Alphabet: {self.alphabet}\n"
f"States: {self.states}\n"
f"Transition Function:\n {self.transition_function}\n"
f"Accept States: {self.accept_states}\n"
f"In States: {self.in_states}\n"
f"Accepting: {'Yes' if self.is_accepting() else 'No'}\n"
)
if __name__ == "__main__":
regex = input("Enter the regex pattern:\n> ").lower()
print("\nGiven Regex Pattern:", regex)
print("Building NFA...")
start_time = time.time()
regex_nfa = get_regex_nfa(regex)
end_time = time.time()
print(f"\nBuilt NFA in {(end_time - start_time)*1000:.3f} ms\n")
print(regex_nfa)
Code:
nfa_utils.py:
from nfa import NFA
import copy
def get_single_symbol_regex(symbol):
nfa = NFA()
nfa.add_state(1, True)
nfa.add_transition(0, symbol, {1})
return nfa
def shift(nfa, inc):
nfa.states = {state + inc for state in nfa.states}
nfa.accept_states = {state + inc for state in nfa.accept_states}
new_tf = {}
for (state, symbol), to_states in nfa.transition_function.items():
new_tf[(state + inc, symbol)] = {s + inc for s in to_states}
nfa.transition_function = new_tf
def merge(a, b):
a.states |= b.states
a.transition_function.update(b.transition_function)
a.accept_states = b.accept_states
a.alphabet |= b.alphabet
def get_concat(a, b):
shift(b, max(a.states))
merge(a, b)
return a
def get_union(a, b):
nfa = NFA()
a.accept_states = set()
b.accept_states = set()
shift(a, 1)
merge(nfa, a)
shift(b, max(nfa.states) + 1)
merge(nfa, b)
nfa.add_transition(0, "", {1, min(b.states)})
final_state = max(nfa.states) + 1
nfa.add_state(final_state, True)
nfa.add_transition(max(a.states), "", {final_state})
nfa.add_transition(max(b.states), "", {final_state})
return nfa
def get_kleene_star_nfa(nfa):
nfa.accept_states = set()
shift(nfa, 1)
nfa.add_state(0)
last_state = max(nfa.states)
final_state = last_state + 1
nfa.add_state(final_state, True)
nfa.add_transition(0, "", {1, final_state})
nfa.add_transition(last_state, "", {final_state, 0})
return nfa
def get_one_or_more_of_nfa(nfa):
return get_concat(copy.deepcopy(nfa), get_kleene_star_nfa(nfa))
def get_zero_or_one_of_nfa(nfa):
return get_union(get_single_symbol_regex(""), nfa)
def get_regex_nfa(regex):
if "|" in regex:
i = regex.index("|")
return get_union(
get_regex_nfa(regex[:i]),
get_regex_nfa(regex[i+1:])
)
if "." in regex:
i = regex.index(".")
return get_concat(
get_regex_nfa(regex[:i]),
get_regex_nfa(regex[i+1:])
)
if "*" in regex:
i = regex.index("*")
base = get_kleene_star_nfa(get_regex_nfa(regex[:i]))
return get_concat(base, get_regex_nfa(regex[i+1:])) if i+1 < len(regex) else base
if "+" in regex:
i = regex.index("+")
base = get_one_or_more_of_nfa(get_regex_nfa(regex[:i]))
return get_concat(base, get_regex_nfa(regex[i+1:])) if i+1 < len(regex) else base
if "?" in regex:
i = regex.index("?")
base = get_zero_or_one_of_nfa(get_regex_nfa(regex[:i]))
return get_concat(base, get_regex_nfa(regex[i+1:])) if i+1 < len(regex) else base
if len(regex) == 0:
return NFA()
if len(regex) == 1:
return get_single_symbol_regex(regex)
return get_concat(
get_regex_nfa(regex[0]),
get_regex_nfa(regex[1:])
)
Input:
(a|b)*a
Conclusion:-
The program successfully generates a Non-deterministic Finite Automaton (NFA) state table based on the provided regular expression.
Practical No 6
Aim: Write a code to generate the DAG for the input arithmetic expression.
Theory: -
Directed Acyclic Graph:
The Directed Acyclic Graph (DAG) is used to represent the structure of basic blocks, to visualize the flow of values between basic blocks, and to provide optimization techniques in the basic block. To apply an optimization technique to a basic block, a DAG is a three-address code that is generated as the result of an intermediate code generation.
Directed acyclic graphs are a type of data structure and they are used to apply transformations to basic blocks.
The Directed Acyclic Graph (DAG) facilitates the transformation of basic blocks.
DAG is an efficient method for identifying common sub-expressions.
It demonstrates how the statement’s computed value is used in subsequent statements.
Examples of directed acyclic graph :
Directed Acyclic Graph Characteristics :
A Directed Acyclic Graph for Basic Block is a directed acyclic graph with the following labels on nodes.
The graph’s leaves each have a unique identifier, which can be variable names or constants.
The interior nodes of the graph are labelled with an operator symbol.
In addition, nodes are given a string of identifiers to use as labels for storing the computed value.
Directed Acyclic Graphs have their own definitions for transitive closure and transitive reduction.
Directed Acyclic Graphs have topological orderings defined.
Algorithm for construction of Directed Acyclic Graph :
There are three possible scenarios for building a DAG on three address codes:
Case 1 – x = y op z
Case 2 – x = op y
Case 3 – x = y
Directed Acyclic Graph for the above cases can be built as follows :
Step 1 –
If the y operand is not defined, then create a node (y).
If the z operand is not defined, create a node for case(1) as node(z).
Step 2 –
Create node(OP) for case(1), with node(z) as its right child and node(OP) as its left child (y).
For the case (2), see if there is a node operator (OP) with one child node (y).
Node n will be node(y) in case (3).
Step 3 –
Remove x from the list of node identifiers. Step 2: Add x to the list of attached identifiers for node n.
Example :
T0 = a + b —Expression 1
T1 = T0 + c —-Expression 2
d = T0 + T1 —–Expression 3
Expression 1 : T0 = a + b
Expression 2: T1 = T0 + c
Expression 3 : d = T0 + T1
Example :
T1 = a + b
T2 = T1 + c
T3 = T1 x T2
Example :
T1 = a + b
T2 = a – b
T3 = T1 * T2
T4 = T1 – T3
T5 = T4 + T3
Example :
a = b x c
d = b
e = d x c
b = e
f = b + c
g = f + d
Example :
T1:= 4*I0
T2:= a[T1]
T3:= 4*I0
T4:= b[T3]
T5:= T2 * T4
T6:= prod + T5
prod:= T6
T7:= I0 + 1
I0:= T7
if I0 <= 20 goto 1
Code:
class Graph:
# Constructor
def __init__(self, edges, n):
# Adjacency list representation
self.adjList = [[] for _ in range(n)]
# Add edges to the directed graph
for (src, dest) in edges:
self.adjList[src].append(dest)
# Perform DFS and set departure time
def DFS(graph, v, discovered, departure, time):
discovered[v] = True
for u in graph.adjList[v]:
if not discovered[u]:
time = DFS(graph, u, discovered, departure, time)
departure[v] = time
time += 1
return time
# Function to check if graph is DAG
def isDAG(graph, n):
discovered = [False] * n
departure = [None] * n
time = 0
for i in range(n):
if not discovered[i]:
time = DFS(graph, i, discovered, departure, time)
for u in range(n):
for v in graph.adjList[u]:
if departure[u] <= departure[v]:
return False
return True
if __name__ == '__main__':
edges = [
(0, 1), (0, 3), (1, 2), (1, 3),
(3, 2), (3, 4), (3, 0), (5, 6), (6, 3)
]
n = 7
graph = Graph(edges, n)
print("edges =", edges)
if isDAG(graph, n):
print("The graph is a DAG")
else:
print("The graph is not a DAG")
Conclusion:-
We successfully constructed and checked DAG for the input arithmetic expression.
Practical 7
Aim: Write a program to demonstrate loop unrolling and loop splitting for the given code sequence containing loop.
Theory: -
Loop unrolling is a loop transformation technique that helps to optimize the execution time of a program. We basically remove or reduce iterations. Loop unrolling increases the program’s speed by eliminating loop control instruction and loop test instructions.
Example:
// This program does not uses loop unrolling.
#include<stdio.h>
int main(void)
{
for (int i=0; i<5; i++)
printf("Hello\n"); //print hello 5 times
return 0;
}
// This program uses loop unrolling.
#include<stdio.h>
int main(void)
{
// unrolled the for loop in program 1
printf("Hello\n");
printf("Hello\n");
printf("Hello\n");
printf("Hello\n");
printf("Hello\n");
return 0;
}
Loop splitting (or loop peeling) is a compiler optimization technique. It attempts to simplify a loop or eliminate dependencies by breaking it into multiple loops which have the same bodies but iterate over different contiguous portions of the index range.
A useful special case is loop peeling, which can simplify a loop with a problematic first (or first few) iteration by performing that iteration separately before entering the loop.
Here is an example of loop peeling. Suppose the original code looks like this:
p = 10; for (i=0; i<10; ++i) { y [i] = x [i] + x [p] ; p = i; }
In the above code, only in the 1st iteration is p=10. For all other iterations p=i-1. We get the following after loop peeling:
y [0] = x [0] + x [10] ; for (i=1; i<10; ++i) { y [i] = x [i] + x [i-1] ; }
Code:
Program 1: Without Loop Unrolling
public class LoopUnrollingDemo1 {
public static void main(String[] args) {
System.out.println("Without Loop Unrolling:");
for (int i = 0; i < 5; i++) {
System.out.println("Hello");
}
}
}
Program 2: With Loop Unrolling
public class LoopUnrollingDemo2 {
public static void main(String[] args) {
System.out.println("With Loop Unrolling:");
System.out.println("Hello");
System.out.println("Hello");
System.out.println("Hello");
System.out.println("Hello");
System.out.println("Hello");
}
}
Loop Splitting (Loop Peeling) in Java:
public class LoopPeelingOptimized {
public static void main(String[] args) {
int[] x = new int[11];
int[] y = new int[10];
// Initialize x array
for (int i = 0; i <= 10; i++) {
x[i] = i;
}
System.out.println("After Loop Peeling:");
// First iteration handled separately
y[0] = x[0] + x[10];
// Remaining iterations
for (int i = 1; i < 10; i++) {
y[i] = x[i] + x[i - 1];
}
// Print result
for (int i = 0; i < 10; i++) {
System.out.println("y[" + i + "] = " + y[i]);
}
}
}
OUTPUT:
Loop Peeling (Optimized):
CONCLUSION:
Hence, We have successfully completed Loop rolling and unrolling and Loop splitting(loop peeling ) of the given sequence of code we understand the loop which is printing the word in the two methods which is rolling and unrolling.
Comments
Post a Comment