what is meant by left most derivation?

2020-07-08 03:53发布

问题:

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 :

回答1:

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.