CSharp  Java  Python  Swift  GO  WPF  Ruby  Scala  F#  JavaScript  SQL  PHP  Angular  HTML
DerivationDerivation is a sequence of production rules. It is used to get the input string through these production rules. During parsing, we have to take two decisions. These are as follows:
We have two options to decide which nonterminal to be placed with production rule. 1. Leftmost Derivation:In the leftmost derivation, the input is scanned and replaced with the production rule from left to right. So in leftmost derivation, we read the input string from left to right. Example:Production rules: E = E + E E = E  E E = a  b Input a  b + a The leftmost derivation is: E = E + E E = E  E + E E = a  E + E E = a  b + E E = a  b + a 2. Rightmost Derivation:In rightmost derivation, the input is scanned and replaced with the production rule from right to left. So in rightmost derivation, we read the input string from right to left. ExampleProduction rules: E = E + E E = E  E E = a  b Input a  b + a The rightmost derivation is: E = E  E E = E  E + E E = E  E + a E = E  b + a E = a  b + a When we use the leftmost derivation or rightmost derivation, we may get the same string. This type of derivation does not affect on getting of a string. Examples of Derivation:Example 1:Derive the string "abb" for leftmost derivation and rightmost derivation using a CFG given by, S → AB  ε A → aB B → Sb Solution: Leftmost derivation: Rightmost derivation: Example 2:Derive the string "aabbabba" for leftmost derivation and rightmost derivation using a CFG given by, S → aB  bA S → a  aS  bAA S → b  aS  aBB Solution: Leftmost derivation: S aB S → aB aaBB B → aBB aabB B → b aabbS B → bS aabbaB S → aB aabbabS B → bS aabbabbA S → bA aabbabba A → a Rightmost derivation: S aB S → aB aaBB B → aBB aaBbS B → bS aaBbbA S → bA aaBbba A → a aabSbba B → bS aabbAbba S → bA aabbabba A → a Example 3:Derive the string "00101" for leftmost derivation and rightmost derivation using a CFG given by, S → A1B A → 0A  ε B → 0B  1B  ε Solution: Leftmost derivation: S A1B 0A1B 00A1B 001B 0010B 00101B 00101 Rightmost derivation: S A1B A10B A101B A101 0A101 00A101 00101
Next TopicDerivation Tree
