在C中处理长递归生成时如何防止堆栈溢出？

Question

给定一个语法,在C中计算FIRST和FOLLOW时,如何避免堆栈溢出问题.当我不得不通过长时间的生产时,问题出现在我的代码中.

例:

S->ABCD
A->aBc | epsilon
B->Bc
C->a | epsilon
D->B

这只是一个语法.递归是这样的:

S->A
C->A
A->B
B->D
D->aBc | epsilon

FIRST(S)=FIRST(A)=FIRST(B)=FIRST(D)={a,epsilon}.  

提供一个C(而不是C++)代码来计算和打印上面的语法的FIRST和FOLLOW集合,记住你可能会遇到一个更长的语法,它具有特定非终端的多个隐含的第一/后续集合.

例如:

FIRST(A)=FIRST(B)=FIRST(B)=FIRST(C)=FIRST(D)=FIRST(E)=FIRST(F)=FIRST(G)=FIRST(H)=FIRST(I)=FIRST(J)=FIRST(K)={k,l,epsilon}.

那就是:让你得到FIRST(A)你算算FIRST(B),并依此类推,直至到达FIRST(K)具有其FIRST(K)具有终端'k','l'和epsilon.暗示越长,越有可能因多次递归而遇到堆栈溢出.
如何在C语言中避免这种情况并仍能获得正确的输出？
用C(不是C++)代码解释.

char*first(int i)
{
    int j,k=0,x;
    char temp[500], *str;
    for(j=0;grammar[i][j]!=NULL;j++)
    {
        if(islower(grammar[i][j][0]) || grammar[i][j][0]=='#' || grammar[i][j][0]==' ')
        {
           temp[k]=grammar[i][j][0];
           temp[k+1]='\0';
        }
        else
        {
            if(grammar[i][j][0]==terminals[i])
            {
                temp[k]=' ';
                temp[k+1]='\0';
            }
            else
            {
                x=hashValue(grammar[i][j][0]);
                str=first(x);
                strncat(temp,str,strlen(str));
            }
        }
        k++;
    }
    return temp;
}

我的代码转到堆栈溢出.我怎么能避免呢？

Answer 1

你的程序溢出堆栈不是因为语法"太复杂"而是因为它是左递归的.由于你的程序没有检查它是否已经通过非终端递归,一旦它尝试计算first('B'),它将进入无限递归,最终将填充调用堆栈.(在示例语法中,不仅是B左递归的,它也没用,因为它没有非递归生成,这意味着它永远不能导出只包含终端的句子.)

不过,这不是唯一的问题.该计划至少还有两个其他缺陷:

• 在将终端添加到集合之前,它不检查给定终端是否已经添加到非终端的FIRST集合中.因此,第一组中将有重复的终端.

• 该程序仅检查右侧的第一个符号.然而,如果非终端可以产生ε(换句话说,非终端可以为空),则还需要使用以下符号来计算第一组.

  例如,

  A ? B C d
  B ? b | ?
  C ? c | ?
  

  这里,FIRST(A)是{b, c, d}.(类似地,FOLLOW(乙)是{c, d}).

递归对FIRST和FOLLOW集的计算没有多大帮助.最简单的描述算法是这个,类似于龙书中提出的算法,它足以满足任何实际语法:

1. 对于每个非终端,计算它是否可以为空.

2. 使用上述内容,将每个非终端N的FIRST(N)初始化为N的每个生成的前导符号集.如果符号是右侧的第一个符号或者左侧的每个符号都可以为空,则符号是生产的前导符号.(这些集合将包含终端和非终端;暂时不用担心.)

3. 执行以下操作直到循环期间未更改FIRST集:

   • 对于每一个非末端Ñ,对于每个非末端中号在FIRST(Ñ),在添加每个元素FIRST(中号)到FIRST(ñ)(除非,当然,这是已存在).

4. 从所有FIRST集中删除所有非终端.

以上假设您有一个计算可空性的算法.你也会在龙书中找到这个算法; 它有点类似.此外,你应该消除无用的制作; 检测它们的算法与可空性算法非常相似.

有一种算法通常更快,实际上并不复杂得多.完成上述算法的第1步后,您已经计算了关系lead-with(N,V),当且仅当非终结N的某些生成从终端或非终端V开始时才是真的,可能跳过可以为空的非终端.FIRST(N)则是潜在的传递关闭-其域仅限于终端.可以使用Floyd-Warshall算法有效地计算(无递归),或使用Tarjan算法的变体来计算图的强连通分量.(例如,参见Esko Nuutila的传递封闭页面.)