在 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}.  
Provide a C (not C++) code that calculates and print FIRST and FOLLOW set of the grammar above keeping in mind that you might encounter a longer grammar that has multiple implicit first/follow sets of a particular non-terminal.

例如：

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}.

That is: for you to get FIRST(A) you have to calculate FIRST(B) and so on until you get to FIRST(K) that has its FIRST(K) has terminals 'k','l', and epsilon. The longer the implication, the more likely you will encounter stack-overflow due to multiple recursion.
How can this be avoided in C language and yet still get the correct output?
Explain with a C (not C++) code.

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]='[=14=]';
        }
        else
        {
            if(grammar[i][j][0]==terminals[i])
            {
                temp[k]=' ';
                temp[k+1]='[=14=]';
            }
            else
            {
                x=hashValue(grammar[i][j][0]);
                str=first(x);
                strncat(temp,str,strlen(str));
            }
        }
        k++;
    }
    return temp;
}

我的代码发生堆栈溢出。我怎样才能避免它？

Answer 1

您的程序溢出堆栈不是因为语法是 "too complex"，而是因为它是左递归的。由于您的程序不会检查是否已经通过非终端递归，一旦它尝试计算 first('B')，它将进入无限递归，最终将填满调用堆栈。（在例子文法中，不仅B是左递归的，而且没用因为它没有非递归产生式，也就是说永远不能推导出一个句子仅由端子组成。)

但这不是唯一的问题。该程序至少存在两个其他缺陷：

在将终端添加到集合之前，它不会检查给定的终端是否已经添加到非终端的 FIRST 集合中。因此，在 FIRST 组中会有重复的终端。
程序只检查右侧的第一个符号。但是，如果非终结符可以产生ε（换句话说，非终结符是nullable），则需要使用后面的符号以及计算 FIRST 集合。

例如，
```
A → B C d
B → b | ε
C → c | ε
```
这里，FIRST(A)是{b, c, d}。（同样，FOLLOW(B) 是 {c, d}。）

递归对 FIRST 和 FOLLOW 集的计算帮助不大。描述最简单的算法是这个，类似于Dragon Book中介绍的算法，它足以满足任何实用语法：

对于每个非终端，计算它是否可以为空。
使用上面的方法，为每个非终端 N 初始化 FIRST(N) 到 前导符号 的集合 N 的每个产品。如果一个符号是右侧的第一个符号，或者如果它左边的每个符号都可以为空，则该符号是产生式的前导符号。（这些集合将包含终端和非终端；暂时不要担心。）
执行以下操作直到在循环期间没有 FIRST 集被更改：
- 对于每个非终结符N，对于FIRST中的每个非终结符M (N)，将FIRST(M)中的每个元素添加到FIRST(N)（当然，除非它已经存在）。
从所有 FIRST 集合中删除所有非终结符。

以上假定您有计算可空性的算法。您也会在龙书中找到该算法；它有点相似。此外，您应该消除无用的产生式；检测它们的算法与可空性算法非常相似。

有一种算法通常速度更快，实际上也不会复杂多少。完成上述算法的第 1 步后，您就计算出了 leads-with(N, V)，当且仅当非终结符 N 的某些产生式以终结符或非终结符 V 开始时才成立，可能跳过可为空的非终端。 FIRST(N) 是 leads-with 的传递闭包，其域仅限于终端。这可以使用 Floyd-Warshall 算法或使用 Tarjan 算法的变体来有效计算（无需递归）来计算图的强连通分量。（参见，例如，Esko Nuutila's transitive closure page.）

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

How to prevent stack overflow when dealing with long recursive productions in C?

c

stack-overflow

compiler-construction

recursion

buffer-overflow