Let’s suppose the following grammar:
S → variable = math_expr variable → a | b | c math_expr → INT | function math_expr → func_1() | func_2(INT, INT, INT, INT) INT → 1 | 2 | 3 | 4 | 5
Since this grammar cannot generate an infinite number of programs (you should assume this for my problem), I want to know if there is some kind of formula that calculate the number of COMPLETE and INCOMPLETE programs that can be generated by a finite grammar.
In my own definition, a complete program is a program that does not have non-terminal nodes.
b = func_2(2,4,3,3),
a = func_1()
An incomplete program is a program that does have non-terminal nodes.
b = func_2(2,2,INT,INT),
c = math_expr,
At the moment, I am able to know the number of complete and incomplete programs by applying a Breadth-First Search (BFS) starting from the
However, because I’m working with search in program synthesis, it would be great to know the size of the domain without the need to do an exhaustive search on it.
How can I find the number of complete and incomplete programs given only the grammar?
PS.: In my original problem, I am working with program synthesis with a Domain Specific Language (DSL). I tagged CFG with the hope that the same applies, granted I’m not 100% sure.