# How many syntax trees can be made by a BNF

An example of this would be:

1+2*3+4

Expression = Expression Arithmetic Expression | number

Arithmetic = + | - | * | /

Through just breaking down 1+2*3+4, it was easy to find that the answer was 5 trees.

1. 1+((2*3)+4)

2. ((1+2)*3)+4

3. 1+(2*(3+4))

4. (1+2)*(3+4)

5. (1+(2*3))+4

But doing it in this brute force manner wouldn't work on larger more complex BNFs.

I have tried using CYK to get 5 but haven't figured out how, even through they do seem similar enough. Any advice on using any algorithms or strategies to break down larger BNFs to see how many syntax trees they can make would be much appreciated.

The answer is given by the Catalan numbers; if you have $$n$$ operators, the number of syntax trees is $$\frac{1}{n+1}{2n \choose n}$$. The problem is equivalent to finding all ways of inserting $$n$$ parentheses pairs in a word of $$n+1$$ letters, as mentioned in OEIS: