如何转译 python 将 ast 节点与 c 进行比较？
How to transpile python Compare ast nodes to c?
让我们从考虑 python3.8.5's grammar 开始，在这种情况下，我有兴趣弄清楚如何转译 python 与 c.
的比较
为了简单起见，假设我们正在处理一个非常小的 python 普通子集，我们只想转换普通的比较表达式：
expr = Compare(expr left, cmpop* ops, expr* comparators)
如果我没记错的话，在 python 中，诸如 a<b<c 的表达式被转换为类似于 a<b && b<c 的表达式，其中 b 仅被评估一次...所以我猜c 你应该做类似 bool v0=a<b; bool v1=v0<c 的事情，以防止 b 在第一个子句为真时被多次评估。
不幸的是，我不知道如何将其放入代码中，到目前为止，这就是我所得到的：
import ast
import shutil
import textwrap
from subprocess import PIPE
from subprocess import Popen
class Visitor(ast.NodeVisitor):
def visit(self, node):
ret = super().visit(node)
if ret is None:
raise Exception("Unsupported node")
return ret
def visit_Expr(self, node):
return f"{self.visit(node.value)};"
def visit_Eq(self, node):
return "=="
def visit_Lt(self, node):
return "<"
def visit_LtE(self, node):
return "<="
def visit_Load(self, node):
return "//load"
def visit_Name(self, node):
return f"{node.id}"
def visit_Compare(self, node):
left = self.visit(node.left)
ops = [self.visit(x) for x in node.ops]
comparators = [self.visit(x) for x in node.comparators]
if len(ops) == 1 and len(comparators) == 1:
return f"({left} {ops[0]} {comparators[0]})"
else:
lhs = ",".join([f"'{v}'" for v in ops])
rhs = ",".join([f"{v}" for v in comparators])
return f"cmp<{lhs}>({rhs})"
def visit_Call(self, node):
func = self.visit(node.func)
args = [self.visit(x) for x in node.args]
# keywords = [self.visit(x) for x in node.keywords]
return f"{func}({','.join(args)})"
def visit_Module(self, node):
return f"{''.join([self.visit(x) for x in node.body])}"
def visit_Num(self, node):
return node.n
if __name__ == "__main__":
out = Visitor().visit(
ast.parse(
textwrap.dedent(
"""
1 == 1<3
1 == (1<3)
1 == (0 < foo(0 <= bar() < 3, baz())) < (4 < 5)
foo(0 <= bar() < 3, baz())
"""
)
)
)
if shutil.which("clang-format"):
cmd = "clang-format -style webkit -offset 0 -length {} -assume-filename None"
p = Popen(
cmd.format(len(out)), stdout=PIPE, stdin=PIPE, stderr=PIPE, shell=True
)
out = p.communicate(input=out.encode("utf-8"))[0].decode("utf-8")
print(out)
else:
print(out)
如您所见，输出将是某种不可编译的 c 输出：
cmp<'==', '<'>(1, 3);
(1 == (1 < 3));
cmp<'==', '<'>((0 < foo(cmp<'<=', '<'>(bar(), 3), baz())), (4 < 5));
foo(cmp<'<=', '<'>(bar(), 3), baz());
问题，算法是什么（python 工作示例在这里是理想的，但只是一些允许我改进提供的代码段的通用伪代码也很好）让我能够convert python 将表达式与 c?
进行比较
正确翻译为：
if 1 == 2 < 3:
是：
int i1 = 1;
int i2 = 2;
int i3 = 3;
if(i1 == i2 && i2 < i3) {
（编辑：这仍然不正确，因为它没有短路）
或者，最后一个不一定是临时变量：
int i1 = 1;
int i2 = 2;
if(i1 == i2 && i2 < 3) {
或者：（此版本将被比较的表达式保留在比较表达式中）
int i1;
if(1 == (i1 = 2) && i2 < 3) {
您的编译器需要知道被比较的值是 int，以便它可以声明临时变量。而且它还需要选择每次都不同的临时变量名，所以如果你有两个这样的比较那么它不会尝试生成多个具有相同名称的变量。
您可能会意识到可以多次计算表达式 2，因此编译器可以生成以下代码：
if(1 == 2 && 2 < 3) {
但这是一个可选的附加项。
请注意，同一表达式中可能有多个：
if 1 < (2 if (6 < 7 < 8) else 3) < 4:
翻译成这样：
int i1 = 1;
int i2 = 6;
int i3 = 7;
int i4 = 8;
int i5 = (i2 < i3 && i3 < i4 ? 2 : 3);
int i6 = 4;
if(i1 < i5 && i5 < i6) {
或：
int i1;
int i2;
if(1 < (i1 = (6 < (i2 = 7) && i2 < 8 ? 2 : 3)) && i1 < 4) {
// ^^^^^^^^^^^^^^^^^^^^^^ inside
// ^^^^^^^^^^^ ^^^^^^^^^^^ outside
您正在寻找的方法，试图转到 class，将永远不会与 C 一起使用，因为 C 不支持 classes。如果您想将逻辑和 object 捆绑到一个简洁的单元中，您正在寻找 C++。
我能想到的最好的办法是创建一个全新的 Compare.c 文件，其中包含一个 header，它声明 struct Compare，它对来自 [= 的操作和比较器具有可变大小26=]，但即使使用 flexible array members，你仍然处于困境，因为你不能在一个结构中有两个灵活的数组，这意味着你需要一个 sub-struct（也许叫做 op) 具有元素 operand 和 comparator - 现在带来了另一个问题（假设 Python 的库支持它们） - 处理一元和三元运算符。
您可以使用 union 来处理支持 comparator 结构中的一元和三元运算符，但除此之外，您将涉入非常深的水域。
转换 Compare 表达式时的另一个复杂问题是，您要防止在拆分后多次使用的 sub-expressions 被多次求值，如果存在诸如以下的副作用，这一点尤为重要函数调用。
可以将 sub-expressions 提前声明为变量，以避免多次求值。
有一个聪明的方法可以将 Python 比较表达式转换为 JavaScript
亚历山大·谢帕诺夫斯基。他在他的博客 post 中详细解释了他的整个解决方案：http://hackflow.com/blog/2015/04/12/metaprogramming-beyond-decency-part-2/.
基本上相同的方法可以应用于 C 的转译。
他确定成对的相邻操作数。这是将链式比较转换为单独的比较所必需的，其中 'middle' 操作数随后被复制并且是拆分的第二个子比较的左操作数。
一种符号table可以用来将变量与sub-expressions联系起来。变量的命名可以通过一个简单的计数器来完成。
访问表达式节点时可以输出变量。要在 C 中为问题中作为示例给出的表达式获取输出，您可以简单地发出 printf.
为了进一步简化，我们可以假设假设的小而琐碎的 Python 子集只需要处理 int 表达式。
Python代码
我已经获取了您的代码片段并根据上述几点稍作修改，使其成为一个 self-contained 示例，可以为您的示例表达式输出可编译的 C 代码。
import ast
import itertools
import textwrap
def pairwise(iterable):
"""s -> (s0,s1), (s1,s2), (s2, s3), ..."""
a, b = itertools.tee(iterable)
next(b, None)
return zip(a, b)
class Visitor(ast.NodeVisitor):
def __init__(self):
self.varCounter = 0
self.varTable = []
def visit_Expr(self, node):
code = self.visit(node.value)
variables = '\n'.join(self.varTable)
self.varTable = []
return f'{variables}\nprintf("%d\n", {code});\n'
def visit_Eq(self, node):
return "=="
def visit_Lt(self, node):
return '<'
def visit_LtE(self, node):
return '<='
def visit_Gt(self, node):
return ">"
def visit_GtE(self, node):
return ">="
def visit_Name(self, node):
return str(node.id)
# see http://hackflow.com/blog/2015/04/12/metaprogramming-beyond-decency-part-2/
def visit_Compare(self, node):
ops = node.ops
operands = [node.left] + node.comparators
variables = []
for o in operands:
self.varCounter += 1
num = self.varCounter
op = self.visit(o)
variables.append((num, op))
self.varTable.append(f'int t{num} = {op};')
pairs = pairwise(variables) # adjacent pairs of operands
return ' && '.join('%s(%s %s %s)' %
('!' if isinstance(op, ast.NotIn) else '',
f't{l[0]}', self.visit(op), f't{r[0]}')
for op, (l, r) in zip(ops, pairs))
def visit_Call(self, node):
args = [self.visit(x) for x in node.args]
return self.visit(node.func) + "(" + ", ".join(args) + ")"
def visit_Num(self, node):
return str(node.n)
def main():
analyzer = Visitor()
tree = ast.parse(
textwrap.dedent(
"""
1 == 1<3
1 == (1<3)
1 == (0 < foo(0 <= bar() < 3, baz())) < (4 < 5)
foo(0 <= bar() < 3, baz())
"""
)
)
# print(ast.dump(tree))
for node in ast.iter_child_nodes(tree):
c = analyzer.visit(node)
print(c)
if __name__ == '__main__':
main()
测试运行
当您运行 Python 程序时，调试控制台中显示以下内容：
int t1 = 1;
int t2 = 1;
int t3 = 3;
printf("%d\n", (t1 == t2) && (t2 < t3));
int t4 = 1;
int t6 = 1;
int t7 = 3;
int t5 = (t6 < t7);
printf("%d\n", (t4 == t5));
int t8 = 1;
int t10 = 0;
int t12 = 0;
int t13 = bar();
int t14 = 3;
int t11 = foo((t12 <= t13) && (t13 < t14), baz());
int t9 = (t10 < t11);
int t16 = 4;
int t17 = 5;
int t15 = (t16 < t17);
printf("%d\n", (t8 == t9) && (t9 < t15));
int t18 = 0;
int t19 = bar();
int t20 = 3;
printf("%d\n", foo((t18 <= t19) && (t19 < t20), baz()));
当然有办法进一步简化这个。例如，常量表达式不需要分配给变量。当然还有更多的细节需要考虑。但这应该是为您的示例数据输出可编译 C 代码的起点。
让我们从考虑 python3.8.5's grammar 开始，在这种情况下，我有兴趣弄清楚如何转译 python 与 c.
的比较为了简单起见，假设我们正在处理一个非常小的 python 普通子集，我们只想转换普通的比较表达式：
expr = Compare(expr left, cmpop* ops, expr* comparators)
如果我没记错的话，在 python 中，诸如 a<b<c 的表达式被转换为类似于 a<b && b<c 的表达式，其中 b 仅被评估一次...所以我猜c 你应该做类似 bool v0=a<b; bool v1=v0<c 的事情，以防止 b 在第一个子句为真时被多次评估。
不幸的是，我不知道如何将其放入代码中，到目前为止，这就是我所得到的：
import ast
import shutil
import textwrap
from subprocess import PIPE
from subprocess import Popen
class Visitor(ast.NodeVisitor):
def visit(self, node):
ret = super().visit(node)
if ret is None:
raise Exception("Unsupported node")
return ret
def visit_Expr(self, node):
return f"{self.visit(node.value)};"
def visit_Eq(self, node):
return "=="
def visit_Lt(self, node):
return "<"
def visit_LtE(self, node):
return "<="
def visit_Load(self, node):
return "//load"
def visit_Name(self, node):
return f"{node.id}"
def visit_Compare(self, node):
left = self.visit(node.left)
ops = [self.visit(x) for x in node.ops]
comparators = [self.visit(x) for x in node.comparators]
if len(ops) == 1 and len(comparators) == 1:
return f"({left} {ops[0]} {comparators[0]})"
else:
lhs = ",".join([f"'{v}'" for v in ops])
rhs = ",".join([f"{v}" for v in comparators])
return f"cmp<{lhs}>({rhs})"
def visit_Call(self, node):
func = self.visit(node.func)
args = [self.visit(x) for x in node.args]
# keywords = [self.visit(x) for x in node.keywords]
return f"{func}({','.join(args)})"
def visit_Module(self, node):
return f"{''.join([self.visit(x) for x in node.body])}"
def visit_Num(self, node):
return node.n
if __name__ == "__main__":
out = Visitor().visit(
ast.parse(
textwrap.dedent(
"""
1 == 1<3
1 == (1<3)
1 == (0 < foo(0 <= bar() < 3, baz())) < (4 < 5)
foo(0 <= bar() < 3, baz())
"""
)
)
)
if shutil.which("clang-format"):
cmd = "clang-format -style webkit -offset 0 -length {} -assume-filename None"
p = Popen(
cmd.format(len(out)), stdout=PIPE, stdin=PIPE, stderr=PIPE, shell=True
)
out = p.communicate(input=out.encode("utf-8"))[0].decode("utf-8")
print(out)
else:
print(out)
如您所见，输出将是某种不可编译的 c 输出：
cmp<'==', '<'>(1, 3);
(1 == (1 < 3));
cmp<'==', '<'>((0 < foo(cmp<'<=', '<'>(bar(), 3), baz())), (4 < 5));
foo(cmp<'<=', '<'>(bar(), 3), baz());
问题，算法是什么（python 工作示例在这里是理想的，但只是一些允许我改进提供的代码段的通用伪代码也很好）让我能够convert python 将表达式与 c?
进行比较正确翻译为：
if 1 == 2 < 3:
是：
int i1 = 1;
int i2 = 2;
int i3 = 3;
if(i1 == i2 && i2 < i3) {
（编辑：这仍然不正确，因为它没有短路）
或者，最后一个不一定是临时变量：
int i1 = 1;
int i2 = 2;
if(i1 == i2 && i2 < 3) {
或者：（此版本将被比较的表达式保留在比较表达式中）
int i1;
if(1 == (i1 = 2) && i2 < 3) {
您的编译器需要知道被比较的值是 int，以便它可以声明临时变量。而且它还需要选择每次都不同的临时变量名，所以如果你有两个这样的比较那么它不会尝试生成多个具有相同名称的变量。
您可能会意识到可以多次计算表达式 2，因此编译器可以生成以下代码：
if(1 == 2 && 2 < 3) {
但这是一个可选的附加项。
请注意，同一表达式中可能有多个：
if 1 < (2 if (6 < 7 < 8) else 3) < 4:
翻译成这样：
int i1 = 1;
int i2 = 6;
int i3 = 7;
int i4 = 8;
int i5 = (i2 < i3 && i3 < i4 ? 2 : 3);
int i6 = 4;
if(i1 < i5 && i5 < i6) {
或：
int i1;
int i2;
if(1 < (i1 = (6 < (i2 = 7) && i2 < 8 ? 2 : 3)) && i1 < 4) {
// ^^^^^^^^^^^^^^^^^^^^^^ inside
// ^^^^^^^^^^^ ^^^^^^^^^^^ outside
您正在寻找的方法，试图转到 class，将永远不会与 C 一起使用，因为 C 不支持 classes。如果您想将逻辑和 object 捆绑到一个简洁的单元中，您正在寻找 C++。
我能想到的最好的办法是创建一个全新的 Compare.c 文件，其中包含一个 header，它声明 struct Compare，它对来自 [= 的操作和比较器具有可变大小26=]，但即使使用 flexible array members，你仍然处于困境，因为你不能在一个结构中有两个灵活的数组，这意味着你需要一个 sub-struct（也许叫做 op) 具有元素 operand 和 comparator - 现在带来了另一个问题（假设 Python 的库支持它们） - 处理一元和三元运算符。
您可以使用 union 来处理支持 comparator 结构中的一元和三元运算符，但除此之外，您将涉入非常深的水域。
转换 Compare 表达式时的另一个复杂问题是，您要防止在拆分后多次使用的 sub-expressions 被多次求值，如果存在诸如以下的副作用，这一点尤为重要函数调用。
可以将 sub-expressions 提前声明为变量，以避免多次求值。
有一个聪明的方法可以将 Python 比较表达式转换为 JavaScript 亚历山大·谢帕诺夫斯基。他在他的博客 post 中详细解释了他的整个解决方案：http://hackflow.com/blog/2015/04/12/metaprogramming-beyond-decency-part-2/.
基本上相同的方法可以应用于 C 的转译。
他确定成对的相邻操作数。这是将链式比较转换为单独的比较所必需的，其中 'middle' 操作数随后被复制并且是拆分的第二个子比较的左操作数。
一种符号table可以用来将变量与sub-expressions联系起来。变量的命名可以通过一个简单的计数器来完成。
访问表达式节点时可以输出变量。要在 C 中为问题中作为示例给出的表达式获取输出，您可以简单地发出 printf.
为了进一步简化，我们可以假设假设的小而琐碎的 Python 子集只需要处理 int 表达式。
Python代码
我已经获取了您的代码片段并根据上述几点稍作修改，使其成为一个 self-contained 示例，可以为您的示例表达式输出可编译的 C 代码。
import ast
import itertools
import textwrap
def pairwise(iterable):
"""s -> (s0,s1), (s1,s2), (s2, s3), ..."""
a, b = itertools.tee(iterable)
next(b, None)
return zip(a, b)
class Visitor(ast.NodeVisitor):
def __init__(self):
self.varCounter = 0
self.varTable = []
def visit_Expr(self, node):
code = self.visit(node.value)
variables = '\n'.join(self.varTable)
self.varTable = []
return f'{variables}\nprintf("%d\n", {code});\n'
def visit_Eq(self, node):
return "=="
def visit_Lt(self, node):
return '<'
def visit_LtE(self, node):
return '<='
def visit_Gt(self, node):
return ">"
def visit_GtE(self, node):
return ">="
def visit_Name(self, node):
return str(node.id)
# see http://hackflow.com/blog/2015/04/12/metaprogramming-beyond-decency-part-2/
def visit_Compare(self, node):
ops = node.ops
operands = [node.left] + node.comparators
variables = []
for o in operands:
self.varCounter += 1
num = self.varCounter
op = self.visit(o)
variables.append((num, op))
self.varTable.append(f'int t{num} = {op};')
pairs = pairwise(variables) # adjacent pairs of operands
return ' && '.join('%s(%s %s %s)' %
('!' if isinstance(op, ast.NotIn) else '',
f't{l[0]}', self.visit(op), f't{r[0]}')
for op, (l, r) in zip(ops, pairs))
def visit_Call(self, node):
args = [self.visit(x) for x in node.args]
return self.visit(node.func) + "(" + ", ".join(args) + ")"
def visit_Num(self, node):
return str(node.n)
def main():
analyzer = Visitor()
tree = ast.parse(
textwrap.dedent(
"""
1 == 1<3
1 == (1<3)
1 == (0 < foo(0 <= bar() < 3, baz())) < (4 < 5)
foo(0 <= bar() < 3, baz())
"""
)
)
# print(ast.dump(tree))
for node in ast.iter_child_nodes(tree):
c = analyzer.visit(node)
print(c)
if __name__ == '__main__':
main()
测试运行
当您运行 Python 程序时，调试控制台中显示以下内容：
int t1 = 1;
int t2 = 1;
int t3 = 3;
printf("%d\n", (t1 == t2) && (t2 < t3));
int t4 = 1;
int t6 = 1;
int t7 = 3;
int t5 = (t6 < t7);
printf("%d\n", (t4 == t5));
int t8 = 1;
int t10 = 0;
int t12 = 0;
int t13 = bar();
int t14 = 3;
int t11 = foo((t12 <= t13) && (t13 < t14), baz());
int t9 = (t10 < t11);
int t16 = 4;
int t17 = 5;
int t15 = (t16 < t17);
printf("%d\n", (t8 == t9) && (t9 < t15));
int t18 = 0;
int t19 = bar();
int t20 = 3;
printf("%d\n", foo((t18 <= t19) && (t19 < t20), baz()));
当然有办法进一步简化这个。例如，常量表达式不需要分配给变量。当然还有更多的细节需要考虑。但这应该是为您的示例数据输出可编译 C 代码的起点。