Menu
Please help me understand what is meant by Left Most Derivation the second L in LL Parser.
Explain it with a simplest example.
I saw the following picture explaining Left most derivation but I do not understand it :
583
Leftmost derivation − A leftmost derivation is obtained by applying production to the leftmost variable in each step. Rightmost derivation − A rightmost derivation is obtained by applying production to the rightmost variable in each step.
If the sentential form of an input is scanned and replaced from left to right, it is called left-most derivation. The sentential form derived by the left-most derivation is called the left-sentential form.
In a leftmost derivation, at each step the leftmost nonterminal is re- placed. In a rightmost derivation, at each step the rightmost nonter- minal is replaced.
There are three types of Derivation trees; Leftmost Derivation tree. Rightmost derivation tree. Mixed derivation tree.
The grammar rules are displayed on the left with Nonterminal symbols and terminal symbols. Nonterminal symbols should be Capital letters, everything else is typically a terminal symbol. In the example N and D are nonterminal and 0-9 are terminals. A Left Most Derivation ALWAYS makes the left most nonterminal go through a grammar rule. Trying to format the example below.
N
=> N D --Replaces the first/left most/only (which is "N") with the N => N D rule
=> N D D --Replaces the first/left most nonterminal (which is "N") with the N => N D rule
=> D D D --Replaces the first nonterminal (which is "N") with the N => D rule
=> 1 D D --Replaces the first nonterminal ("D") with the D => 1 rule(our first terminal character!)
=> 1 2 D --Replaces the first nonterminal ("D") with the D => 2 rule
=> 1 2 3 --Replaces the first nonterminal ("D") with the D => 3 rule
-- Only terminal characters remain, derivation/reduction is complete.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
