Suppose we have a simple grammar specification. There is a way to enumerate terms of that grammar that guarantees that any finite term will have a finite position, <a href="http://lukepalmer.wordpress.com/2008/05/02/enumerating-a-context-free-language/">by iterating it diagonally</a>. For example, for the following grammar:
You can enumerate terms like that:
My question is: is there a way to do the opposite? That is, to take a valid term of that grammar, say,
, and find its position on such enumeration - in that case, 9?
Code:
S ::= add
add ::= mul | add + mul
mul ::= term | mul * term
term ::= number | ( S )
number ::= digit | digit number
digit ::= 0 | 1 | ... | 9You can enumerate terms like that:
Code:
0
1
0+0
0*0
0+1
(0)
1+0
0*1
0+0*0
00
... etcMy question is: is there a way to do the opposite? That is, to take a valid term of that grammar, say,
Code:
0+0*0