问题描述
初学编译原理，想写一个简单的编译器。A Compiler is just a Staged Interpreter Rewriting under Algebraic Law, what's the problem?
考虑如下语言:
class Expr:
pass
class Lit(Expr):
def __init__(self, i: int):
self.i = i
class Var(Expr):
def __init__(self, name: str):
self.name = name
class Plus(Expr):
def __init__(self, l: Expr, r: Expr):
self.l = l
self.r = r
class Mult(Expr):
def __init__(self, l: Expr, r: Expr):
self.l = l
self.r = r适合PL宝宝体质的教学语言。
def interpret(e: Expr, env: dict[str, int]) -> int:
if isinstance(e, Lit):
return e.i
elif isinstnace(e, Var):
return env[e.name]
elif isinstance(e, Plus):
return interpret(e.l, env) + interpret(e.r, env)
elif isinstance(e, Mult):
return interpret(e.l, env) * interpret(e.r, env)
else:
assert False一个标准的tree walking interpreter。
现在看我施展魔法，把这变成编译器！
def compile(e: Expr) -> str:
if isinstance(e, Lit):
return f"{e.i}"
elif isinstnace(e, Var):
return f"""env["{e.name}"]"""
elif isinstance(e, Plus):
return f"({compile(e.l)} + {compile(e.r)})"
elif isinstance(e, Mult):
return f"({compile(e.l)} * {compile(e.r)})"
else:
assert False噔噔！现在就是编译器了，是不是很神奇呢！
考虑我们有(2 + 4) + X，这段代码在解释器中，我们需要不停递归访问这个AST，而这很耗性能。但是，当我们用编译器的时候，我们可以在编译期递归访问AST，生成一段合法的python（或者C++，这同时是两个语言的合法代码，编译，很神奇吧！）代码，而这时候我们就不需要继续tree walk了。编译器的优势，正是宇宙可能还没给你X的值，这时候解释器在干瞪眼，但是编译器来骗来偷袭宇宙这个一百三十八亿年的老同志，先偷跑把工作做了，利用了一些废物时间，但是对宇宙的坏影响不可估量。
但是，我们每次访问一个变量，我们都需要进行一个hashtable of string的查找。数据结构是这样的，hashtable只需要不停构建string，取hash解collison就行了，array要考虑的就多了。
没问题，正如同我们把tree walking提前到编译时，我们也可以把hashtable访问提前到编译时。
symbol_table: dict[str, int] = {}
def symbol(s: str): int =
if s not in symbol_table:
symbol_table[s] = len(symbol_table)
return symbol_table[s]
def compile(e: Expr) -> str:
# ...
elif isinstnace(e, Var):
return f"""{env["{symbol(e.name)}"]}"""
# ...这时候全部引用都是连续小数字，比如什么0 1 2 3 4，运行时的env我们就不需要用dict了，一个array就可以了。但是要注意，hashtable没被我们消灭，只是把天赋带到了编译期，换了个叫intern_table的球衣号码继续吃香喝辣。
我们能不能再给点力呢？如果你拿了数学诺贝尔奖，为国争光，你就可以注意到，
(2 + 4) + X的左边没有任何的X，我们可以在编译期就算出这的值，变成6 + X。
def compile(e: Expr) -> Union[int, str]:
if isinstance(e, Lit):
return e.i
elif isinstnace(e, Var):
return f"""{env["{symbol(e.name)}"]}"""
elif isinstance(e, Plus):
l = compile(e.l)
r = compile(e.r)
if isinstance(l, int) and isinstance(r, int):
return l + r
else:
return f"({l} + {r})"
elif isinstance(e, Mult):
l = compile(e.l)
r = compile(e.r)
if isinstance(l, int) and isinstance(r, int):
return l * r
else:
return f"({l} * {r})"
else:
assert False哇！很有精神！
如果你的数学方面超过了诺贝尔奖，足够承担下伦敦铸币厂部门主管岗位，你就可以发现
(0 + X) = (X + 0) = X = (1 * X) = (X * 1) 跟
(0 * X) = (X * 0) = 0
这些妙妙公式。我们就可以在那怕有X的情况下，继续化简计算！
def compile(e: Expr) -> Union[int, str]:
# ...
elif isinstance(e, Plus):
l = compile(e.l)
r = compile(e.r)
if isinstance(l, int) and isinstance(r, int):
return l + r
elif l == 0:
return r
elif r == 0:
return l
else:
return f"({l} + {r})"
elif isinstance(e, Mult):
l = compile(e.l)
r = compile(e.r)
if isinstance(l, int) and isinstance(r, int):
return l * r
elif l == 0 or r == 0:
return 0
elif l == 1:
return r
elif r == 1:
return l
else:
return f"({l} * {r})"
# ...如果你的数学再好好好一些，可以进行服装设计，你就能发现交配律，结合律，跟分换律。
这时候，我们就能把(2 + (X + 3)) * 4优化成20 + (4 * X)了！
def compile(e: Expr) -> tuple[int, Optional[str]]:我们返回的，永远有一个int，代表着静态部分。同时，我们可能有一些代码，代表着动态部分。
# ...
if isinstance(e, Lit):
return (e.i, None)
elif isinstnace(e, Var):
return (0, f"""{env["{symbol(e.name)}"]}""")
elif isinstance(e, Plus):
ls, ld = compile(e.l)
rs, rd = compile(e.r)
if not ld and not rd:
return (ls + rs, None)
elif not ld and rd:
return (ls + rs, rd)
elif ld and not rd:
return (ls + rs, ld)
else:
assert ld and rd
return (ls + rs, f"({ld} + {rd})")
elif isinstance(e, Mult):
ls, ld = compile(e.l)
rs, rd = compile(e.r)
if not ld and not rd:
return (ls * rs, None)
elif not ld and rd:
if ls == 0:
return (ls * rs, None)
elif ls == 1:
return (ls * rs, rd)
else:
return (ls * rs, f"({ls} * {rd})")
elif ld and not rd:
if rs == 0:
return (ls * rs, None)
elif rs == 1:
return (ls * rs, ld)
else:
return (ls * rs, f"({ld} * {rs})")
else:
assert ld and rd
return (ls * rs, f"({ls} * {rd} + {ld} * {rs} + {ld} * {rd})")
# ...搞定！能不能更厉害一些呢？
不能。
因为我饿了，要去吃饭。