Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
What is a Boolean Expression?
3.
Methods to Translate Boolean Expressions
3.1.
Numerical Representation
3.1.1.
Translation Scheme using a Numerical Representation
3.2.
Flow-of-Control Statements
3.2.1.
Syntax-Directed Definition for Flow-of-Control Statements
4.
What is Backpatching?
4.1.
Translation Scheme of Backpatching
5.
Frequently Asked Questions
5.1.
How do Compilers handle Short-Circuiting in Boolean Expressions?
5.2.
What are the different ways to optimize the Boolean Expressions in Compiler Design?
5.3.
How do Boolean Expressions influence the flow of the program?
6.
Conclusion
Last Updated: Mar 27, 2024
Easy

Boolean Expression in Compiler Design

Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

Hello Ninja, I hope you are doing great. Do you know about Boolean Expressions in Compiler Design? If not, don't worry. We are here to enrich your knowledge and clear all your doubts. In Compiler Design, the Conditional Statements and Loops are used to control the flow of execution based on some condition, and Boolean Expressions are used to evaluate these conditions. In this article, we will cover Boolean Expressions in detail.

Boolean Expression in Compiler Design

This article will discuss the concept of Boolean Expressions and its different translation methods along with some examples to show its translation schemes. We will also discuss the Backpatching Concept and its translation method.

What is a Boolean Expression?

A Boolean Expression is an expression that evaluates to either true or false. We generally use Boolean Expressions in conditional statements and loops in programming languages. It can be a simple Boolean Variable or a combination of Boolean Variables, Constants, and Operators. Examples of Boolean Operators include “and,” “or,” and “not.” In programming languages, we write boolean expressions in some specific syntax. For example, we represent “and” as “&&” in C++ and Java. In Compiler Design, we use parsing to analyze the Boolean Expression as it allows the Compiler to understand the structure of the Expression.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Methods to Translate Boolean Expressions

Numerical Representation

In Numerical Representation, we denote true by ‘1’ and false by ‘0’. The direction of evaluation of a Boolean Expression is from left to right.
Let’s see some examples to understand Numerical Representation:

The translation for p AND q OR NOT s is:


f1 : = NOT s
f2 : = q OR f1
f3 : = p AND f2


Let’s translate a < b into the three-address code sequence and start numbers at 50:


50:  if a < b goto 53
51:  t : = 0
52:  goto 54
53:  t : = 1
54:


Now, translate a > b into the three-address code sequence and start numbers at 60:


60:  if a < b goto 63
61:  t : = 1
62:  goto 64
63:  t : = 0
64:


Translation Scheme using a Numerical Representation

Productive Rule Semantic Action
E -> E1 OR E2

{

 E.place = newtemp();

 Emit(E.place ‘:=’ E1.place ‘OR’ E2.place)

}

E -> E1 AND E2

{

 E.place = newtemp();

 Emit(E.place ‘:=’ E1.place ‘AND’ E2.place)

}

E -> NOT E1

{

 E.place = newtemp();

 Emit(E.place ‘:=’ ‘NOT’ E1.place)

}

E -> (E1)

{

 E.place = E1.place

}

E -> id1 relop id2

{

 E.place = newtemp();

 Emit(‘if id1.place relop id2.place ‘goto’ nextstate + 3);

 Emit(E.place ‘:=’ ‘0’);

 Emit(‘goto’ nextstate + 2);

 Emit(E.place ‘:=’ ‘1’)

}

E -> true

{

 E.place ‘:=’ newtemp();

 Emit(E.place ‘:=’ ‘1’)

}

E -> false

{

 E.place ‘:=’ newtemp();

 Emit(E.place ‘:=’ ‘0’)

}

Flow-of-Control Statements

In this method, we translate the Boolean Expression into the three-address code in terms of if-then statements, if-then-else statements, and while-do statements.
Here, Boolean Expressions are denoted by ‘E’ and the three-address statement is symbolically labelled.

These are some points you need to keep in mind while determining the Syntax-Directed Definition:

  • The Control will go to the E.true label, if the Expression ‘E’ will be true and the Control will go to the E.false label, if the Expression ‘E’ will be false.
     
  • The Control will flow from S.code to the three-address instruction.
     
  • The label S.next is the first three-address instruction that needs to be executed after the S.code.
     

Syntax-Directed Definition for Flow-of-Control Statements

Production Semantic Rules
S -> if then S1

E.true : = newlabel;

E.false : = S.next;

S1.next : = S.next;

S.code : = E.code || gen(E.true ‘:’) || S1.code

S -> if E then S1 else S2

E.true : = newlabel;

E.false : = newlabel;

S1.next : = S.next;

S2.next : = S.next;

S.code : = E.code || gen(E.true ‘:’) || get(‘goto’ S.next) || gen(E.false ‘:’) || S1.code || S2.code

S -> Whiledo S1

S.begin : = newlabel;

E.true : = newlabel;

E.false : = S.next;

S1.next : = S.begin;

S.code : = gen(S.begin ‘:’) || E.code || gen(E.true ‘:’) || S1.code || gen(‘goto’ S.begin)

What is Backpatching?

It is a technique that involves inserting addresses or labels into the code to represent the jump to be made so that the control will go to that labelled address. 
To manipulate the list of labels, we use three functions:

makelist(i) : It creates a new list containing only ‘i’ and returns a pointer to the list it has made.

merge(p1, p2) : It concatenates the lists pointed by p1 and p2 and returns a pointer to the concatenated list.

backpatch(p, i) : It inserts ‘i’ as the target label for each of the statements on the list pointed by ‘p’.

There are some notations that you need to keep in mind to understand the translation scheme of Backpatching.

  • The attributes ‘truelist’ and ‘falselist’ are used to generate the jumping code for the Boolean Expression.
     
  • The variable ‘nextquad’ holds the index of the next quadruple to follow.
     
  • The attribute ‘M.quad’ records the number of the first statement of E.code

Translation Scheme of Backpatching

Production  Semantic Rules
E -> E1 OR M E2

{

 backpatch (E1.falselist, M.quad);

 E.truelist : = merge(E1.truelist, E2.truelist);

 E.falselist : = E2.falselist

}

E -> E1 AND M E2

{

 backpatch(E1.truelist, M.quad);

 E.truelist : = E2.truelist;

 E.falselist : = merge(E1.falselist, E2.falselist);

}

E -> NOT E1

{

 E.truelist = E1.falslist;

 E.falselist = E1.truelist;

}

E -> (E1)

{

 E.truelist = E1.truelist;

 E.falselist = E1.falselist;

}

E -> id1 relop id2

{

 E.truelist : = makelist(nextquad);

 E.falselist : = makelist(nextquad + 1);

 emit(‘if’ id1.place relop.op id2.place ‘goto_’)

 emit(‘goto_’)

}

E -> true

{

 E.truelist : = makelist(nextquad);

 emit(‘goto_’)

}

E -> false

{

 E.falselist : = makelist(nextquad);

 emit(‘goto_’)

}

M -> ε

{

 M.quad : = nextquad

}

Also check out - Phases of Compiler and Cross Compiler

Frequently Asked Questions

How do Compilers handle Short-Circuiting in Boolean Expressions?

Compilers use Short-Circuiting to optimize Boolean Expressions involving “AND” and “OR” operators. They evaluate only the necessary part of the Expression and skip the remaining part if it is not dependent on the remaining part.

What are the different ways to optimize the Boolean Expressions in Compiler Design?

The Boolean Expressions can be optimize by Constant Folding (replacing constant values with the computed value), Dead Code Elimination (removes the code that will never be executed), Strength Reduction (replaces expensive operation with the cheaper operation) etc.

How do Boolean Expressions influence the flow of the program?

Boolean Expressions determine which branch of the conditional statement should execute and whether the loop should continue or terminate. This plays a crucial role in controlling the program flow and makes the program more flexible.

Conclusion

This article covers the concept of Boolean Expressions in Compiler Design and the Methods to translate Boolean Expressions with the help of a Syntax-Directed Definition table. We have also covered the idea of Backpatching along with its translational scheme.
We hope you enjoyed the article and gained insight into this topic.

You can refer to Control Flow to learn more about Boolean Expressions in Compiler Design.
Head over to our practice platform Coding Ninjas Studio to practice top problems, attempt mock tests, read interview experiences and interview bundles, follow guided paths for placement preparations, and much more!!
Happy Learning Ninja!

Previous article
Handle Pruning in Compiler Design
Next article
Lexeme in Compiler Design
Live masterclass