How do we read the input string in the rightmost derivation?
Question
How do we read the input string in the rightmost derivation?
Solution
In the rightmost derivation, we read the input string from left to right. Here are the steps:
-
Start with the start symbol on the left.
-
Choose a non-terminal symbol in the current string. In rightmost derivation, we always choose the rightmost non-terminal symbol.
-
Replace the chosen non-terminal symbol with one of its production rules from the grammar. This will give you a new string.
-
Repeat steps 2 and 3 until you get the input string. If you can't get the input string, then the input string is not derivable from the grammar.
-
If you can get the input string, then the input string is derivable from the grammar, and the sequence of strings you got is a rightmost derivation of the input string from the grammar.
Similar Questions
Which derivation is used to generate a string by the bottom up parser?Right-most derivation in reverseLeft-most derivation in reverseRight-most derivationLeft-most derivation
The input is scanned and replaced with the production rule from left to right in the ____ derivation.
A top down parser generates ____a) Rightmost Derivation b) Right most derivation in reverse c) Left most derivation d) Left most derivation in reverse
For the grammar E -> E + E | E * E | a, select all leftmost derivations for the string a+a*a1 pointE => E + E => E + E * E => E + E * a => E + a * a => a + a * aE => E + E => E + E * E => a + E * E => a + a * E => a + a * aE => E * E => E + E * E => E + E * a => E + a * a => a + a * aE => E * E => E + E * E => a + E * E => a + a * E => a + a * a
The derivation tree is also known as ____.
Upgrade your grade with Knowee
Get personalized homework help. Review tough concepts in more detail, or go deeper into your topic by exploring other relevant questions.