Left and Right Derivation

• Aim

  To design an online Lexical Analyzer simulator to derive leftmost derivation tree and rightmost derivation tree from a given grammar for a goal string.

• Programming Languages Used

  • HTML
  • CSS
  • JavaScript

• Theory

  The process of deriving a string is called as derivation. The geometrical representation of a derivation is called as a parse tree or derivation tree.

  Properties of Parse Tree

  • Root node of a parse tree is the start symbol of the grammar.
  • Each leaf node of a parse tree represents a terminal symbol.
  • Each interior node of a parse tree represents a non-terminal symbol.
  

  Leftmost Derivation:

  The process of deriving a string by expanding the leftmost non-terminal at each step is called as leftmost derivation.

  Rightmost Derivation:

  The process of deriving a string by expanding the rightmost non-terminal at each step is called as rightmost derivation.

• Program Logic

  • We start from Starting symbol and represent it as the root node.
  • We check for input symbol and start expanding according to the given grammar.
  • We start elaborating the production i.e., expanding the non-terminals from left to right in case of leftmost derivation tree and from right to left in case of rightmost derivation tree.
  • Similarly, we move the expansion for all the production until we achieve the goal string.

• Examples

  Let's consider a Grammar:
  S → aB / bA
  S → aS / bAA / a
  B → bS / aBB / b
  Let us consider a string
  w = aaabbabbba

  Leftmost Derivation:

  S → aB
  → aaBB (Using B → aBB)
  → aaaBBB (Using B → aBB)
  → aaabBB (Using B → b)
  → aaabbB (Using B → b)
  → aaabbaBB (Using B → aBB)
  → aaabbabB (Using B → b)
  → aaabbabbS (Using B → bS)
  → aaabbabbbA (Using S → bA)
  → aaabbabbba (Using A → a)
  

  Leftmost Derivation Tree:

  

  Rightmost Derivation:

  S → aB
  → aaBB (Using B → aBB)
  → aaBaBB (Using B → aBB)
  → aaBaBbS (Using B → bS)
  → aaBaBbbA (Using S → bA)
  → aaBaBbba (Using A → a)
  → aaBabbba (Using B → b)
  → aaaBBabbba (Using B → aBB)
  → aaaBbabbba (Using B → b)
  → aaabbabbba (Using B → b)
  

  Right Derivation Tree:

  

• Online Simulator

  Click on this Link to go to the simulator.

• Discussion

  We wrote the online simulator using HTML, CSS, JavaScript and successfully implemented the concept of left and right derivation tree.

• Sources of Errors

  If the grammar is ambiguous i.e., if there exist more than one left or right derivations for the same string. For an ambiguous grammar left and right derivation tree of a given grammar may yield different results.