c - 在 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]='\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 集合中。因此，FIRST 集合中会有重复的终端。

• 程序只检查右侧的第一个符号。但是，如果非终结符可以产生 ε(换句话说，非终结符是可空)，则还需要使用以下符号来计算 < strong>第一个集合。

  例如，

  A → B C d
  B → b | ε
  C → c | ε
  

  在这里，FIRST(A) 是 {b, c, d}。 (同样，FOLLOW(B) 是 {c, d}。)

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

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

2. 使用上面的方法，将每个非终结符 N 的 FIRST(N) 初始化为 leading N 的每个产品的符号。如果一个符号是右侧的第一个符号，或者如果它左边的每个符号都可以为空，则该符号是产生式的前导符号。 (这些集合将同时包含终端和非终端；暂时不要担心。)

3. 执行以下操作，直到在循环期间没有更改FIRST 集:

   • 对于FIRST(N)中的每个非终结符N，对于每个非终结符M，将 FIRST(M) 中的每个元素添加到 FIRST(N)(当然，除非它已经是出席)。

4. 从所有 FIRST 集中删除所有非终结符。

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

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