Alpha以多种语言重命名

Question

我有我想象的将是一个相当复杂的技术挑战:我希望能够以多种语言(尽可能多的)可靠地对重命名标识符进行alpha重命名.这需要特别考虑每种语言,我正在寻求建议,以便通过共享代码来最大限度地减少我需要做的工作量.像已经支持多种语言的统一解析或抽象语法框架这样的东西会很棒.

例如,这是一些python代码:

def foo(x):
    def bar(y):
        return x+y
    return bar

的α重命名x以y 改变x到y和保持语义.所以它会成为:

def foo(y):
    def bar(y1):
        return y+y1
    return bar

了解我们如何重命名y以y1避免破坏代码？这就是为什么这是一个难题.似乎程序必须非常了解构成范围的内容,而不仅仅是进行字符串搜索和替换.

我还想尽可能多地保留格式:注释,间距,缩进.但这不是100%必要的,它会很好.

有小费吗？

Answer 1

要安全地执行此操作,您需要能够确定

• 代码中的所有标识符(以及那些不是,例如,注释的中间)
• 每个标识符的有效范围
• 能够在文本中替换旧标识符的新标识符
• 确定是否重命名标识符导致另一个名称被遮蔽的能力

要准确地确定标识符,您至少需要一个语言准确的词法分析器.PHP中的标识符看起来与COBOL中的标识符不同.

要确定有效范围,您必须在实践中确定程序结构,因为大多数"范围"都是由这种结构定义的.这意味着你需要一个语言准确的解析器; PHP中的范围与COBOL中的范围不同.

要确定哪些名称在哪些范围内有效,您需要了解语言范围规则.您的语言可能会坚持标识符X将根据找到X的上下文引用不同的Xes(考虑使用不同参数命名为X的对象构造函数).现在,您需要能够根据命名规则遍历范围结构.单继承,多继承,重载,默认类型都需要你为程序构建一个范围模型,将标识符和相应的类型插入每个范围,然后从遇到标识符的角度爬上去根据语言语义通过各种范围编写文本.您将需要符号表,继承链接,AST以及导航所有这些的能力.这些结构与PHP和COBOL不同,但它们共享许多常见的想法,因此您可能需要具有通用概念支持的库.

要重命名标识符,您必须修改文本.在一百万行代码中,您需要仔细指出.修改AST节点是一种仔细指出的方法.实际上,您需要修改与重命名的标识符对应的所有标识符; 你必须爬过树才能找到它们,或者在AST中记录所有参考文献,以便轻松找到它们.修改树后,必须在修改AST后重新生成源文本.这是很多机器; 看看我的答案如何漂亮印刷ASTs预先显示你应该保留的所有你合理建议的东西.(您的另一个选择是跟踪字符串文本所在的AST,以及读取/修补/写入文件.)

在更新文件之前,您需要检查是否有阴影.考虑以下代码:

 {  local x;
     x=1;
    {local y;
     y=2;
      {local z;
         z=y
         print(x);
      }
    }
 }

我们同意此代码打印"1".现在我们决定将y重命名为x.我们已经打破了范围,现在从概念上提到外部x的print语句指的是由重命名的y捕获的x.代码现在打印"2",所以我们的重命名打破了它.这意味着必须检查可能在其中找到重命名变量的范围中的所有其他标识符,以查看新名称是否"捕获"了我们不期望的某个名称.(如果打印声明打印z,这将是合法的).

这是很多机器.

是的,有一个框架几乎包含所有这些以及许多强大的语言前端.请参阅我们的DMS软件再造工具包.它具有生成AST的解析器,用于从AST生成文本的prettyprinters,通用符号表管理机制(包括支持多重继承),AST访问/修改机制.它有漂亮的印刷机制将AST转回文本.它具有实现名称和类型解析的C,C++,COBOL和Java的前端(例如,即时符号表范围和符号表条目映射的标识符); 它有许多其他尚未实施范围的语言的前端.

我们刚刚完成了为Java实现"重命名"的练习.(当然所有上述问题都出现了).我们即将为C++启动一个.