python - 在Python3中使用解析器模块计算表达式的时间复杂度(theta)是多少？

Question

我想知道 Python3 中的解析器模块用于评估表达式的算法或时间复杂度。

这是我的代码:

import random
import parser

equation_ = '(x**3 + 5*(x**2) - 3*x + 3) + (4*(x**5) - 2*(x**2) + 1)'

code = parser.expr(equation_).compile()
test_cases = [random.randrange(-100, 100) for _ in range(10)]

for x in test_cases:
    print(eval(code))

现在，我想知道使用了哪种算法或者该方法的时间复杂度是多少:parser.expr() 和 eval()。

我尝试阅读 documentation但无法弄清楚，source code 的情况也是如此。 :parser.c和parser.h

Answer 1

我无法说出Python的parser库中的具体算法，但一般来说解析是O(n)。它使用正则表达式从文本中提取标记流，然后将其与语法模式进行匹配，这可以通过表查找来完成。处理语法中的嵌套结构可能涉及递归，但这都是通过对输入进行固定次数的扫描来完成的。我认为 Python 是一种上下文无关语法，因此它应该可以通过一次解析来解析。

一旦解析了表达式，对其求值就具有与在普通源代码中编写该表达式相同的复杂性 - eval() 只是对 Python 的该部分的调用口译员。如果代码中没有循环，则时间复杂度为 O(n)。