I have a context free grammar such as the following:

$E→E+T | T$
$T→T×F | F$
$F→(E) | a$

Using the left-most derivation, the following can be derived:


I know what the left most derivation is and I know what the grammar notation means but what I am trying to understand is how should I substitute the symbols in correct order? For example:

I start with:


I substitute 'E' first on the left and it becomes:


Then I need to substitute $T$ on the left and it becomes:


Why $T×F$ wasn't chosen to replace $T$ and why $F$ in this case?

Also, in the very next step $F$ was replaced by $a$ and why it wasn't replaced by $(E)$?


The term "left-derivation" only pertains to choosing the left-most non-terminal in the sentential form.

It does not force you to choose the left-most rule; that would be silly since the rules are a set, i.e. they are unordered. Also, you couldn't derive that word at all then, now wouldn't you?

Also, keep in mind that there is no "choosing" going on. This is not a parsing algorithm; grammars only give you a declarative definition of languages. There exists a derivation that results in that word, and the one you have is an example.

Note that there are ambiguous grammars, that is grammars that have multiple left-most derivations for some words.

If you are really asking about how to find syntax trees algorithmically, take your pick; there are a lot, and then some.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.