解釋上下文無關文法（CFG）是否能被非確定性下推自動機識別。

上下文無關文法（CFG）肯定可以被非確定性下推自動機（NPDA）識別，但程式語言是透過確定性下推自動機（PDA）轉換為二進位制（機器碼）的。

這是因為這具有以下影響：

• 如果程式語言應該透過NPDA進行轉換，那麼對於一個給定的程式例項，我們將生成多個版本的二進位制（機器碼）用於同一個程式，這在理想情況下不應該發生。
• 對於一個給定的程式，應該只生成一個版本的二進位制程式碼，並且該程式碼應該在所有作業系統平臺上保持一致。
• 輸出將有很大差異：如果我們有多個目標檔案，那麼在一個情況下輸出可能是預期的，而在再次執行程式時，輸出將會有所不同，因為由於NPDA編譯過程發生了變化，因此目的碼的生成也發生了變化。因此，輸出是變化的，在許多情況下會導致錯誤的輸出。
• 語法的多重解釋可能導致無限迴圈：考慮一個具有終止條件的迴圈體的情況。透過多種編譯方式，許多關鍵字可能會被錯誤地解釋，如果未評估正確的終止條件，這可能會導致無限迴圈。例如，對於迴圈 (i = 0; i< n ; i++)，如果它被編譯為 (i = n; i >0; i++)，這將導致無限迴圈。
• 難以除錯 - 由於NPDA過程生成了多個版本的obj檔案，因此我們將發現很難除錯程式碼中的bug以修復它們。

Bhanu Priya

更新於： 2021年6月16日

512 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

開始學習