Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Last Updated: Jul 17, 2024

Control Flow

Author Apoorv Dixit
0 upvote
Table of contents
Leveraging ChatGPT - GenAI as a Microsoft Data Expert
23 Jul, 2024 @ 01:30 PM
Speaker
Prerita Agarwal
Data Specialist @

Control flow is an order in which statements are executed. The code executes in order from the first line in the file to the last line unless it comes across conditionals or loops that change the order. 

Control flow statements include conditional statements, branching statements, and looping statements. Control flow can be decided with the help of a boolean expression (an expression that evaluates to either true or false). 

The translation of boolean expressions is connected to the translation of statements like if-else statements and while statements. Boolean expressions are frequently used in programming languages to:-

  1. Compute the logical values: True or false can be represented as values in a boolean expression. These boolean phrases can be evaluated using three-address instructions and logical operators, just like arithmetic expressions.
  2. Alter the flow control: Boolean expressions are utilized as conditional expressions in statements that change the flow of control. The value of such boolean expressions is implicit in the program's position. For example, if(E) S, where E is a boolean expression, and 'S' is the statement. Control will reach S only if the boolean expression E evaluates to true. 

Compiler Design
Also see, Translation of Expressions

Boolean Expressions

As discussed above boolean expressions are expressions that evaluate to either true or false and are used to alter the control flow. Boolean expressions are made of boolean operators(such as &&(AND), ||(OR), !(NOT), etc), elements(boolean variables) and relational expressions. Relational expressions are of the form E1 rel E2, where E1 and E2 are arithmetic expressions.

Example: A→ A1 || A2 | (A && A) | E rel E | true 

In the above expression, if we determine whether A1 is true for expression A1 || A2, the whole expression will be true since OR is taken of the two. Similarly, each part of the expression can be calculated independently, and then the result is combined. If the language definition permits portions of the expression to go unevaluated, the compiler can optimize the evaluation of boolean expression by computing only enough to determine its value. Suppose different OR expressions are present and any one of them becomes true, then the whole expression is considered true and the control will jump accordingly.

Another example can be the expression B1 && B2, if any of the B1 is false, then no need to determine the whole expression, the expression is false. If  B1 is true then only check for B2, if B2 is also true, only then the expression is true. To check whether all parts of the boolean expressions should be evaluated or not we use semantic definitions. We will be discussing it below.

Also read About, Specifications of Tokens in Compiler Design and,Lexical Analysis in Compiler Design

Short-Circuit Code

The boolean operators &&, I I, and ! translate into jumps in short-circuit (or jumping) code. Instead of the operators appearing in the code, the value of a boolean expression is represented by a position in the code sequence.

For example: Consider the following boolean expression.

If ( a< 7 || a> 9 && a!=b) then a=0;

Here if any of the boolean expressions (a<7) or (a> 9 && a!=b) becomes true, then the expression a=0, will be executed. If the whole expression becomes false then the control will jump to the rest of the code. Let’s denote expression a=0, at Label L2, and the remaining part of the code at label L1. Label can be defined as a position where the control will jump after the evaluation of the expression. The jumping code for the above expression is given in the table below.

If a < 7 goto L2
If FALSE a > 9 goto L1
If FALSE a!=b goto L1
L2:  a = 0
L1:
                               Jumping code


First the expression a<7 is checked if its true control will directly jump to label L2 and expression a=0 will be executed. It is because the expression is in OR with the rest of the expression. But if a<7 comes to false, then the other expression will be checked part-wise. Since there is an &&(and) operation in the second part first the expression a>9 will be checked if it is false, no need to evaluate the remaining expressions, the whole expression will result in false, and control will jump to label L1. If a>9 is true, then the remaining part of the expression is checked (a!=b), if it is false the whole expression again will become false and control will jump to label L1. Else if both expressions( a> 9 && a!=b) are true, then the control will jump to label L2.

Also See, Top Down Parsing

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

Flow-of-Control Statements

Now let’s look at how boolean expressions are translated into three-address code in the context of statements like the ones generated by the grammar below:

S → if(X) S1

 S → if(X) S1 else S2

 S → while(B) S1

                        Grammar for the flow of control statements

Here nonterminal X represents a boolean expression, and nonterminal S represents a statement.           

The above three statements are the grammar of flow-of-control statements, first production contains the if statement, the second contains if-else, and the third production contains the while statement. The three address codes for all three grammars can be generated with the help of the diagram given below.

Illustration Image

Let’s see figure (a) for ‘if’ code. B.code is the synthesized attribute for B. B.code can return two types of value- true and false. If it returns true then the control will jump to label B.true and S1.code is executed. If B.code returns false control will jump to label B.false the remaining part of the code.

For ‘if-else’, see figure (b) above. If B.code is true then a new label B.true is created and statement S1.code is executed, for B.false S2.code is executed. And then the remaining code S.next will be executed.

For ‘while’( see figure c), if B.code is true then S1.code will be executed and control will again jump to label begin and the condition for B.code will be checked. It is done until B.code becomes false and then the remaining code will be executed( control will jump to label B.false).

With the help of the above block diagrams, we can write semantic rules for the flow of control statements. The semantic rules for some productions are given below.

Illustration Image

Control-Flow Translation of Boolean Expressions

A boolean expression is translated into three address instructions that evaluate the expression using create labels only when they are needed. Alternatively, unnecessary labels can be eliminated during the subsequent optimization phase. The semantic rules for different expressions are given in the diagram below.

Illustration Image

Also see, Phases of Compiler

Avoiding Redundant Gotos

The goto statements alter the flow of control. If we implement goto statements, we need to define a Label for a statement. In the production system, semantic action is attached to record the Label and its value in the symbol table. Production can be added as

S →     LABEL: S  

    LABEL →     id  

With the inherited labels and following proper rules, multiple instructions can generate a single instruction. 

Boolean Values and Jumping Code

A boolean expression can be used to alter the flow of control in statements. A boolean expression can also be evaluated for its value, as in an assignment statement such as p=true; or x= y<z.

A clean way to handle both roles of boolean expressions is to build a syntax tree for expressions, using any of the following rules:

  1. Use two passes to construct a complete syntax tree for the input, and then walk the tree in depth-first order, translating the changes specified by semantic rules.
  2. Use one pass for statements but two passes for expressions.

Frequently Asked Questions

What is compiler design?

Compiler Design is the structure and set of principles that guide the translation, analysis, and optimization process of a compiler.

What is meant by the term ‘control flow’?

The control flow is the sequence in which the computer executes a script's statements.

Why is a control flow important?

Control flow allows you to tell your program when and how to run different pieces of code.

What are jump statements?

Jump statements are a type of Control Statements used to interrupt the normal flow of the program.

What is an intermediate code?

An internal form of a program created by the compiler while translating the program from a high-level language to assembly code(or)object code is known as an intermediate code.

Conclusion

In this article, we have extensively discussed ‘Control Flow’ in compiler design. We hope that this blog has helped you enhance your knowledge regarding control flow.

Recommended Reading:

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Code360.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts.

Cheers!