假设我们有一个简单的语法规范.有一种方法可以枚举该语法的术语,通过对角迭代来保证任何有限项都具有有限的位置.例如,对于以下语法:
S ::= add
add ::= mul | add + mul
mul ::= term | mul * term
term ::= number | ( S )
number ::= digit | digit number
digit ::= 0 | 1 | ... | 9
您可以枚举这样的术语:
0
1
0+0
0*0
0+1
(0)
1+0
0*1
0+0*0
00
... etc
我的问题是:有没有办法做相反的事情？也就是说,采用该语法的有效术语,比如说0+0*0,并在这样的枚举中找到它的位置 - 在这种情况下,9？