I'm learning the basics of grammars and compilers for a comparative programming languages class, but having a bit of trouble with one aspect of grammar derivation.
Here is an example of a grammar derivation in a Youtube lecture I found. I get everything he covers here except that it isn't clear to me how a derivation is chosen when there are multiples available.
For example, in the video he constructs a grammar E that has productions E + E
, E * E
, and id
. I'm assuming that the correct derivation is chosen by pattern matching the input string to the grammar but that isn't made clear, nor is it really made clear in other sources I've read and watched. The derivation used at a given step sometimes seems arbitrarily chosen.
My reason for asking is because if it isn't matched to the input pattern, what is to keep his grammar from expanding an E into the (arbitrarily chosen) non-terminal production E + E
infinitely, and never reach a terminal condition?
Edit Related question:
On the bottom of this page there is a discussion of leftmost and rightmost derivation. In the leftmost derivation example, how does it know the correct derivation to use to move from the second to third derivation? In other words, how does it know to make this derivation: a+X → a+ X*X
Why couldn't it just derive a+X → a+a
and terminate? I know it doesn't match the input string, but what actually prevents that incorrect derivation from being chosen?