決定，如果不正確的程序可以有一個正確的延續

Question

（以下問題涉及OCaml的語言，並在OCaml的例子，但問題是非常普遍的，可能對任何其他計算機語言以正確的答案能解決我的問題太多這樣。 ，用你最喜歡的語言假設這個問題。）

我想寫一個函數，它將OCaml中的一個任意程序作爲一個字符串，並決定程序是正確還是不正確，以及在後一種情況下，我可以通過在最後連接適當的字符來將它變成正確的。

我假設有一個編譯器的語言在某處，我可以應用它，並得到一個答覆說「編譯」或「不編譯 - 在X行，字符Y的錯誤」（是反正大多數語言都是這種情況）。綜上所述，我想有一個函數，需要一個程序，並返回：

• 正確 - 如果字符串包含一個正確的程序;
• 錯誤的 - 如果字符串包含不正確的方案，其中，不管你怎麼串連字符的話，會不會變成正確的;
• 不完整 - 如果字符串包含不正確的方案，這是沒有錯。

例如，OCaml程序let x = f不正確，因爲f在使用時尚未定義。而且它不能繼續，因爲無論你在f後面寫什麼，總會是一些以前沒有定義過的標識符。程序let x =也是不正確的;但如果我們擴展到let x = 5那麼我們有一個完全有效的程序。所以，我的函數應該在第一種情況下返回錯誤，在第二種情況下返回不完整。

事情可能變得棘手，如果我們有程序

let ans = 5 
let x = a 

，因爲我的功能，就必須看到，如果我繼續運行程序與ns然後程序變得正確。

我的問題是：你認爲有可能編寫這樣的函數/算法嗎？如果是這樣，那麼總體思路是什麼？如果沒有，試着說服我，它不是。例如，我相信如果語言編譯器說在第3行有一個錯誤，並且程序有100行，那麼在那裏，我會很高興與任何見解或部分答案，例如暗示不完整的東西。是程序沒有可能繼續。）

Answer 1

在你的第一個例子，let x = f，如果我添加un y -> y？

我想你想要什麼是可能的，但沒有與當前的工具。如果您只對語法正確性感興趣，那麼基本思想是運行解析器/詞法分析器，如果它引發錯誤則返回「錯誤」;如果沒有返回完整的AST，則返回「不完整」，但沒有錯誤它仍然在等待更多的輸入）。

注：還有一個小錯配詞法分析器只會EOF之前返回一個令牌，這可能一直在繼續。您不需要將該令牌視爲完整的令牌，並在此時進行更精細的推理。更一般地說，您輸入的極值將需要專門的推理，我在這裏沒有涉及。

在lexing/parsing階段容易理解的屬性是詞法分析器是由分析器驅動的需求 - 它只讀取解析器推理令牌流的必要信息 - 解析器是「嚴格的」，還是提前失敗，而不是在故障現場要求更多的信息。

程序正確性的後一個主要階段是標識符解析（這個變量名是指什麼？）和類型系統 - 還有其他標準，比如檢查構造函數和類型名稱的arity，但是它們我不是很有意思。你的問題。這些通常不是以需求驅動的方式編寫的，或者不是更一般地試圖推斷部分信息。應該可以用這種方式重新設計它們，但這可能需要很多努力。

一個好的方向是「增量解析器」。許多人已經認識到與編輯器相關的程序工具（程序逐步編寫）需要增量性。他們解決了在源代碼發生具體變化後更新抽象信息的更一般問題;不僅是「最後添加」的變化，而且是更普遍的變化。他們的工具也可能解決你的問題。

編輯：啊，我終於找到了我在找的東西。你應該看看奧列格的differentiating parsers。