Leftmost
Derivation
During a
leftmost derivation step
, the
leftmost nonterminal is rewritten.
Definition:
Let
G
= (
N
,
T
,
P
,
S
) be a CFG
, let
u
Î
T
*
,
v
Î
(
N
È
T
)
*
. Let
p
=
A
®
x
Î
P
be a
rule
.
Then,
u
A
v
directly derives
u
x
v
in the
leftmost way
according to
p
in
G
, written as
u
A
v
Þ
lm
u
x
v
[
p
]
Note:
We d
efine
Þ
lm
+
and
Þ
lm
*
by analogy with
Þ
+
and
Þ
*
, respectively.
Gist:
12/50