I've been reading / studying formal grammars for the past few weeks and I came across a question that puzzled me and I cannot seem to get my head around it for some reason.
<expression> is the starting symbol
<expression> → <term> | <expression> + <term> | <expression> - <term>
<term> → <primary> | <term> * <primary> | <term> / <primary>
<primary> → a | b | c | d | e | f | g | h
(i) a/b-c/d*e+f
(ii) a+b*-c+d/e*f
and for each of the words, if it's a sentence in the grammar then I have to draw it's derivation tree. If it's not a sentence, I have to explain why it's not a sentence.
Would anyone be able to guide me through the question with examples please? What would the derivation trees for this look like? I've drawn some out on paper but I'm not certain they're even correct.
Best Answer
I’ll work an example with the expression
a*b/c+d-e*f. Note that plus and minus signs separate terms, while multiplication and division signs separate primaries within terms. Also, expressions generate their component terms from right to left: the rightmost term is the first one to be split off, via the productions<expression> → <expression> ± <term>. Similarly, terms generate their component primaries from right to left. Thus, when we try to match an expression to the grammar, we should do the same thing, and the expression therefore breaks down like the first tree below.This is not the parse tree, however; it’s just an aid to seeing how the expression breaks down into the kinds of pieces defined by the grammar. The second tree is the actual parse tree, showing the derivation of the expression including all of the non-terminal symbols.
In other words, the derivation begins
$$\langle\text{expression}\rangle\Rightarrow\langle\text{expression}\rangle-\langle\text{term}\rangle\;.\tag{1}$$
The
<expression>on the right-hand side of $(1)$ then expands by the derivation$$\langle\text{expression}\rangle\Rightarrow\langle\text{expression}\rangle+\langle\text{term}\rangle\;,$$
while the
<term>on the right-hand side of $(1)$ expands via$$\langle\text{term}\rangle\Rightarrow\langle\text{term}\rangle*\langle\text{primary}\rangle\;.$$
One of your exercises is quite similar; the other will prove not to be a sentence, because it contains a substring that cannot be generated by this grammar.