关于相互递归调用
递归 关于 调用 相互
2023-09-27 14:27:45 时间
在编译原理的语法分析中，很多文法都是递归形式给出的。
假设有如下文法：
G[F]:
F→fG
G→gF
判断字符串 a 是否满足的程序如下：
int F(int pos) { if(a[pos] == 'f') return G(pos+1); return -1; } int G(int pos) { if(a[pos] == 'g') return F(pos+1); return -1; } int main(){ //freopen("1.in","r",stdin); while(cin>>a){ printf("%d\n", F(0)); } return 0; }
易知，这个程序输出总为 -1，因为不存在有限长的 F，F = fgF.
反过来，要想结果输出的不是 -1，F的结果是G(pos+1)，G的结果又是F，不可能从这个圈推出。
如果我们给 F/G 增加一个可行出口，就能找到满足条件的有限长的字符串。
例如文法改成：
G[F]:
F→fG | a
G→gF
int F(int pos) { if(a[pos] == 'a') return pos+1; if(a[pos] == 'f') return G(pos+1); return -1; } int G(int pos) { if(a[pos] == 'g') return F(pos+1); return -1; }
此时，像 fgfga 这样的就满足条件了。
可见，相互递归调用有可行输出的条件是，一个函数的可行输出不是唯一的。