I need to draw the derivation tree for $1-2-(3-4)*5*6$ from the grammar below. I want to know how many possible derivation trees are there from this grammar.

$$\begin{align}V_n&=\{expr,term,factor,number\}\\ V_t&= \{(,),-,*,0...9\}\\ P&=\left \{ \begin{aligned} expr&\to expr-expr\;\mid\;term\\ term&\to term*factor\;\mid\;factor\\ factor&\to number \;\mid\; (expr) \\ number&\to 0\mid1\mid2\mid3\mid4\mid5\mid6\mid7\mid8\mid9 \end{aligned} \right \}\\ S&=expr \end{align} $$

The possibilities that I can find are:

$$(1-2)-(((3-4)*5)*6)\\ 1-(2-( ((3-4)*5) *6))$$

Are there other possibilities?

  • 1
    $\begingroup$ Welcome to Computer Science! Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. $\endgroup$ – dkaeae Jul 9 at 11:41
  • $\begingroup$ @dkaeae hello im trying to edit it $\endgroup$ – Devina Muljono Jul 9 at 15:03
  • $\begingroup$ Also posted on Mathematics. Please do not post the same question on multiple sites. Each community should have an honest shot at answering without wasting anybody's time. If you don't get a satisfying answer after a week or so, you may flag to request migration. $\endgroup$ – Apass.Jack Jul 10 at 16:05
  • $\begingroup$ @Apass.Jack I disagree. Mathematicians might be interested in this problem as well in my opinion, in particular Theoretical Computer Science topics. You posted an accepted answer (which does not mean that it is the rule), I feel free to post one of the answers to that question, which shows in some cases it can be ok: meta.stackexchange.com/a/234946/292908 $\endgroup$ – Ely Jul 11 at 13:49
  • $\begingroup$ @Ely I have not posted an answer to the current question on either site. So I could not understand when you said, "You posted an accepted answer". You are encouraged to post your answer on either site or both sites. You are especially encouraged to post your answer on this site since questions about parsing of formal languages is more proper to this site. $\endgroup$ – Apass.Jack Jul 11 at 14:59

No, there are no other possibilities as far as I can see.

The ambiguity comes from the production rule $expr \rightarrow expr - expr$. This rule allows you to derive the expression in two different ways:

  1. Derive $1$ from the left $expr$ and the rest from the right $expr$
  2. Derive $1-2$ from the left $expr$ and the rest from the right $expr$

Some ideas that might help.

The precedences look ok to me; the lower the precedence the closer the operator should be to the root (in this case $expr$).
- has the lowest (derived from $expr$), * has a higher precedence (derived from a production after $expr$).
And the parentheses (...) have the highest (derived from a production after $term$).

The $term$ production rule is left associative, which helps avoid the ambiguity of associativity.

The $expr$ production rule is the problem as mentioned above. A solution to that would be similar to what you see for the $term$ production rule. Make it left associative.

  • $\begingroup$ Thankyou so much!! Clear my confusion!!!! :D $\endgroup$ – Devina Muljono Jul 16 at 14:15

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.