如何在處理C中的長遞歸生成時防止堆棧溢出？

給定一個語法，當計算C中的FIRST和FOLLOW集時，如何避免堆棧溢出問題。當我不得不通過長期生產遞歸時，問題出現在我的代碼中。如何在處理C中的長遞歸生成時防止堆棧溢出？

實施例：

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，並按照上文牢記語法，你可能會遇到有較長的語法一個特定的非終端的多個隱含的第一/後續集合。

例如：

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

我的代碼去堆棧溢出。我怎樣才能避免它？

來源

2016-03-01 K1b1w077

你的程序溢出堆棧不是因爲語法太「複雜」，而是因爲它是左遞歸的。由於你的程序不檢查它是否已經通過非終端遞歸，一旦它試圖計算first('B')，它將進入無限遞歸，這將最終填充調用堆棧。（在本例中的語法，不僅是B左遞歸，也沒用因爲它沒有非遞歸的生產，這意味着它不能獲得僅由終端的句子。）

這不是唯一的問題，但。該計劃從至少兩個其他缺陷所害：

如果給定的終端已經加入終端的集之前添加到FIRST一套用於非終端它不檢查。因此，將會有重複的終端在FIRST集合中。
該程序只檢查右側的第一個符號。但是，如果一個非終端可以產生＆epsilon; （換句話說，非終端是，可空的），以下的符號也需要用來計算集合FIRST集合。

例如，
```
A → B C d 
B → b | ε 
C → c | ε 
```
這裏，FIRST（甲）是{b, c, d}。（同樣，FOLLOW（乙）是{c, d}。）

遞歸沒有太大的幫助與FIRST和FOLLOW套計算。來描述最簡單的算法是這一個，類似於在Dragon Book提出的算法，這將足以滿足任何實際語法：

對於每個非末端，計算其是否爲空。
使用上述，初始化FIRST（Ñ）對於每個非末端Ñ該組主導符號每個生產Ñ。如果一個符號是右邊的第一個符號或者左邊的每個符號都是可以爲空的，那麼符號就是生產的主要符號。（這些設置將包含終端和非終端;不用擔心，就目前而言。）
執行以下操作，直到循環過程中沒有FIRST集改爲：
- 對於每個非末端ñ，對於每個非末端中號在FIRST（ñ），在FIRST添加的每一個元素（中號）到FIRST（N）（當然，除非它已經存在）。
刪除所有FIRST集合中的所有非終端。

上面假設你有一個計算可空性的算法。你也可以在Dragon Book中找到該算法;它有點類似。此外，你應該消除無用的生產;檢測它們的算法與可空性算法非常相似。

有一種算法通常更快，實際上並不複雜得多。一旦你完成上述算法的步驟1，你已經計算的關係引線，與（ñ，V），這是真的當且僅當一些生產非終結ñ開始與終端或非終端V，可能跳過可空的非終端。FIRST（N）然後是導致的傳遞性關閉 - 與其域限於終端。這可以使用Floyd-Warshall算法有效地計算（無遞歸），或使用Tarjan算法的變體來計算圖的強連通分量。（例如，參見Esko Nuutila's transitive closure page.）

來源

2016-03-01 16:08:37 rici

這清楚地解釋了算法。我很想在C中看到一個示例代碼。代碼將解決所有問題。 – K1b1w077

我很確定答案是這樣寫的，以幫助你學習和解決問題，因爲這似乎是一個班級任務。編寫解決方案不會實現這一目標。 –

如何在處理C中的長遞歸生成時防止堆棧溢出？

回答

相關問題