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+((2*3)+4)

((1+2)*3)+4

1+(2*(3+4))

(1+2)*(3+4)

(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:


  Number of ways to insert n pairs of parentheses in a word of n+1 letters. E.g., for n=2 there are 2 ways: ((ab)c) or (a(bc)); for n=3 there are 5 ways: ((ab)(cd)), (((ab)c)d), ((a(bc))d), (a((bc)d)), (a(b(cd))).


There are several ways to prove this, e.g. via the Dyck language. The Wikipedia article contains several ones.