World's most popular travel blog for travel bloggers.

# How to choose symbols to replace for this left-most derivation?

, ,
Problem Detail:

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:

\$E⇒E+T⇒T+T⇒F+T⇒a+T\$
\$⇒a+F⇒a+(E)⇒a+(T)\$
\$⇒a+(T×F)⇒a+(F×F)\$
\$⇒a+(a×F)=a+(a×a)\$

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:

\$E⇒E+T\$

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

\$⇒T+T\$

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

\$⇒F+T\$

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.

Question Source : http://cs.stackexchange.com/questions/55649

3200 people like this