Cheap and Secure Web Hosting Provider : See Now

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

, , No Comments
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:

I start with:

$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)$?

Asked By : cpx
Answered By : Raphael

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.

Best Answer from StackOverflow

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

3200 people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback