Sur*_*tor 3 compiler-construction ocaml programming-languages compiler-theory
(以下问题涉及OCaml语言并且在OCaml中有示例,但问题非常普遍,对于任何其他计算机语言来说,正确答案也可能解决我的问题.所以,只需用您最喜欢的语言来假设这个问题.)
我想编写一个函数,它将OCaml中的任意程序作为字符串,并决定程序是正确还是不正确,在后一种情况下,我是否可以通过在最后连接适当的字符使其成为正确的程序.
我假设有一个语言的编译器,我可以应用它并得到一个回复,说"编译"或"不编译 - 错误在第X行,字符Y"(大多数情况下)语言无论如何).总之,我想有一个函数,它接受一个程序并返回:
例如,OCaml程序let x = f不正确,因为f它在使用时尚未定义.它不能继续,因为你在f之后写的东西总是一些以前没有定义过的标识符.该程序let x =也是不正确的; 但如果我们延伸到let x = 5那时我们有一个完全有效的程序.所以,我的函数应该在第一种情况下返回Erroneous而在第二种情况下返回Incomplete.
如果我们有这个计划,事情可能会变得棘手
let ans = 5
let x = a
因为我的功能必须要看到如果我继续该程序,ns那么程序就变得正确了.
我的问题是:你认为有可能编写这样的函数/算法吗？如果是这样,那么一般的想法是什么？如果没有,试着说服我,事实并非如此.
(我会对任何见解或部分答案感到满意,例如暗示不完整的东西.例如,我相信如果语言编译器说第3行有错误并且程序有100行,那么就没有可能继续该计划.)
在你的第一个例子中,let x = f如果我添加un y -> y怎么办？
我认为你想要的是可能的,但目前的工具却没有.如果你只对句法正确性感兴趣,基本的想法是运行解析器/词法分析器,如果它引发错误则返回"错误",如果它没有返回完整的AST则返回"不完整",但没有错误(所以它还在等待更多的输入).
注意:仍然存在一个小的不匹配,因为词法分析器将在EOF之前返回一个令牌,这可能已经继续.您不需要将该令牌视为完整令牌,并在此时进行更精细的推理.更一般地说,您输入的极值将需要我在此处未涵盖的专门推理.
在lexing/parsing阶段轻松实现的属性是词法分析器由解析器驱动需求 - 它只读取解析器所需的时间来推理令牌流 - 并且解析器是"严格的" ,或提前失败,而不是在故障站点要求更多信息.
程序正确性的后一个主要阶段是标识符解析(这个变量名称是指什么？)和类型系统 - 还有其他标准,例如检查构造函数和类型名称的arity,但它们不是很有趣的wrt.你有问题 这些通常不是以需求驱动的方式编写的,或者通常不会尝试推理部分信息.应该可以用这种方式重新设计它们,但这可能需要付出很多努力.
一个好的方向是"增量解析器".许多人已经认识到与编辑器相关的程序工具的增量性需求(程序是逐步编写的).他们解决了在源代码中进行具体更改后更新抽象信息的更普遍的问题; 不仅是"最后添加"的更改,而是更一般的更改.他们的工具也可能解决你的问题.
编辑:啊,我终于找到了我想要的东西.你应该看看Oleg的差异化解析器.