Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Operations Within Expressions
3.
Incremental Translation
4.
Frequently Asked Questions
4.1.
What is the purpose of a compiler?
4.2.
What is the objective of learning compiler design?
4.3.
How many types of Compilers are there?
4.4.
What kind of tools are needed in order to design a compiler?
4.5.
Who wrote the first compiler?
5.
Conclusion
Last Updated: Mar 27, 2024
Easy

Translation Of Expressions

Author Shiva
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @
Compiler Design

Introduction

Before reading this article, it is recommended to have a decent understanding of parsing and three-address code in compiler design. I will cover them briefly in this article still it is recommended for better understanding. The assignment statement is used to deal with expressions in syntax-directed translation. The type of the expression can be real, integer, array, or record.

A multi-operator expression, such as a + b* c, will be translated into instructions with only one operator per instruction. There can only be one operator on the right side of instruction in a three-address code; no built-up arithmetic expressions are allowed. As a result, a source-language statement like x+y*z might be translated into a three-address instruction sequence.

 t1 = y*z

 t2= x+t1

Where t1 and t2 are temporary names produced by the compiler.

Also See, Top Down Parsing

Operations Within Expressions

Using attribute code for S and attributes addr and code for an expression E, the syntax-directed definition in the below figure constructs the three-address code for an assignment statement S. S.code and E.code are attributes that represent the three-address code for S and E, respectively.

Three Address Code Generation

This is the translation schema.

Consider the last production, E ->• id, in the syntax-directed definition in the figure above.

  • top denote the current symbol table.
  • Function top.get retrieves the entry
  • Attribute E.addr denotes the address that will hold the value of E.
  • new Temp() creates t1, t2 …
  • gen(x’=’ y ‘+’ z) represents the 3-address instruction x=y+z. Expression appearing in place of variables like x, y, and z are evaluated when passed to gen
     

Advantage: No code generated for variable access

Disadvantage: Not good with side effects. Eg. x-(x=3)

 

In Fig. 6.19, the operators + and unary - reflect the operators in a typical language. The semantic rules for E —> E1 + E2 create code to compute E's value from E1 and E2's values. Values are computed and stored in temporary names that are formed on the fly. E1 + E2 translates to t = E1. addr + E2. addr, where t is a new temporary name, if E1 is computed as Ei.addr and E2 is computed as E2. addr. The value of E.addr is set to t. By repeatedly performing n e w Tempi), a succession of separate temporary names ti,t2,... is formed.
 

To denote the three-address instruction x = y + z, we use the notation gen(x '=' y '+' z). When provided to gen, expressions that appear in place of variables like x, y, and z are evaluated, and quoted strings are taken literally. 5 Other three-address instructions will be constructed in the same way. 5 In syntax-directed definitions, gen creates and returns an instruction.
 

By applying gen to a combination of expressions and strings, gen constructs an instruction and incrementally emits it by placing it into the stream.

When we translate E -> Ei+E2, the semantic rules in Fig. 6.19 combine Ei.code, E2.code, and an instruction that adds the values of E1 and E2 to create E.code. The instruction saves the result of the addition as E.addr, a new temporary name for E.

E -» - E1 has a similar translation. The rules provide instruction to do the unary minus operation and build a new temporary for E.

Finally, the production is completed. S id = E; creates instructions that assign the expression E's value to the identifier id. As with the rules for E —v id, the semantic rule for this production employs function top.get to find the address of the identifier represented by id. S.code contains instructions to compute E's value into an address specified by E.addr, followed by an assignment to top.get(id. lexeme) for this instance of id.
 

Example 6.11: In figure above 6.19, the syntax-directed definition converts the assignment phrase a = b + - c; into a three-address code sequence.

Illustration Image

a=b+-c

=> t2 = minus c

t1= b+t1

a= t2

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

Incremental Translation

The syntax-directed specification in Fig. 6.19 generates the same code as the translation scheme in Fig. 6.20. The code property is not needed in the incremental technique since a single sequence of instructions is formed by successive calls to gen. The semantic rule in Fig. 6.20 for E ->• E1 + E2 merely calls gen to construct an add instruction; the instructions to calculate Ei into Ei.addr and E2 into E2.addr have already been generated.

A syntax tree can also be built using the method shown in Fig. 6.20. The new semantic action for E — > E1 + E2 uses a constructor to produce a node, similar to generated instructions.

E.addr = new Node("+', E1.addr, E2.addr); E — > Ei + E2 E.addr = new Node("+', E1.addr, E2.addr);

 

The syntax-directed specification in Fig. 6.19 generates the same code as the translation scheme in Fig. 6.20. The code attribute is not used in the incremental technique because a single sequence of instructions is formed by successive calls to gen. The semantic rule in Fig. 6.20 for E ->• E1 + E2 merely calls gen to construct an add instruction; the instructions to compute Ei into Ei.addr and E2 into E2.addr have already been generated.

 

A syntax tree can also be built using the method shown in Fig. 6.20. The new semantic action for E — > E1 + E2 uses a function Object() { [native code] } to create a node, similar to how generated instructions do.

Three Address Code Generation

Read about Instruction Format in Computer Architecture

Frequently Asked Questions

What is the purpose of a compiler?

A compiler converts code written in one language into code written in another without affecting the program's meaning. A compiler should also make the target code efficient and optimized in terms of both time and space.

What is the objective of learning compiler design?

A well-balanced mix of software and hardware constitutes a computer. Hardware recognizes electrical charge instructions, which are the software programming equivalent of binary language. In binary, there are only two letters: 0 and 1. In order to instruct, the hardware instructions must be encoded in binary format, which is just a sequence of 1s and 0s. For computer programmers, writing such programs would be difficult and time-consuming, which is why compilers exist.

How many types of Compilers are there?

We can broadly categorize it into 3 types: Single Pass, Two-pass, and Muti-Pass.

What kind of tools are needed in order to design a compiler?

Common tools that are required: Parser Generator, Scanner Generator, Syntax directed translation engines, Automatic code generators, Data-flow analysis engines, Compiler construction toolkits.

Who wrote the first compiler?

Admiral Grace Murray Hopper's achievements, which include the creation of the Compiler, cemented her place at the vanguard of the early 1940s computer revolution. Her mathematics career spanned six decades.

Conclusion

In this article, we have extensively discussed the Translation of Expressions in Compiler Design. We hope that this blog has helped you enhance your knowledge regarding the IPR 

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 Coding Ninjas Studio.

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 only on Coding Ninjas Studio.

Cheers!

Previous article
Types and Declarations
Next article
Control Flow
Live masterclass