Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Derivation
3.
Left-most Derivation
4.
Right-most Derivation
5.
Frequently Asked Questions
5.1.
What is the purpose of derivation in compiler design?
5.2.
What is the relationship between derivation and parsing?
5.3.
Can derivation be applied to any input string?
6.
Conclusion
Last Updated: Mar 27, 2024

Derivation in Compiler Design

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

Introduction

The derivation is the guiding light that guarantees code follows a programming language's grammar rules. It examines each character and symbol meticulously, validating their placement and relationships within the syntax of the code.

derivation in compiler design

 

In this article, we'll take a look at the Derivation in Compiler Design and its types.

Derivation

A Derivation in compiler design is the successive application of production rules to produce the desired input string. For each sentential form of the input, two critical choices are made throughout the parsing process:

  • Choosing the Non-terminal: This choice entails deciding which sentential form non-terminal symbol needs to be changed next. It is essential for getting closer to the intended input string.
     
  • Selection of the Production Rule: After the non-terminal has been decided upon, the next choice is the production rule that will take its place. The production rule determines the change that occurs, which causes the sentential form to expand.
     

These choices are iterative and keep being made up until the complete input string has been determined. The objective is to find a valid chain of production rule applications that generate the desired input string while adhering to the programming language's grammar rules. The structure and accuracy of the final parse tree or abstract syntax tree are greatly influenced by each choice made throughout the derivation process.

There are two types of derivation in compiler design: 

  • Left-most Derivation
     
  • Right-most Derivation
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

Left-most Derivation

The left-most derivation is a method of transforming an input string according to the grammar rules of a programming language. The leftmost non-terminal is selected at each stage of left-most derivation, and its expansion is governed by the production rule associated with that non-terminal. This operation continues from left to right, matching the scan of the input string from left to right.

A more formal definition would be, A leftmost derivation A⇒*w is one where we apply productions only to the leftmost variable at each step. The asterisk (*) indicates zero or more derivations.

Grammar:

S -> AB

A -> a

B -> b

Example

Input: ab

Parse Tree: 

LeftMost Derivation parse tree

To derive the input string "ab" using left-most derivation, the steps would be as follows:

S (Start symbol)

AB (Using production rule S -> AB)

aB (Using production rule A -> a)

ab (Using production rule B -> b)

Explanation:

  • We begin with the start symbol S.
     
  • In the first step, we replace S with the production rule S -> AB to match the non-terminal A in the input string.
     
  • Then, in the second step, we replace A with the production rule A -> a to match the first character "a" in the input string.
     
  • Finally, in the third step, we replace B with the production rule B -> b to match the second character "b" in the input string.

Right-most Derivation

Just like left-most, the right-most derivation is a method for transforming an input text depending on the grammar rules of a programming language. 

The emphasis in the right-most derivation is on the rightmost part of the input string that hasn't yet been processed. The rightmost non-terminal is selected for expansion at each step, which is regulated by the production rule associated with that non-terminal. This procedure proceeds from right to left, matching the scanning of the input string from right to left.

A more formal definition would be, A rightmost derivation A⇒*w is a type of derivation where, at each step, we consistently choose the rightmost non-terminal symbol to expand using a production rule. This process is also referred to as a canonical derivation.

Grammar:

S -> AB

A -> a

B -> b

Example

Input: ab

Parse Tree:

Rightmost derivation tree

To derive the input string "ab" using right-most derivation, the steps would be as follows:

S (Start symbol)

AB (Using production rule S -> AB)

Ab (Using production rule B -> b)

ab (Using production rule A -> a)
 

Explanation:

  • We begin with the start symbol S.
     
  • In the first step, we replace S with the production rule S -> AB to match the non-terminal B in the input string.
     
  • Then, in the second step, we replace B with the production rule B -> b to match the second character "b" in the input string.
     
  • In the third step, we replace A with the production rule A -> a to match the first character "a" in the input string.


Also see,  cousins of compiler

Frequently Asked Questions

What is the purpose of derivation in compiler design?

The derivation ensures that the input string complies with the syntactic rules established by the grammar of a computer language. It aids in language recognition, mistake detection, and the creation of parse trees or abstract syntax trees that depict the organisation of the code.

What is the relationship between derivation and parsing?

The derivation is closely related to parsing, which is the process of examining a string's syntactic structure using grammatical rules. The derivation is a transformation procedure utilised during parsing to verify that the input string can be derived from the grammatical rules.

Can derivation be applied to any input string?

If an input string follows the grammar rules given by the computer language, derivation can be applied. The derivation procedure may be impossible if the input string violates grammar rules or is not recognised by the language's grammar.

Conclusion

This article covered everything you needed to know about Derivation in Compiler Design and its types, i.e. Left-most and Right-most derivation, with an example. We also looked at some frequently asked questions.

Recommended Readings:


Check out some amazing Guided Paths on topics such as Data Structure and AlgorithmsCompetitive ProgrammingBasics of CBasics of Java, etc., along with some Contests and Interview Experiences only on Coding Ninjas Studio

Do check out The Interview Guide for Product Based Companies, as well as some of the Popular Interview Problems from Top companies like AmazonAdobeGoogle, etc., on Coding Ninjas Studio.

Cheers!

Previous article
Parsing in Compiler Design
Next article
LALR Parser in Compiler Design
Live masterclass