如何通过类型推断处理前向引用

问题描述 投票:0回答:1

为oop语言制作一个编译器,使用相同的语言。编译器当前遍历 ast 4 次,前两次用于解析类型链,第三次用于填充符号表以供将来查找,最后一次用于解析符号。在解析过程中,我还尝试进行类型推断来解析变量符号的类型。

这是我用来测试编译器的示例代码。

var c = a.name;

var a = TestClass(1);

var d = a.test(1);

class TestClass<E> {
  TestClass(E name) : this.name = name;

  TestClass.create(this.name);

  E name;

  E test(E element) {
    return element;
  }

}

在上面的代码中,c依赖于a来推断自己的类型,但a也需要类型推断。因此,当编译器在解析 c 的类型时尝试查找 a 时,它会变得未知并引发错误。

这是我第一次制作编译器,我不知道如何解决这个问题。

oop compiler-errors compiler-construction compiler-optimization type-inference
1个回答
0
投票

解决问题

您需要生成(未知)类型的依赖关系图作为第一个类型推断过程。作为一种数据结构,映射可以是一组对或一组关联数组。此处使用前者是为了说明目的。对于提供的示例,我们将有一个依赖关系图,如下所示:

c -> a.name 
a.name -> a
a -> TestClass(1)
TestClass(1) -> TestClass
d -> a.test(1)
a.test(1) -> a.test
a.test -> a

请注意,未知数可能依赖于多个其他未知数。例如,如果我们有类似

var a = b + c
的东西,那么我们就会同时拥有
a -> b
a -> c
作为依赖项。

我保留了数字文字

1
,因为我不知道 Dart 是否允许模板具有 C++
template <unsigned i>
的常量。如果没有,我们可以使用数字文字的类型(例如
int
Number
Literal<int>
)来加快分析速度。

我们不添加隐式模板参数,因为我们不知道哪些调用是对模板函数/类进行的。如果显式提供模板参数来初始化

a
,我们将为
a
提供以下依赖项。

a -> TestClass<int>(1)
TestClass<int>(1) -> TestClass<int>
TestClass<int> -> TestClass

然后我们可以获取依赖图中的所有未知数,并将依赖项排序在相应的依赖项之后。排序后,我们可以解析每个未知数的类型,而不会遇到问题。例如,排序后我们会得到以下列表:

TestClass
TestClass(1)
a
a.test
a.test(1)
d
a.name
c

提高性能

为了减少排序的计算成本并检测和报告/解决循环依赖关系,我们可以在排序之前计算每个未知数的完整依赖关系集。为此,我们重复扩展依赖关系图中的每个依赖关系,直到依赖关系图不再发生变化;在与编译器相关的文献中,该过程有时被称为“闭包”。作为伪代码,该过程可以表示为:

let set: set of (T, T); # our set of dependencies
let unknowns: set of T; # the set of all the unknowns
let prevSize = 0;

while prevSize < set.size: # continue while set is growing
    prevSize = set.size;
    for every (dependent, dependency) in set: # b -> c
        for every unknown in unknowns:
            if (unknown, dependent) in set: # if a -> b, then a -> c
                add (unknown, dependency) to set

只有在完全遍历 AST 后,扩展才会完成,尽管我们可以在将新依赖项添加到依赖项映射的每个步骤中进行部分更新。在最终的集合中,循环依赖将以

unknown -> unknown
的形式出现。为了说明结果集,这里是所提供示例的部分结果(没有循环依赖项):

c -> a.name
c -> a
c -> TestClass(1)
c -> TestClass
...
d -> a.test(1)
d -> a.test
d -> a
d -> TestClass(1)
d -> TestClass
a.test(1) -> a.test
a.test(1) -> a
a.test(1) -> TestClass(1)
a.test(1) -> TestClass
...
© www.soinside.com 2019 - 2024. All rights reserved.