Aim:-

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

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

Input/Output Examples:-

Consider the following Grammer:.

Left Derivation:

Right Derivation:

Online Simulator:-

Click on this Link to go to the Online Simulator.

Discussion:-

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

Source of Error & Error Recovery:-

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. .