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:
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:
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 Algorithms, Competitive Programming, Basics of C, Basics 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 Amazon, Adobe, Google, etc., on Coding Ninjas Studio.
Cheers!
84+ registered