1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

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.