查找跟隨集 - 無限遞歸

找到跟隨集時，規則（如 A->aA）可能會導致無限遞歸。有沒有任何編碼技術可以避免它？查找跟隨集 - 無限遞歸

請注意，上面的例子只是一個例子，實際上這種遞歸也可能間接發生。

這是我的示例C代碼，用於查找跟隨集。語法存儲爲鏈表的數組。 請告訴我，代碼在任何時候都不清楚。

set findFollowSet(char nonTerminal[], Grammar G, hashTable2 h) //later assume that all first sets are already in the hashtable. 
{ 
    LINK temp1 = find2(h, nonTerminal);  
    set s= createEmptySet(); 
    set temp = createEmptySet(); 
    char lhs[80] = "\0"; 
    int i; 

    //special case 
    if(temp1->numRightSideOf==0)  //its not on right side of any grammar rule 
     return insert(s, "$"); 

    for(i=0;i<temp1->numRightSideOf;i++) 
    { 
     link l = G.rules[temp1->rightSideOf[i]]; 

     strcpy(lhs, l->symbol);  //storing the lhs just in case the nonTerm appears on the rightmost end of the rule. 
     printf("!!!!! %s\n", lhs); 
     sleep(1); 
     //finding nonTerminal in G 
     while(l!=NULL) 
     { 
      if(strcmp(l->symbol, nonTerminal) == 0) 
      break; 

      l=l->next; 
     } 
     //found the nonTerminal in G 

     if(l->next!=NULL) 
     { 
      temp = findFirstSet(l->next, G, h); 
      temp = removeElement(temp, "EPSILON"); 
     } 

     else //its on the rightmost end of the rule 
      temp = findFollowSet(lhs, G, h); 

     s = setUnion(s, temp); destroySet(temp); 
    } 
    return s; 
}

來源

2014-03-13 ishan3243

在任何遞歸，要做的第一件事是在什麼是你的「停止條件」決定。有了這個條件，該函數將停止遞歸併簡單地返回。 – anonymous

@anonymous，那麼這將是什麼基礎的情況？ – ishan3243

我不知道findFollowSet（）意味着什麼或它意味着什麼。我將不得不穀歌了一些關於「遵循集合」的信息，除非你可以舉一些你想要做的事情的例子。啊..編譯器理論101.我在學校時沒有考慮到的東西:-)這是一個選修課，但我會讀它 – anonymous

FIRST和FOLLOW集是遞歸定義的，所以你需要找到遞歸閉包。這在實踐中意味着你沒有找到FOLLOW爲單個非終端設置 - 你可以同時找到所有終端的所有FOLLOW設置，從所有的設置開始空着，並重復語法，爲不同的符號添加符號設置，直到沒有更多符號可以添加到任何集合。所以，你最終的東西，如：

FOLLOW[*] = {}; // all follow sets start empty 
done = false; 
while (!done) 
    done = true; 
    for (R : each rule in the grammar) 
     A = RHS[R]; 
     tmp = FOLLOW[A]; 
     for (S : each symbol in LHS[R] from right to left) 
      if (S is terminal) 
       tmp = {S}; 
      else 
       if (!(FOLLOW[S] contains tmp)) 
        done = false 
        FOLLOW[S] |= tmp 
       if (epsilon in FIRST[S]) 
        tmp |= FIRST[S] - epsilon 
       else 
        tmp = FIRST[S]

來源

2014-03-13 05:05:27

好的我得到了答案，但效率不高。所以，如果有人想提出一些更有效的答案，請感受歡迎。

只需顯式地存儲遞歸堆棧並在每次遞歸調用時檢查該條目是否已存在於堆棧中。請注意，你需要檢查整個堆棧，而不僅僅是堆棧的頂部。

來源

2014-03-13 05:02:05 ishan3243

這是如何回答這個問題？ – ibid

@ibid爲什麼它不是？ – ishan3243

它看起來像一個其他答案的評論，而不是一個答案。 – ibid

查找跟隨集 - 無限遞歸

回答

相關問題